38. Bundeswettbewerb

Material zu den Aufgaben der 1. Runde

Hier steht das Material für die 1. Runde des 38. BwInf zum Download bereit (letzte Änderung: 31. August 2019). Einige Fragen zu den Aufgaben sind bereits 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.

Das Material steht zusammen mit den Aufgaben auch in einem Git-Repository auf git.bwinf.de zur Verfügung. Wenn Git installiert ist, kann man das Repository mit dem folgenden Kommandozeilenbefehl auf den eigenen Rechner klonen:

git clone https://git.bwinf.de/bwinf/bwinf38-runde1.git

Vorlagen

Im Folgenden findet ihr drei Vorlagen (letzte Änderung: 31. August 2019), die ihr für eure Dokumentation der Aufgabenbearbeitungen verwenden könnt (aber nicht müsst).

Eine kurze Anleitung, wie man mit LaTeX Texte schreibt, haben wir für euch hier bereitgestellt: LaTeX-Kurzanleitung.

Alle Vorlagen befinden sich auch in einem Git-Repository unter https://git.bwinf.de/bwinf/vorlagen.

Allgemeiner Hinweis: Nur die Quelltexte der implementierten Programme können komplett englischsprachig sein, d.h. auch Bezeichner und Kommentare im Programmcode dürfen in Englisch geschrieben sein.

Junioraufgabe 1: Parallelen

Zu dieser Aufgabe gibt es eine zu verarbeitende Textdatei mit Morgensterns Gedicht (letzte Änderung: 31. August 2019):

Jede Zeile der Textdatei enthält eine Zeile des Gedichts; eine Leerzeile trennt zwei Strophen des Gedichts voneinander. Die erste Hälfte des Gedichts endet mit dem Halbsatz „Doch als sie zehn Lichtjahre gewandert neben sich hin“, am Ende der zweiten Zeile der dritten Strophe.

Diese Aufgabe kann mit einer Blockly-Umgebung bearbeitet werden, die man sich auch herunterladen kann, um sie auch ohne Internetzugang benutzen zu können:

Dokumentation der Ergebnisse:

Jedes Wort der erste Hälfte von Morgensterns Gedicht sollte je einmal als sogenanntes “Anfangswort” vom Programm verwendet werden und die schrittweise Berechnung klar dokumentiert werden, d.h. die Ausgabe des Programms sollte das jeweilige Anfangswort und das nach jedem Sprung erreichte Wort umfassen. Bei jedem Wort sollte seine Buchstabenzahl stehen (z.B. direkt nach dem Wort in Klammern).

Alle Ausgaben des Programms müssen vollständig für alle verwendeten Anfangswörter zusammen mit der berechneten Antwort auf die Frage, ob Martin Recht hat, in der Dokumentation der Aufgabe enthalten sein.

Junioraufgabe 2: Kacheln

Zu dieser Aufgabe gibt es die unvollständige Beispiellandschaft auf dem Aufgabenblatt als Karte in einer Textdatei (ohne Nummer) sowie fünf neue Textdateien (Nr. 1 bis 5) mit zu verarbeitenden Beispielkarten für unvollständige Landschaften (letzte Änderung: 31. August 2019):

Für jede Landschaft enthält die entsprechende Textdatei

  • in der ersten Zeile ihre vertikale Länge als Anzahl von Kachelreihen von oben nach unten und
  • in der zweiten Zeile ihre horizontale Breite als Anzahl von Kachelspalten von links nach rechts.

Für das Beispiel einer unvollständigen Landschaft auf dem Aufgabenblatt ist also die Länge "2" in der ersten Zeile und die Breite "2" in der zweiten Zeile der Textdatei. Danach folgt stets eine Leerzeile.

Die weiteren Zeilen der Textdatei enthalten die Landschaft als eine Karte von Kacheln. Je zwei aufeinander folgende Zeilen der Textdatei enthalten horizontal nebeneinander liegende Kacheln, gefolgt von jeweils einer die Kacheln vertikal trennenden Leerzeile oder dem Dateiende. Da jede Kachel aus 2x2 Quadraten besteht, umfasst die Landschaftskarte insgesamt doppelt so viele Quadrate in der Länge und Breite als Kacheln.

Jedes der vier Quadrate einer Kachel wird durch eines der Zeichen "0", "1" oder *" dargestellt. "0" steht für ein Quadrat mit Wasser und "1"  für ein Quadrat mit Land an den jeweiligen Außenseiten der Kachel. "*" repräsentiert je eines von vier Quadraten einer Kachel mit noch unbekannter Landschaft.

Innerhalb einer Textzeile folgt auf jedes Zeichen für ein Quadrat ein trennendes Leerzeichen. Die beiden horizontal benachbarten Quadrate zweier nebeneinander liegenden Kacheln sind jeweils durch drei Leerzeichen voneinander getrennt.

Als alternative Eingabedateien (zum Beispiel für die Blockly-Umgebung) stehen die obigen Textdateien auch in kompakter Form ohne Leerzeichen und Leerzeilen zur Verfügung:

