43. Bundeswettbewerb Informatik

Zu dieser Aufgabe gibt es 6 Beispieleingaben:

• schwierigkeiten0.txt
• schwierigkeiten1.txt
• schwierigkeiten2.txt
• schwierigkeiten3.txt
• schwierigkeiten4.txt
• schwierigkeiten5.txt

Jede Datei ist so aufgebaut:

• 1. Zeile: 3 ganze positive Zahlen n, m und k.
  • n : Anzahl der Klausuren.
  • m : Gesamtanzahl an Aufgaben.
  • k : Anzahl an Aufgaben für welche eine gute Anordnung gefunden werden soll.
• Folgende n Zeilen: Abstufungen der alten Klausuren. Jede Zeile beschreibt eine Klausur und hat die Form a₁ < a₂ < ..., wobei jedes a_i eine Aufgabe beschreibt. Eine Klausur hat mindestens 2 und maximal m Aufgaben.
• Die Aufgaben werden durch die ersten m Buchstaben des Alphabets von A, B, ... bezeichnet.
• Die letzte Zeile enthält die k Aufgaben, für die eine gute Anordnung gefunden werden soll.

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

Hier eine Bespieleingabe:

2 5 3
B < A < D < E
C < D < E
A E C

In diesem Beispiel gibt es zwei alte Klausuren mit fünf verschiedenen Aufgaben: A, B, C, D und E. Es soll für drei der Aufgaben eine neue Anordnung gefunden werden. In der 2. Zeile steht die Schwierigkeitsabstufung der ersten Altklausur. B ist leichter als A ist leichter als D ist leichter als E. In der 3. Zeile die Abstufung der 2. Altklausur. Hier ist C leichter als D und D leichter als E. Die letzte Zeile gibt an, dass für die Aufgaben A, E und C eine neue Anordnung gefunden werden soll.

Für diese Aufgabe gibt es keine gestellten Einlesedateien für die Arbeit mit Java, denn hier ist das Einlesen Teil der Aufgabe und ändert das weitere Vorgehen. Du kannst natürlich die Einlesedateien anderer Aufgaben verwenden und entsprechend abwandeln.

Zu dieser Aufgabe gibt es 7 Beispieleingaben:

• wandern1.txt
• wandern2.txt
• wandern3.txt
• wandern4.txt
• wandern5.txt
• wandern6.txt
• wandern7.txt

Jede Datei enthält Streckenwünsche und ist so aufgebaut:

• 1. Zeile: Anzahl n der Personen mit Streckenwünschen.
• In den folgenden n Zeilen ist jeweils die kürzeste und längste gewünschte Strecke aus Sicht einer Person angegeben (in Metern). Die angegebenen minimalen und maximalen Streckenlängen sind inklusive, also gilt [x₁, x₂].

Hier ist eine Beispieleingabe:

3
500 1000
100 200
100 600

In diesem Beispiel gibt es insgesamt drei Streckenwünsche. Person 1 möchte gern mindestens 500m und maximal 1000m laufen. Sollte die angebotene Strecke genau 500m oder 1000m betragen, würde sie auch mitkommen. Analog wünscht sich Person 2 eine Strecke zwischen 100m und 200m und Person 3 zwischen 100m und 600m.

Für die Dateien wandern6.txt und wandern7.txt benötigt dein Programm eventuell mehr Zeit als für die anderen Eingaben. Versuche, diese Zeit zu minimieren.

Einlesedateien für die Arbeit mit Java: A3_EinlesenJava.

Zu dieser Aufgabe gibt es 10 Beispieleingaben:

• labyrinthe0.txt
• labyrinthe1.txt
• labyrinthe2.txt
• labyrinthe3.txt
• labyrinthe4.txt
• labyrinthe5.txt
• labyrinthe6.txt
• labyrinthe7.txt
• labyrinthe8.txt
• labyrinthe9.txt

Jede Datei beschreibt die beiden Labyrinthe. In der 1. Zeile werden Breite n und Höhe m der beiden Labyrinthe angegeben. Danach werden die Labyrinthe nacheinander jeweils so definiert:

• m Zeilen mit je n-1 Einträgen: Für jede Labyrinthzeile wird für jedes Feld angegeben, ob rechts davon eine vertikale Wand ist oder nicht. Eine 1 steht für eine Wand, eine 0 für keine Wand.
• m-1 Zeilen mit je n Einträgen: Für jede Labyrinthzeile wird für jedes Feld angegeben, ob unterhalb des Feldes eine horizontale Wand ist oder nicht. Eine 1 steht für eine Wand, eine 0 für keine Wand.
• 1 Zeile: Anzahl g der Gruben.
• g Zeilen: Pro Zeile die Koordinate einer Gruben im Labyrinth im Format xy. Die Koordinate (0,0) entspricht der Startposition, also der oberen linken Eckposition. Gibt es keine Gruben, folgen direkt die Angaben für das zweite Labyrinth beginnend bei den Angaben zu den vertikalen Wänden.

