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.