Diese Aufgabe kann mit einer Blockly-Umgebung bearbeitet werden, die man sich auch herunterladen kann, um sie auch ohne Internetzugang benutzen zu können:

Dokumentation der Ergebnisse:

Jede der fünf neuen Karten sollte vom Programm verarbeitet und das jeweilige Ergebnis ausgegeben werden. Alle Ausgaben des Programms müssen in der Dokumentation der Aufgabe enthalten sein. Die Ausgabe des Programms soll als Text erfolgen; eine grafische Ausgabe wird nicht erwartet.

Um aus einer als Text vorliegenden Landschaft zusätzlich eine grafische Karte zu erzeugen, kann das folgende Javascript in einem ZIP-Archiv heruntergeladen werden, seine Anwendung ist jedoch optional:

Nach dem Entpacken dieses ZIP-Archivs in einen Ordner kann die Webseite index.html darin in einem modernen Webbrowser geöffnet werden. Hierdurch wird das JavaScript zum Erzeugen der SVG-/PNG-Bilder für eine grafische Landschaftskarte automatisch aktiviert. Nähere Bedienungshinweise finden sich auf der Webseite.

Außerdem gibt es hier in einem weiteren ZIP-Archiv die mit diesem JavaScript erzeugten grafischen Landschaften für alle oben genannten eins plus fünf Karten:

Aufgabe 1: Blumenbeet

Zu dieser Aufgabe gibt es das Beispiel vom Aufgabenblatt in einer Textdatei (ohne Nummer) sowie fünf neue Textdateien (Nr. 1 bis 5) mit zu verarbeitenden Beispielen von Kundenangaben (letzte Änderung: 10. September 2019):

Jede Textdatei enthält

  • in der ersten Zeile die Anzahl f der benötigten unterschiedlichen Farben (höchstmögliche Anzahl ist 7),
  • in der zweiten Zeile die Anzahl w der Kundenwünsche (höchstmögliche Anzahl ist 7) und
  • in jeder der folgenden Zeilen für den jeweiligen Kundenwunsch zwei durch ein Leerzeichen getrennte Farben in Kleinbuchstaben ohne Umlaut-Tremata (blau, gelb, gruen, orange, rosa, rot oder tuerkis) und die zusätzliche Bonuspunktzahl (1 bis 3) nach einem weiteren Leerzeichen.

Die Reihenfolge der Zeilen der Kundenwünsche sowie der beiden benachbarten Farben eines Kundenwunsches ist beliebig.

Dokumentation der Ergebnisse:

Jedes der fünf neuen Beispiele sollte vom Programm verarbeitet und das jeweilige Ergebnis ausgegeben werden. Alle Ausgaben des Programms müssen in der Dokumentation der Aufgabe enthalten sein. Die Ausgabe des Programms soll als Text erfolgen; eine grafische Ausgabe wird nicht erwartet.

Das dokumentierte Ergebnis für jedes Beispiel sollte zumindest die folgenden Angaben umfassen (weitere Angaben wie z.B. die Anzahl der berechneten Hochbeete sind gerne möglich):

  • (Größtmögliche) Bewertung des Hochbeetes als Summe von Bonuspunkten und
  • Liste der Blumenfarben, die z.B. die folgenden Positionen P1 bis P9 entlang der Bepflanzung des (besten) Hochbeetes in Rautenform von links nach rechts und von oben nach unten verwendet:

         P1    
      P2    P3
   P4    P5    P6
      P7    P8
         P9

Eine mögliches Ergebnis für das Beispiel auf dem Aufgabenblatt sieht mittels Verwendung der Positionen P1 bis P9 wie folgt aus:

Bewertung: 7
Hochbeet: P1:rot, P2:tuerkis, P3:rosa, P4:gelb, P5:blau, P6:orange, P7:gruen, P8:rot, P9:tuerkis.

Natürlich ist es auch alternativ möglich, die Liste der Blumenfarbe in Rautenform auszugeben, indem man den sieben möglichen Farben eindeutige Ziffern zuweist, z.B. blau 1, gelb 2, gruen 3, orange 4, rosa 5, rot 6 und tuerkis 7:

Bewertung: 7
Hochbeet:
    6    
  7   5
2   1   4
  3   6
    7 

Auch andere Darstellungen z.B. mit Farbbezeichnern statt Ziffern sind denkbar sowie z.B. auch einfach eine linksbündige Ausgabe.

Aufgabe 2: Nummernmerker

Zu dieser Aufgabe gibt es fünf neue zu verarbeitende Beispielnummern (Nr. 1 bis 5) (letzte Änderung: 31. August 2019):

Nummer1: 005480000005179734
Nummer2: 03495929533790154412660
Nummer3: 5319974879022725607620179
Nummer4: 9088761051699482789038331267
Nummer5: 011000000011000100111111101011

Alle fünf Nummern stehen auch in einer Textdatei mit einer Nummer pro Zeile zur Verfügung:

Dokumentation der Ergebnisse:

