40. Bundeswettbewerb

Material zu den Aufgaben der 2. Runde

Hier steht das Material für die 2. Runde des 40. Bundeswettbewerbs zum Download bereit. Fragen zu den Aufgaben werden im Community-Forum des Portals Einstieg Informatik beantwortet, ein wiederholter Blick dorthin lohnt sich also. Wertvolle Anregungen geben aber auch die Tipps und Beispiellösungen der Vorjahre. Wichtig sind zudem die Beschreibungen von Inhalt und Struktur der einzureichenden ZIP-Archivdatei mit den Aufgabenlösungen.

Das Material steht zusammen mit den Aufgaben auch in einer ZIP-Archivdatei bwinf40-runde2.zip zur Verfügung.

Git Repository

Unter https://git.bwinf.de könnt ihr euch mit eurem BWINF-Account eigene Git-Repositories anlegen.

Vorlagen

Unter Vorlagen sowie unter https://git.bwinf.de/bwinf/vorlagen.git haben wir Vorlagen für die Dokumentation zur Verfügung gestellt.

Beispieleingaben und -ausgaben

Bitte gebt alle zusätzlich von euch erdachten Beispiele in einer separaten Textdatei mit ab. Auch alle Ergebnisse bzw. Beispielausgaben bitte in einer jeweiligen Textdatei mit eindeutiger Benennung (Ergebnisdatei) mit abgeben. Dies gilt natürlich zusätzlich zur Angabe aller Ergebnisse in der Dokumentation.


Aufgabe 1: Müllabfuhr

Zu dieser Aufgabe gibt es neun Beispieleingaben:

Jede Datei beschreibt einen Straßenplan und enthält

  • in der ersten Zeile die Anzahl n an Kreuzungen und die Anzahl m an Straßen und
  • in den folgenden m Zeilen je drei (natürliche) Zahlen a, b und l, die eine Straße beschreiben: a und b ist jeweils die Nummer einer Kreuzung, und l gibt die Länge der Straße zwischen diesen beiden Kreuzungen an (in Kilometern). Das Ende einer Sackgasse gilt ebenfalls als eine Kreuzung.

Die Zentrale ist in den Beispielen immer Kreuzung 0.

Die Datei muellabfuhr0.txt entspricht dem Beispiel aus der Aufgabenstellung.

Hinweis zur Dokumentation: Damit auch die Ergebnisse zu den größeren Beispieleingaben einfach überprüft werden können, sollte in einer Ergebnisdatei pro Zeile jeweils ein Tag mit einer Auflistung aller besuchten Kreuzungen (in der richtigen Reihenfolge) stehen, gefolgt von der Gesamtlänge des Weges. Als Beispiel ist hier ein mögliches Ergebnis muellabfuhr0-ans.txt zur Beispieleingabe muellabfuhr0.txt zu sehen.


Aufgabe 2: Rechenrätsel

Zu dieser Aufgabe gibt es keine Beispieleingaben. Es wird erwartet, dass interessante Rätsel mit mindestens 15 Operatoren generiert werden können. Die Dokumentation sollte Rätsel mit mindestens sechs verschiedenen Operatorenanzahlen enthalten, darunter die Anzahlen 2 und 3.

Hinweis zur Dokumentation: Um zu gewährleisten, dass die Korrektheit der Rätsel einfach überprüft werden kann, sollte zusätzlich auch die Lösung mit angegeben werden.


Aufgabe 3: Hex-Max

Zu dieser Aufgabe gibt es sechs Beispieleingaben:

Jede Datei beschreibt eine Problemstellung und enthält

  • in der ersten Zeile die Hexadezimalzahl und
  • in der zweiten Zeile die maximale Anzahl an Umlegungen.

Die Datei hexmax0.txt entspricht dem Beispiel aus der Aufgabenstellung. Es wird erwartet, dass (mindestens) die Beispiele hexmax0.txt bis hexmax4.txt erfolgreich gelöst werden. Das größere Beispiel hexmax5.txt dient als Herausforderung.

Hinweis zur Dokumentation: Die Ausgabe des Zwischenstandes nach jeder Umlegung, also der aktuellen Belegung der Positionen, wird nur für die Beispiele hexmax0.txt, hexmax1.txt und hexmax2.txt verlangt. Für die Beispiele hexmax3.txt, hexmax4.txt und hexmax5.txt reicht es aus, die größte Hexadezimalzahl zu dokumentieren, die mit höchstens m Umlegungen erzeugt werden kann. In den Ergebnisdateien reicht die finale Hexadezimalzahl. Eine Auflistung der Umlegungen ist außerhalb der Dokumentation nicht noch einmal gefordert.


Bonusaufgabe: Zara Zackigs Zurückkehr

Zu dieser Aufgabe gibt es sechs Beispieleingaben:

Jede Datei beschreibt einen Stapel Karten und enthält

  • in der ersten Zeile
    • die Gesamtanzahl n an Karten,
    • die Anzahl k von Zaras Öffnungskarten (zusammen mit der Sicherungskarte besitzt Zara also k + 1 Karten und die Freunde haben n - k - 1 Karten hinzugefügt) und
    • die Anzahl m an Bits auf jeder Karte sowie
  • in den folgenden n Zeilen die Codes jeder Karte mit jeweils m Bits.

Die Datei stapel2.txt enthält die in der Aufgabenstellung genannten 111 Karten. Es wird erwartet, dass (mindestens) dieses Beispiel erfolgreich gelöst wird. Die größeren Beispiele stapel3.txt, stapel4.txt und stapel5.txt dienen als Herausforderung, die kleineren zum Testen.

Hinweis zur Dokumentation: Ähnlich wie beim Eingabeformat sollen in einer Ergebnisdatei pro Zeile die Bits einer Karte gelistet sein.