Die Datei labyrinthe0.txt entspricht dem Beispiel aus der Aufgabenstellung und wird hier erläutert. Die Zeilennummerierung ist in den Dateien nicht enthalten und dient der besseren Verständlichkeit der Beschreibung. Für eine visuelle Unterstützung bietet es sich an, die Aufgabenstellung vorliegen zu haben.

 1: 3 3
 2: 1 0
 3: 1 1
 4: 0 1
 5: 0 0 0
 6: 0 0 0
 7: 0
 8: 1 0
 9: 0 1
10: 0 0
11: 0 0 0
12: 1 1 0
13: 1
14: 0 2

Es handelt sich um zwei Labyrinthe mit den Maßen 3 x 3. Zeile 2 bis 4 beschreiben die vertikalen Wände in den einzelnen Labyrinthzeilen des ersten Labyrinths. Beispielsweise ist in der ersten Labyrinthzeile zwischen dem ersten und zweiten Feld eine Wand, zwischen dem zweiten und dritten Feld nicht. Zeile 5 und 6 beschreiben die horizontalen Wände des ersten Labyrinths. In diesem Labyrinth sind keine horizontalen Wände vorhanden. Die 0 in Zeile 7 sagt aus, dass es keine Gruben gibt. Damit ist die Beschreibung des ersten Labyrinths abgeschlossen.
Es folgen in Zeile 8 bis 10 direkt die Angaben für die vertikalen Wände des zweiten Labyrinths. Aus Zeile 12 ist ersichtlich, dass an Position eins und zwei unterhalb der zweiten Labyrinthzeile im zweiten Labyrinth Wände existieren. Zeile 13 gibt an, dass es im zweiten Labyrinth eine Grube gibt. Sie ist laut Zeile 14 an Position (0,2).

Zu dieser Aufgabe gibt es 14 Beispieleingaben:

• konfetti00.txt
• konfetti01.txt
• konfetti02.txt
• konfetti03.txt
• konfetti04.txt
• konfetti05.txt
• konfetti06.txt
• konfetti07.txt
• konfetti08.txt
• konfetti09.txt
• konfetti10.txt
• konfetti11.txt
• konfetti12.txt
• konfetti13.txt

Jede Datei beschreibt einen zerschnittenen Aushang und ist so aufgebaut:

• 1. Zeile: Zwei ganze Zahlen r und c, sowie ein Zeichen t:
  • r ist die Anzahl der Personen = Zeilen des Aushangs.
  • c ist die Anzahl der Termine = Spalten des Aushangs.
  • t gibt an, ob Annas Zeile in dem Beispiel bekannt (y) oder unbekannt (n) ist.
• Folgende r Zeilen: Jeweils c durch Leerzeichen getrennte Zeichen. y steht für einen möglichen, n für einen unmöglichen Zeitslot, ? für ein unleserliches Zeichen.
• Wenn Annas Zeile nicht bekannt ist, ist die Beschreibung des Aushangs abgeschlossen
• Ist Annas Zeile bekannt, folgt eine letzte Zeile: Annas richtig geordnete Terminangaben wieder mit möglichen (y) und unmöglichen (n) Zeitslots, sowie ggf. ? bei unleserlichen Zeichen. Diese Angabe entspricht der ersten Zeile der r Zeilen, allerdings mit der korrekten Anordnung der Spalten.

Hier eine Erklärung zu konfetti00.txt, das Beispiel vom Aufgabenblatt zu Teilaufgabe d :

4 4 n
n y n n
y y ? n
y n n y
y n y n

In diesem Beispiel gibt es vier Personen und vier mögliche Zeitslots. Anna weiß ihre eigenen Angaben nicht mehr. Die erste Person hat an drei von vier Zeitslots keine Zeit. Die zweite Person hat an zwei Zeitslots sicher Zeit, eine Angabe ist unleserlich und einmal hat sie keine Zeit. Person drei und vier können jeweils an zwei von vier Zeitslots.

Die hohe Anzahl an Beispielen resultiert aus den Teilaufgaben dieser Aufgabe. Wir erwarten in der Dokumentation folgende Ausgaben bei den Teilaufgaben:
Teilaufgabe a & b:konfetti01.txt - konfetti05.txt
Teilaufgabe c:konfetti06.txt & konfetti07.txt
Teilaufgabe c & d:konfetti08.txt & konfetti12.txt
Teilaufgabe d:konfetti09.txt - konfetti11.txt und konfetti00.txt
Teilaufgabe e:konfetti13.txt und alle bisher “nicht lösbaren” Beispiele.

Ist ein Beispiel lösbar, wird eine zulässige Anordnung als Ausgabe erwartet, ansonsten ein Hinweis auf Unlösbarkeit.