Jede der fünf neuen Beispielnummern sollte vom Programm verarbeitet und das jeweilige Ergebnis ausgegeben werden. Es genügt die Ausgabe einer Lösung, selbst wenn es in manchen Fällen mehrere gleichwertige Lösungen geben kann (z.B. lässt sich 3450421 als 3450-421 oder 34-504-21 aufteilen). Alle Ausgaben des Programms müssen in der Dokumentation der Aufgabe enthalten sein. Die Ausgabe des Programms soll als Text erfolgen; eine grafische Ausgabe wird nicht erwartet.

Aufgabe 3: Telepaartie

Zu dieser Aufgabe gibt es drei zu verarbeitende Beispiele (Nr. 1 bis 3) von Biberverteilungen für das erste Programm (letzte Änderung: 19. September 2019):

Verteilung1: (2, 4, 7)
Verteilung2: (3, 5, 7)
Verteilung3: (80, 64, 32)

Zudem muss laut Aufgabenstellung die Dokumentation der Aufgabe die Ausgabe des zweiten, erweiterten Programms beispielhaft sowohl für die Eingaben=10 als auch für die Eingaben=100 enthalten, ohne hierfür eine Biberverteilung einzulesen.

Dokumentation der Ergebnisse:

Jede Beispieleingabe sollte vom Programm verarbeitet und das jeweilige Ergebnis ausgegeben werden. Alle Ausgaben der beiden Programme müssen in der Dokumentation der Aufgabe enthalten sein. Die Ausgabe des Programms soll als Text erfolgen und sollte möglichst Zwischenergebnisse während der Programmberechnung enthalten.

Aufgabe 4: Urlaubsfahrt

Zu dieser Aufgabe gibt es fünf neue zu verarbeitende Beispieldateien (Nr. 1 bis 5) für die Tankplanung (letzte Änderung: 17. September 2019):

Jede Textdatei enthält

  • in der 1. Zeile den ganzzahligen Verbrauch v (in l) des Wohnmobils auf 100 km,
  • in der 2. Zeile die ganzzahlige Tankgröße g (in l) des Wohnmobils,
  • in der 3. Zeile die anfängliche ganzzahlige Tankfüllung f (in l) des Wohnmobils,
  • in der 4. Zeile die ganzzahlige Gesamtlänge l (in km) der zu fahrenden Strecke,
  • in der 5. Zeile die ganzzahlige Anzahl z von Tankstellen auf der Reiseroute und
  • in jeder der folgenden Zeilen für die jeweiligen Tankstelle ihre ganzzahlige Distanz d (in km) vom Startpunkt s der Reiseroute (nicht vom Endpunkt!) und ihr Dieselpreis p (in Cent/l) zwischen 100 und 199; die jeweilige Distanz d und der dazugehörige Dieselpreis p einer Tankstelle sind in der betreffenden Zeile durch mindestens drei Leerzeichen voneinander getrennt.

Es gibt keine zwei Tankstellen, die dieselbe Distanz d haben, d.h. die Distanz d identifiziert die jeweilige Tankstelle eindeutig, was für die Ausgabe des Programms nützlich ist.

Dokumentation der Ergebnisse:

Jedes der fünf neuen Beispiele sollte vom Programm verarbeitet und das jeweilige Ergebnis ausgegeben werden. Alle Ausgaben des Programms müssen in der Dokumentation der Aufgabe enthalten sein. Die Ausgabe des Programms soll als Text erfolgen; eine grafische Ausgabe wird nicht erwartet.

Das dokumentierte Ergebnis für jedes Beispiel sollte zumindest die folgenden Angaben umfassen (weitere Angaben wie z.B. das Gesamtvolumen der getankten Liter Diesel sind gerne möglich):

  • Anzahl der durchgeführten Tankstopps und eine
  • Liste der angefahrenen Tankstellen mit Angabe der jeweils getankten Liter Diesel; die jeweilige Tankstelle wird durch ihre Distanz d eindeutig identifiziert (d kann also als Nummer bzw. Namen der Tankstelle bei der Ausgabe verwendet werden).

Zur Veranschaulichung der Aufgabe hier noch eine Skizze zum ersten Beispiel:

Das Wohnmobil verbraucht 8 l/100 km und der Tank fasst 55 l; er ist anfangs mit 20 l gefüllt, die Strecke beträgt 1000 km und hat drei Tankstellen:

Am günstigsten ist es an der ersten Tankstelle nur so viel zu tanken, um gerade noch die zweite Tankstelle zu erreichen und dort so viel zu tanken, um bis zum Ziel zu kommen. An der zweiten Tankstelle weniger zu tanken und auch die dritte Tankstelle zu verwenden wäre preislich günstiger, verstieße aber gegen das Gebot, so selten wie möglich zu tanken.

Aufgabe 5: Rominos

Zu dieser Aufgabe gibt es keine Beispieldateien, sondern laut Aufgabenstellung muss die Dokumentation der Aufgabe die berechneten Anzahlen von n-Rominos für n von 4 bis 10 als Ausgabe des Programms enthalten und zudem die grafische Ausgabe des Programms für 4- und 5-Rominos (letzte Änderung: 31. August 2019).