36. Bundeswettbewerb

Material zu den Aufgaben der 1. Runde

Hier stehen die Materialen für die erste Runde des 36. BwInf zum Download bereit.

Wer will, findet alle Materialien auch in einem Git-Repository unter: https://git.bwinf.de/bwinf/bwinf36-runde1.

Vorlagen

Hier findet ihr zwei Vorlagen, die ihr für eure Dokumentation verwenden könnt (aber nicht müsst).

  • Eine Vorlage im OpenDocument-Format (ODT; LibreOffice) und
  • eine Vorlage für LaTeX.

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

Alle Vorlagen können auch in einem Git-Repository gefunden werden: https://git.bwinf.de/bwinf/vorlagen.

Die Team-ID findet ihr nach der Anmeldung im PMS auf der Seite "Team". Bei Team / Name kann entweder der Team-Name oder euer eigener Name eingetragen werden.

Junioraufgabe 1: Bücherregal

Zu dieser Aufgabe gibt es sechs Beispieleingaben, die jeweils in einer Textdatei enthalten sind.

Jede Beispieldatei enthält:

  • in der ersten Zeile die Anzahl der Deko-Figuren,
  • in der zweiten Zeile die Anzahl der aufzustellenden Bücher
  • und in den folgenden Zeilen jeweils die Höhe eines Buches.

Die Höhen der Bücher sind allerdings in mm angegeben, nicht in cm.

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

Junioraufgabe 2: Wintervorrat

Auch zu dieser Aufgabe gibt es sechs Dateien mit Beispieleingaben.

Jede Datei enthält

  • in der ersten Zeile zwei Zahlen, nämlich Breite und Höhe des Rechteckwaldes,
  • in der zweiten Zeile die Anzahl der Vögel und
  • in jeder der folgenden Zeilen die Angaben zu einem Vogel: das Startfeld (angegeben sind dessen x- und y-Koordinaten, also Spalte und Zeile des Startfeldes), die Startminute und die Flugrichtung (W, O, N oder S).

Die erste Koordinate ist die x-Koordinate (Ost-West) und die zweite Koordinate ist die y-Koordinate (Nord-Süd). Das Feld mit den Koordinaten 1 1 liegt in der süd-westlichen Ecke. (Vgl. das Bild in der Aufgabenstellung.)

Die Datei wintervorrat1.txt beschreibt das Beispiel aus der Aufgabenstellung.  Eine weitere Datei (wintervorrat1-ausgabe.txt) zeigt, wie eine Ausgabe von sicheren und absolut sicheren Feldern sowie der sicheren Zeiträume aussehen könnte.

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

Aufgabe 1: Zimmerbelegung

Bei dieser Aufgabe enthält jede Datei mit Beispieleingaben die Wunschlisten mehrerer Schülerinnen.  Jede Wunschliste wird in drei Zeilen beschrieben:

  • In der ersten Zeile steht der Name der Schülerin.
  • Die zweite Zeile enthält die Positivliste:  Auf ein + folgen (evtl. null) Namen anderer Schülerinnen.
  • Die dritte Zeile enthält die Negativliste:  Auf ein - folgen (evtl. null) Namen anderer Schülerinnen.

Zwei Wunschlisten sind durch eine leere Zeile voneinander getrennt.

Die Dateien zimmerbelegung1.txt und zimmerbelegung2.txt beschreiben die Beispiele aus der Aufgabenstellung.

Eine Zimmerbelegung, die alle Wünsche erfüllt, kann in eine Textdatei ausgegeben werden. Eine solche Ausgabedatei könnte in jeder Zeile die Namen der Schülerinnen enthalten, die sich in der Zimmerbelegung ein Zimmer teilen.

Aufgabe 2: Schwimmbad

Beispiel 1:

Eine Abiturklasse mit 26 Schülerinnen und Schülern und einer Lehrerin wollen an einen Wochentag das Schwimmbad besuchen.  Sie haben drei Gutscheine und wollen eigentlich an einem beliebigen Tag in den Ferien gehen.  Wenn sie aber dadurch mindestens €5 sparen können, würden sie den Besuch auf die Schulzeit verschieben, der dann aber am Wochenende stattfinden müsste.

Beispiel 2:

Die Großfamilie Stutzenberg besteht aus Anton und Gerda, die eine Tochter Amalie haben.  Diese ist mit Gerhard verheiratet und hat mit ihm die fünf Kinder Bobo (3), Zoe (7), Bibi (10), Josefine (14) und Josef (17). Außerdem bringt Josef noch seine Freundin Miri (15) mit.  Sie möchten die Eintrittspreise für Besuche an Wochentagen und am Wochenende herausfinden, aber nur während der Ferienzeit.

Beispiel 3:

Zwei Kegelvereine mit 14 beziehungsweise 18 volljährigen Mitgliedern haben zusammen zwei Gutscheine.  Sie möchten eigentlich an zwei verschiedenen Wochenenden (beide nicht in den Ferien) das Schwimmbad heimsuchen.  Wieviel können sie sparen, wenn sie stattdessen zusammen gehen?

Aufgabe 3: Dreiecke zählen

Bei dieser Aufgabe besteht eine Beispieleingabe aus einer Menge an Strecken.

Die Dateien sehen jeweils so aus:

  • In der ersten Zeile steht die Anzahl der Strecken.
  • In jeder folgenden Zeile sind die Endpunkte der Strecken angegeben. Jede Zeile enthält also
    • die x-Koordinate von Endpunkt 1
    • die y-Koordinate von Endpunkt 1
    • die x-Koordinate von Endpunkt 2
    • die y-Koordinate von Endpunkt 2

Die Koordinatenwerte sind als Gleitkommazahlen (float) angegeben.

27.9.2017: Wegen eines inhaltlichen Problems wurde die Datei dreiecke3.txt ausgetauscht. In der neuen Datei sind 10 Strecken angegeben, in der alten waren es 9.

Die Aufgabenstellung fordert, dass dein Programm Dreiecke zählt.  Als Ausgabe genügt also jeweils eine Zahl.  Es ist aber besser, wenn dein Programm auch die gefundenen Dreiecke ausgibt; dann ist es leichter, das Ergebnis zu überprüfen.  Eine grafische Ausgabe ist sicher besonders überzeugend, aber eine Textdatei ist auch gut.  Eine solche Ausgabedatei könnte in der ersten Zeile die Anzahl der gefundenen Dreiecke enthalten und in jeder der folgenden Zeilen die (x- und y-) Koordinaten der Eckpunkte des Dreiecks, insgesamt also sechs Zahlen.  Üblicherweise gibt man die Eckpunkte eines Dreiecks gegen den Uhrzeigersinn an, aber das ist natürlich nicht entscheidend.

Aufgabe 4: Auto-Scrabble

Hier gibt es zunächst eine Datei mit der Liste der Städte- bzw. Kreis-Kürzel, die auf deutschen Kfz-Kennzeichen stehen können (kuerzelliste.txt).  Jedes Kürzel steht in einer eigenen Zeile dieser Datei.

Außerdem gibt es eine Eingabedatei, die in den Teilaufgaben 3 und 4 verwendet werden kann (autoscrabble.txt). Sie enthält in jeder Zeile ein Wort, für das überprüft werden soll, ob es aus Kfz-Kennzeichen gebildet werden kann.