IOI 2002
Trainingsbeispiele für die  Informatikolympiade
Zusammenstellung: Dr. Johann Fellner, BG/BRG Wörgl

Aufgabe 1 Man sieht den Wald vor lauter Bäumen nicht!

Man sieht den Wald vor lauter Bäumen nicht, wenn die Bäume im Forst systematisch in Reih und Glied stehen, denn von jedem Standort aus ist der Blick auf viele Bäume durch davorstehende Bäume versperrt!

In einem rechtwinkeligen Gitter von 20x20 Gitterpunkten steht auf einem Gitterpunkt der Förster; auf allen anderen Gitterpunkten stehen Bäume. Förster und Bäume seien punktförmg, haben also keine Ausdehnung. Ein Baum sei dann sichtbar, wenn der Sehstrahl von Gitterpunkt des Försters zum Gitterpunkt dieses Baumes durch keinen anderen Gitterpunkt verläuft.

a) Schreibe ein Programm, das bei Angabe eines beliebigen Gitterpunktes als Standort des Försters eine Landkarte der Gitterpunkte der sichtbaren Bäume ausgibt.

b) Suche Standorte, von denen aus möglichst viel Wald sichtbar ist. Wie viele gleichwertige dieser optimalen Standorte gibt es?

 

Aufgabe 2 Sortieren von Zahlen
Es sollen 1000 Zahlen zufällig ausgewählt und auf dem Bildschirm ausgegeben werden.

a) Schreibe ein Programm, das die Zahlen sortiert und ausgibt!
b) Das Programm soll auch die Sortierzeit angeben!
c) Kannst du den Sorteiralgorithmus verbessern? - Wie wirkt sich das auf die Zeit aus?

 

Aufgabe 3 Lottozahlen
Schreibe ein Programm, das 6 Zahlen (zufällig) aus dem Zahlenbereich 1 bis 45 zieht und nicht anzeigt; anschließend soll der Benutzer seine sechs Tipps eingeben können.

a) Das Programm soll anzeigen, wie viele Tipps richtig waren!
b) Das Programm soll die richtigen Tipps anzeigen!

 

Aufgabe 4 8 Damenproblem
Schreibe ein Programm, das alle Lösungen findet, 8 Damen auf einem Schachbrett so zu plazieren, dass keine die andere schlagen kann!

 

Aufgabe 5 Mobiltelefone IOI 2001, Tampere  -   Qualifikationsbeispiel
Problemstellung:

Nehmen wir an, dass die Basisstationen für die Mobiltelefone der vierten Generation in der Gegend um Tampere folgendermaßen funktionieren. Die Gegend ist in Planquadrate eingeteilt. Die Planquadrate bilden eine SxS Tabelle, in welcher die Reihen und die Spalten jeweils von 0 bis S-1 durchnummeriert sind. Jedes Planquadrat enthält eine Basisstation. Die Anzahl der aktiven Mobiltelefone innerhalb eines Planquadrates kann sich ändern, weil ein Gerät aus einem Quadrat in ein anderes überwechselt oder ein Handy ein- oder ausgeschaltet wird. Zu bestimmten Zeitpunkten meldet jede Basisstation die Änderung der Anzahl eingeschalteter Handys an die Hauptstation, zusammen mit den Reihen- und Spaltenangaben der Tabelle. Schreibe ein Programm, welches diese Berichte empfängt und Anfragen über die aktuelle Anzahl an eingeschalteten Mobiltelefonen in jeder rechteckförmigen Gegend beantwortet.

Eingabe und Ausgabe:

Die Eingabe wird vom Standardeingabegerät als ganze Zahl gelesen und die Antworten zu den Anfragen werden als ganze Zahlen in das Standardausgabegerät geschrieben. Die Eingabe ist folgendermaßen kodiert. Jede Eingabe steht in einer einzelnen Zeile und besteht aus einem ganzzahligen Befehl und einer gewissen Anzahl an ganzzahligen Parametern gemäß der folgenden Tabelle:

Befehl Parameter Bedeutung
0 S Eine Tabelle der Größe SxS ist zu initialisieren; jede Zelle enthält den Wert 0. Dieser Befehl wird nur einmal gegeben und ist auch der erste Befehl.
1 X Y A Addiere A zur Anzahl eingeschalteter Telefone im Planquadrat (X,Y). A kann positiv oder negativ sein.
2 L B R T Erfrage die aktuelle Gesamtzahl an eingeschalteten Mobiltelefonen in den Planquadraten (X,Y), wobei gilt: L≤X≤R, B≤Y≤T.
3
Beende das Programm. Dieser Befehl wird nur einmal gegeben und ist auch der letzte Befehl.

Die Werte bleiben immer in den vorgegebenen Grenzen, sodass keine Notwendigkeit besteht, dies zu überprüfen. Insbesondere wenn A negativ ist, kann vorausgesetzt werden, dass der Zellenwert nicht unter 0 fällt. Die Indizierung beginnt bei 0, z. B. für eine Tabelle 4 x 4 ergibt dies 0 ≤ X ≤ 3 und 0 ≤ Y ≤ 3.
Dein Programm darf keine Antwort geben, außer beim Befehl 2. Wenn der Befehl 2 ist, dann soll dein Programm die Anfrage beantworten, indem es die Antwort als eine einzige ganze Zahl in eine einzige Zeile der Standardausgabe schreibt.

Programmiertechnische Hinweise bzw. Beispiel-Eingaben