Erste Runde SOI 2016

Übersicht

AufgabeSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
cablecar (0/100)0/100/200/300/40
gotthard (0/100)0/200/200/400/20
matryoshka (0/100)0/100/200/200/200/30
waterslide (0/100)0/200/200/200/40
salesman (0/100)0/200/100/100/60
racing (0/100)0/00/200/300/50

Seilbahn

Maus Stofl fährt leidenschaftlich gerne Seilbahn. Um auch zuhause in den Genuss einer Seilbahn zu kommen, hat er sich eine Modellseilbahn gekauft. Die Sicht aus einer Seilbahn lässt sich optimal geniessen, wenn die Seilbahn gleichmässig fährt. Dies ist genau dann der Fall, wenn an jeder Stelle der Seilbahn die Steigung dieselbe ist – ansonsten würde die Seilbahn zu schwingen beginnen und das will Stofl vermeiden. Er hat dazu die Höhen seiner Masten gemessen und braucht deine Hilfe, um damit die Seilbahn zu bauen. Alle Masten werden auf dem Boden, der überall die selbe Höhe hat, aufgestellt. Die Tal- und Bergstation kann Stofl auf beliebiger Höhe anbringen. Nachdem er die Masten aufgestellt hat, wird er sie so anbringen, dass die Steigung dieselbe wie bei den Masten ist.

Teilaufgabe 1: Kurze Seilbahn (10 Punkte)

Die Seilbahn wurde von Stofl bereits aufgestellt. Sie hat genau 3 Masten, die zueinander im Abstand 1 stehen. Hilf Stofl zu entscheiden, ob man die Sicht geniessen kann oder nicht.

Stofl möchte nicht nur eine Modellseilbahn bauen, sondern T. Jede dieser Seilbahnen hat seine eigenen Masten und ist unabhängig von den anderen.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Seilbahnen die Stofl bauen möchte.

Für jede dieser Seilbahnen folgt dann eine Beschreibung der Masten, die folgendermassen aufgebaut ist: Auf der ersten Zeile steht eine Zahl N, die Anzahl der Masten (immer 3) und auf der zweiten Zeile stehen N ganze Zahlen, die Höhen hi der Masten.

Ausgabe

Gib für die t-te der T Seilbahnen “Case #t: yes” aus, falls man die Sicht optimal geniessen kann, ansonsten gib “Case #t: no” aus.

Limits

  • Für die Anzahl Testfälle gilt T = 100.
  • Für die Anzahl Masten gilt N = 3.
  • Für die Höhen der Masten gilt 1 ≤ hi ≤ 109.

Beispiel

sample

Beispieleingabe für Teilaufgabe 1.

Eingabe:

2
3
3 5 7
3
3 5 10

Ausgabe:

Case #1: yes
Case #2: no

Bemerkung:

Case #1: Bei der ersten Seilbahn ist die Steigung vom ersten zum zweiten Masten 2 und vom zweiten zum dritten ebenfalls. Die Steigung ändert sich nicht. Deshalb kann man die Sicht aus der Seilbahn geniessen.

Case #2: Bei der zweiten Seilbahn ist die Steigung vom ersten zum zweiten Masten ebenfalls 2, jedoch die Steigung vom zweiten zum 3ten Masten 5. Da sich die Steigung ändert, kann die Sicht nicht optimal geniessen.

Teilaufgabe 2: Lange Seilbahn (20 Punkte)

Während du die erste Teilaufgabe gelöst hast, hat Maus Stofl sich ein Erweiterungsset für seine Seilbahn gekauft. Mit diesem Set hat Stofl nun 10‘000 Masten. Er wählt N davon aus und stellt sie wie in Teilaufgabe 1 auf. Hilf Stofl erneut herauszufinden, ob man die Sicht aus der Seilbahn geniessen kann.

Eingabe

Wie in Teilaufgabe 1, aber es kann N ≠ 3 gelten.

Ausgabe

Wie in Teilaufgabe 1.

Limits

  • Für die Anzahl Testfälle gilt T = 100.
  • Für die Anzahl Masten gilt 2 ≤ N ≤ 10 000.
  • Für die Höhen der Masten gilt 1 ≤ hi ≤ 109.

Beispiel

Eingabe:

3
8
1 2 3 4 5 6 7 9
2
1 5
4
20 15 10 5

Ausgabe:

Case #1: no
Case #2: yes
Case #3: yes

Teilaufgabe 3: Teilstück finden (30 Punkte)

Maus Stofl hat erneut N Masten im selben Abstand aufgestellt. Da Stofl viel Platz hat, hat er eine lange Reihe gemacht. Er möchte nun das längste Stück dieser Reihe finden, mit dem sich eine Seilbahn bauen lässt, aus der man die Sicht optimal geniessen kann. Da Stofl faul ist, möchte er keine Masten bewegen. Deshalb sollte das Stück zusammenhängend sein. Hilf Stofl das längste zusammenhängende Stück zu finden.

Eingabe

Wie in Teilaufgabe 2.

Ausgabe

Gib für die t-te der T Seilbahnen “Case #t:” aus, gefolgt von einer einzelnen Zahl D, der Länge des längsten zusammenhängenden Stücks.

Limits

  • Für die Anzahl Testfälle gilt T = 100.
  • Für die Anzahl Masten gilt 2 ≤ N ≤ 105.
  • Für die Höhen der Masten gilt 1 ≤ hi ≤ 109.

Beispiel

Eingabe:

2
10
2 3 10 11 12 13 14 15 16 500
5
3 20 25 30 35

Ausgabe:

Case #1: 7
Case #2: 4

Bemerkung:

Case #1: Stofl wählt das Stück zwischen den Masten der Höhen 10 und 16.

Case #2: Das längste Stück liegt zwischen den Masten der Höhe 20 und 35.

Teilaufgabe 4: Masten entfernen (40 Punkte)

Nachdem Stofl lange genug mit der Seilbahn aus Teilaufgabe 3 gespielt hat, möchte er eine neue bauen. Er hat wieder alle Masten in einer Reihe aufgestellt. Diesmal ist er aber dazu bereit, Masten zu entfernen. Nachdem er einige Masten entfernt hat, rückt er die verbleibenden Masten zusammen, bis sie wieder gleichen Abstand haben. Hilf Stofl so wenig Masten wie möglich zu entfernen, so dass die verbleibenden Masten eine möglichst lange Seilbahn bilden, aus der man die Sicht optimal geniessen kann.

Eingabe

Wie in Teilaufgabe 3.

Ausgabe

Gib für die t-te der T Seilbahnen “Case #t:” aus, gefolgt von einer einzelnen Zahl R, der minimalen Anzahl Masten, die Maus Stofl entfernen muss, damit die Sicht aus der Seilbahn optimal ist.

Limits

  • Für die Anzahl Testfälle gilt T = 100.
  • Für die Anzahl Masten gilt 2 ≤ N ≤ 1000.
  • Für die Höhen der Masten gilt 1 ≤ hi ≤ 109.

Beispiel

Eingabe:

2
5
100 200 300 400 500
7
22 24 25 26 100 28 30

Ausgabe:

Case #1: 0
Case #2: 2

Bemerkung:

Case #1: Stofl muss keinen Masten entfernen, da sie bereits eine Seilbahn mit optimaler Sicht bilden.

Case #2: Stofl entfernt die Masten mit Höhe 25 und 100.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Gotthard-Tunnel

Ende Dezember 2016 soll der neue Gotthard-Basistunnel fertiggestellt werden. Ein Bauinspektor besichtigt nun den Tunnel und stellt fest, dass der Boden und die Decke uneben gebaut wurden. Die Unterschiede können sogar so gross sein, dass man nicht durch den Tunnel sieht (d.h. es gibt keine horizontale Gerade durch den Tunnel, die nie den Boden oder die Decke schneidet bzw. berührt). Der Bauinspektor kann mittels spezieller Geräte die Sichtlinie an seiner Position auf einer beliebigen Höhe messen (d.h. die Höhe des Bodens und die Grösse des Inspektors spielen keine Rolle), sie muss jedoch horizontal verlaufen. Auf beiden Seiten des Tunnels befindet sich ein geschlossenes Tor, das über die gesamte Höhe des Tunnels geht und die Sicht blockiert. Die Tore sind direkt vor der ersten bzw. nach der letzten gegebenen Position.

Der Bauinspektor möchte nun die Unebenheiten analysieren und wo nötig bereinigen. Dazu hat er sich die folgenden vier Teilaufgaben vorgenommen. Hilf ihm, diese zu lösen!

Eingabe

Die Eingabe hat für alle Teilaufgaben das gleiche Format: Auf der ersten Zeile steht eine Zahl T, die Anzahl Testfälle.

Danach folgen für jeden Testfall drei Zeilen:

  • Auf der ersten Zeile steht eine natürliche Zahl, die Länge des Tunnels (N) in Metern.
  • Es folgt eine Zeile mit N Zahlen, jeweils die Höhe über Meer der Decke ci für die Position i.
  • Es folgt eine Zeile mit N Zahlen, jeweils die Höhe über Meer des Bodens fi für die Position i.

Die Position i = 1 ist die nördlichste Position, i = N die südlichste.

Ausgabe

In allen Teilaufgaben ist für jeden Testfall als Resultat eine bestimmte Distanz D gesucht. Gib für jeden Testfall eine Zeile im Format “Case #i: D” aus, wobei i der Nummer des Testcases (für den ersten Testcase ist i = 1) entspricht und D der gesuchten Distanz.

Teilaufgabe 1: Stationär (20 Punkte)

Der Bauinspektor steht beim Tor im Nordportal und möchte wissen, wie weit er in den Tunnel hinein sieht.

Limits

  • T = 100
  • 1 ≤ N ≤ 103
  • 0 ≤ fi < ci ≤ 109

Beispiele

Eingabe:

1
4
7 9 6 8
6 2 1 5

Ausgabe:

Case #1: 2

Bemerkung:

Da die Sichtlinie weder Boden noch Decke berühren darf, sieht der Bauinspektor nur 2 Meter in den Tunnel, die Decke an Position 3 verdeckt die Sicht.

Teilaufgabe 2: Kurzer Spaziergang (20 Punkte)

Der Bauinspektor läuft durch den Tunnel und möchte wissen, was die maximale Distanz ist, die er während dem Spaziergang sieht.

Limits

  • T = 100
  • 1 ≤ N ≤ 103
  • 0 ≤ fi < ci ≤ 109

Beispiele

Eingabe:

1
7
7 9 6 8 7 9 8
6 2 1 5 4 3 7

Ausgabe:

Case #1: 5

Teilaufgabe 3: Langer Spaziergang (40 Punkte)

Selbe Aufgabenstellung wie Teilaufgabe 2, aber der Tunnel kann nun wesentlich länger sein.

Limits

  • T = 100
  • 1 ≤ N ≤ 106
  • 0 ≤ fi < ci ≤ 109

Beispiele

Eingabe:

1
15
7 9 6 8 7 9 8 7 9 6 8 7 9 8 7
6 2 1 5 4 3 6 6 2 1 5 4 3 6 6

Ausgabe:

Case #1: 6

Teilaufgabe 4: Tunnelräumung (20 Punkte)

Der Tunnel soll soweit verbessert werden, dass man wieder von einem Ende zum anderen Ende sieht und somit die Schienen flach verlegen kann. Dazu beginnt man von beiden Seiten her, zu weit in den Tunnel ragende Teile am Boden sowie an der Decke zu entfernen (Vertiefungen werden erst in einem späteren Schritt ausgebessert, für den wir uns im Moment nicht interessieren). Man will jedoch eine möglichst kleine horizontale Distanz zurücklegen, um die Kosten tief zu halten. Der Bauinspektor möchte nun wissen, wie weit die beiden Bautrupps mindestens gehen müssen (Summe der beiden Distanzen), bis wieder eine Sichtlinie existiert.

Limits

  • T = 100
  • 1 ≤ N ≤ 106
  • 0 ≤ fi < ci ≤ 1018

Beispiele

Eingabe:

2
15
8 7 6 8 9 5 8 7 4 6 8 9 7 8 7
6 2 3 4 1 2 1 3 1 2 5 3 5 6 4
9
8 7 5 6 8 9 4 8 7
6 4 3 4 5 1 2 1 2

Ausgabe:

Case #1: 8
Case #2: 5

Bemerkung:

Case #1: Aus dem Norden (links) muss der Bautrupp nur 1 Meter weit in den Tunnel, aus dem Süden (rechts) jedoch 7 Meter, was zusammen 8 Meter ergibt.

Case #2:: In diesem Fall muss nur vom Norden (links) her 5 Meter gearbeitet werden.


Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Matroschka

Maus Stofl hat von seinem russischen Freund Maus Dimitri Pakete mit verschiedenen Matroschkas geschenkt bekommen. Matroschkas sind aus Holz gefertigte und bunt bemalte, ineinander verschachtelbare, eiförmige russische Puppen.

sample

Matroshka-Serie

Da Dimitri nicht sehr ordentlich ist, sind Puppen verschiedener Ma­t­ro­sch­ka-Sets zusammengewürfelt. Deshalb können nicht in jedem Fall alle ineinander geschachtelt werden. Eine Puppe kann in eine andere geschachtelt werden, wenn ihre Höhe und Breite strikt kleiner ist.

Teilaufgabe 1: Ein Matroschka-Set (10 Punkte)

Dimitri hat die Matroschkas in T Pakete verpackt. Stofl packt die Pakete einzeln aus und versucht die Puppen paketweise ineinander zu schachteln. Schreib ein Programm, welches Stofl sagt, ob alle Puppen in einem Paket ineinander verschachtelt werden können.

Eingabe

Die erste Zeile enthält die Anzahl mit Ma­t­ro­sch­ka gefüllten Pakete T. Für jedes Paket werden drei Zeilen ausgegeben. Die erste Zeile enthält die Anzahl Puppen N. Die zweite enthält N Zahlen, die die jeweiligen Breiten W der Matroschkas beschreiben. Die dritte enthält N Zahlen, welche die dazugehörigen Höhen H angeben.

Ausgabe

Als Ausgabe wird für das i-te Paket die Ausgabe Case #i: erwartet, gefolgt von YES wenn sie verschachtelbar sind, beziehungsweise NO wenn keine Schachtelung möglich ist.

Limits

  • Für die Anzahl Pakete gilt T = 100.
  • Für die Anzahl Ma­t­ro­sch­ka pro Paket gilt N ≤ 1000.
  • Für die Höhe H und Breite W gilt 1 ≤ H, W ≤ 100000.

Beispiel

Eingabe:

2
3
1 2 3
1 2 3
3
1 2 3
1 3 2

Ausgabe:

Case #1: YES
Case #2: NO

Bemerkung:

Die Matroschkas aus Paket 1 mit den Grössen 1x1, 2x2 und 3x3 lassen sich alle ineinander verschachteln. Die Matroschkas aus Paket 2 mit den Grössen 1x1, 2x3 und 3x2 lassen sich nur teilweise verschachteln.

Teilaufgabe 2: Grösstes Ma­t­ro­sch­ka-Set (20 Punkte)

Da Stofl eine sehr neugierige Maus ist, stellt er sich die Frage, wie viele Puppen er wohl maximal ineinander schachteln kann. Wie zuvor möchte er dies paketweise untersuchen. Hilf Stofl, eine Antwort zu finden!

Eingabe

Wie in Teilaufgabe 1.

Ausgabe

Als Ausgabe wird die Paket-Nummer i und die maximale Anzahl von Puppen Z, welche ineinander geschachtelt werden können, in folgender Form erwartet: Case #i: Z.

Limits

  • Für die Anzahl Pakete gilt T = 100.
  • Für die Anzahl Ma­t­ro­sch­ka pro Paket gilt N ≤ 1000.
  • Für die Höhe H und Breite W gilt 1 ≤ H, W ≤ 10000.

Beispiel

Eingabe:

2
7
1 2 3 4 5 6 7
1 5 6 2 3 4 7
4
1 1 1 2
1 1 1 2

Ausgabe:

Case #1: 5
Case #2: 2

Teilaufgabe 3: Viele Puppen (20 Punkte)

Wenige Tage nach dem Paket erhält Stofl einen Brief von Dimitri. Darin bittet er Stofl um Hilfe. Dimitri hat auf dem Dachboden seiner Grossmutter noch viele weitere Matroschkas entdeckt. Er möchte nun ebenfalls wissen, wie viele Puppen er maximal ineinander schachteln kann. Dimitri vermutet aber, dass die Lösung von Teilaufgabe 2 zu langsam ist.

Eingabe

Wie in Teilaufgabe 1.

Ausgabe

Wie in Teilaufgabe 2.

Limits

  • Für die Anzahl Pakete gilt T = 100.
  • Für die Anzahl Ma­t­ro­sch­ka pro Paket gilt N ≤ 105.
  • Für die Höhe H und Breite W gilt 1 ≤ H, W ≤ 105.

Teilaufgabe 4: Gruppenfoto (20 Punkte)

Stofl freut sich sehr über die Matroschkas und möchte unbedingt Fotos von ihnen auf Instagram posten. Im Gegensatz zu Dimitri ist Stofl sehr ordentlich, so geht er beim Aufstellen der Matroschkas nach folgender Regel vor: Vor jeder Matroschka baut Stofl kleinere Matroschkas nebeneinander in einer Reihe auf. Die Höhe der Matroschkas in dieser Reihe ist kleiner als die dahinter stehende Matroschka und die gesamte Breite der Reihe ist kürzer als die Breite der Matroschka. Für jede Matroschka in dieser Reihe wiederholt Stofl dies.

Stofl fängt mit einer Matroschka an und fährt dann mit seiner Regel fort, bis er keine Matroschkas mehr hinstellen kann. Da Stofl viele Matroschkas derselben Grösse erhalten hat, kannst du annehmen, dass es sich bei der Eingabe um Matroschka-Typen handelt, die beliebig oft eingesetzt werden können. Auch hat genaues Messen der Grösse gezeigt, dass es keine zwei Matroschka-Typen gibt, die exakt gleich hoch oder gleich breit sind.

Eingabe

Wie in Teilaufgabe 1.

Ausgabe

Als Ausgabe wird die Foto-Nummer i und die maximale Anzahl von Puppen Z, welche auf dem Foto zu sehen sind, in folgender Form erwartet: Case #i: Z.

Limits

  • Für die Anzahl Fotos gilt T = 100.
  • Für die Anzahl Matroschka-Typen pro Foto gilt 1 ≤ N ≤ 1000.
  • Für die Höhe H und Breite W gilt 1 ≤ H, W ≤ 100.

Beispiel

sample

Beispiel 1

sample

Beispiel 2

sample

Beispiel 3

Eingabe:

3
7
2 3 4 6 8 10 11
2 5 6 1 3 4 9
2
1 100
1 2
4
14 3 4 5
14 3 4 5

Ausgabe:

Case #1: 8
Case #2: 100
Case #3: 8

Bemerkung:

Bei einer frontalen Fotographie sieht dies wie folgt aus:

Die grosse blaue 11x9 Matroschka stellt Stofl zuhinterst auf. Davor baut er eine Reihe von Matroschkas auf bestehend aus zwei 4x6 Matroschkas und einer 2x2 Matroschka und nützt somit die maximale gesamte Breite der Reihe aus. Vor jeder Matroschka in der roten Reihe baut Stofl nun wieder eine Reihe auf. Dies ist nur vor den beiden 4x6 Matroschkas möglich, da es keine Matroschka gibt die kleiner als 2x2 ist. Die neue, grüne Reihe besteht jeweils nur aus einer 3x5 Matroschka. Vor dieser wird wiederum eine Reihe bestehnd aus einer 2x2 Matroschka gebildet. Somit sind am Schluss 8 Matroschkas auf dem Foto.

Teilaufgabe 5: Gruppenfoto 2 (30 Punkte)

Dimitri, der Stofls Fotos entdeckt hat, möchte ihm einerseits beweisen, dass er auch ordentlich sein kann und andererseits auch zeigen, dass es noch viel grössere Matroschkas gibt. Dimitri macht ebenfalls Fotos und baut seine Matroschkas nach demselben Prinzip auf wie Stofl in Teilaufgabe 4. Wie wir schon bei Teilaufgabe 3 gesehen haben, ist Dimitri nicht sehr geduldig; auch hier wird wahrscheinlich eine Optimierung deines Programms nötig sein.

Eingabe

Wie in Teilaufgabe 1.

Ausgabe

Wie in Teilaufgabe 4.

Limits

  • Für die Anzahl Fotos gilt T = 100.
  • Für die Anzahl Matroschka-Typen pro Foto gilt 1 ≤ N ≤ 1000.
  • Für die Höhe H und Breite W gilt 1 ≤ H, W ≤ 100000.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Wasserrutschen

Maus Stofl rutscht gerne Wasserrutschen hinunter. Sein Lieblings-Vergnügungspark bietet ein grosses Netzwerk von Rutschen an. Die Rutschen verbinden N kleine Pools. An jedem Pool gibt es eine Leiter, welche zu einer bestimmten Anzahl weiterer Rutschen führt. Um Kollisionen auszuschliessen endet nur eine Rutsche an jedem Pool.

Maus Stofl beginnt in einem bestimmten Pool und hätte gerne so viel Spass wie er nur kann. Er hat am meisten Spass, wenn er soviele verschiedene Wasserrutschen in einer Reihe hinunterrutschen kann wie möglich, ohne je zu Fuss zwischen zwei Pools wechseln zu müssen. Kannst du ihm Helfen, so eine spassigste Folge von Rutschen zu finden? Stofl darf die gleiche Rutschbahn mehrfach benutzen, jedoch erhöht er dabei nicht seine Freude.

Teilaufgabe 1 (20 Punkte)

Hilf Stofl, die Anzahl der Rutschen auf einer spassigsten Folge zu finden, gegeben dass er von einem bestimmten Pool aus starten möchte.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält die Zahl T, welche die Anzahl Testfälle angibt. Es folgen T Testfälle.

Ein einzelner Testfall fängt mit einer Zeile N an, auf die eine weitere Zeile mit S folgt (1 ≤ S ≤ N). Die Pools sind von 1 bis N durchnummeriert. N ist die gesamte Anzahl Pools und S gibt den Anfangspool an. N Zeilen folgen, welche die Pools der Reihe nach beschreiben. Jeder dieser Zeilen enthält die Anzahl Pools, welche von diesem Pool aus erreicht werden können, gefolgt von den Nummern dieser Pools. Während jeder Pool eine beliebige Anzahl ausgehender Rutschen haben kann ist es garantiert, dass nur eine Rutsche zu ihm führt.

Ausgabe

Für jeden Testfall sollst du “Case #t:” ausgeben, wobei t die Nummer des Testfalls ist, von 1 an gezählt. Auf der selben Zeile soll eine einzelne Zahl folgen: Die maximale Anzahl verschiedener Rutschen die Stofl besuchen kann ohne zu Fuss zwischen zwei Pools zu wechseln.

Beschränkungen

  • Es gilt 1 ≤ N ≤ 1 000.

Beispiel

sample

Erster Testfall der Beispieleingabe visualisiert.

Eingabe:

3
6
1
2 2 5
2 1 3
0
0
2 4 6
0
6
3
1 2
1 3
1 4
1 5
1 6
1 1
6
2
1 1
1 2
1 4
2 3 5
1 6
0

Ausgabe:

Case #1: 4
Case #2: 6
Case #3: 1

Bemerkung:

Case #1: Die beste Folge von Pools ist entweder 1 → 2 → 1 → 5 → 6 oder auch 1 → 2 → 1 → 5 → 4. Merke, dass Stofl in diesem Beispiel denselben Pool zweimal besuchen muss, um am meisten Spass zu haben.

Case #2: Die beste Folge von Pools ist 4 → 3 → 4 → 5 → 6 → 1 → 2. Stofl kann jeden Pool besuchen, da sie in einer Schleife verbunden sind.

Case #3: Die beste Folge von Pools ist 2 → 2. In diesem Beispiel started Stofl in einem Pool, der nur mit sich selbst verbunden ist. Daher kann er keinen anderen Pool erreichen.

Teilaufgabe 2 (20 Punkte)

Der Anfangspool kann nun von Stofl selbst ausgewählt werden. Deine Aufgabe ist es, die Anzahl verschiedener Rutschen zu finden, die zu einer spassigsten Folge gehören können, wenn diese in einem beliebigen der N Pools beginnt. In der Eingabe wird S deshalb nun weggelassen.

Beispiel

Eingabe:

2
6
2 2 5
2 1 3
0
0
2 4 6
0
6
1 1
1 2
1 4
2 3 5
1 6
0

Ausgabe:

Case #1: 4
Case #2: 4

Bemerkung:

Case #1: Die beste Folge von Pools ist entweder 1 → 2 → 1 → 5 → 6 oder 1 → 2 → 1 → 5 → 4.

Case #2: Stofl kann die Schleifen bei Pool 1 und 2 vermeiden, und wählt stattdessen die spassige Fahrt von Pool 3 nach 6.

Beschränkungen

  • Es gilt 1 ≤ N ≤ 1 000.

Teilaufgabe 3 (20 Punkte)

Um sogar noch mehr Spass zu haben hat sich Stofl entschlossen einen noch grösseren Vergnügungspark zu besuchen, welcher fast eine Million unterschiedliche Pools anbietet. Stofl darf sich den Anfangspool wieder selber aussuchen.

Beschränkungen

  • Es gilt 1 ≤ N ≤ 500 000.

Teilaufgabe 4 (40 Punkte)

Dies ist eine theoretische Teilaufgabe, du brauchst also keinen Quelltext abzugeben. Sende einen Beweis ein, dass deine Lösung zu Teilaufgabe 2 und/oder 3 korrekt ist (siehe Anleitung), inklusive asymptotischer Analysen der Laufzeit und des Speichergebrauches deiner Lösung.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Reisender Händler

Maus Stofl hat genug von der Schweiz und wandert nach Russland aus um ein reisender Händler zu werden. Im uralen Russland nördlich von Kasan, wo die diesjährige IOI stattfindet, befinden sich N Dörfer. Jedes Dorf ist mit jedem anderen verbunden und Stofl muss eine gewisse Distanz überwinden um vom einen zum anderen zu gelangen.

Überwältigt von der kulturellen Vielfalt in Russland möchte Stofl möglichst viel erleben. Aus diesem Grund besucht er immer das Dorf als nächstes das am weitesten von seine aktuellen Standort entfernt ist, bis er alle Dörfer besucht hat, wobei er nie ein Dorf zweimal besucht. Stofl erfährt bald, dass es noch einen zweiten, einheimischen Händler gibt: Maus Vladimir. Maus Vladimir hat die gleiche Strategie wie Stofl, mit der Ausnahme dass er immer zum Dorf mit der kürzesten Distanz geht, da er die Umgebung kennt und einfach möglichst schnell fertig sein möchte.

Teilaufgabe 1: Wege berechnen (20 Punkte)

Maus Stofl startet im Dorf A, Maus Vladimir im Dorf B. Berechne wie weit die beiden jeweils reisen müssen, bis sie alle Dörfer besucht haben.

Eingabe

Auf der ersten Zeile steht eine Zahl T, die Anzahl Testfälle.

Für jeden Testfall stehen auf der ersten Zeile drei ganze Zahlen N, A und B. Die Anzahl Dörfer, das Startdorf von Stofl und das Startdorf von Vladimir. Es folgen N Zeilen mit jeweils N ganzen Zahlen mij wobei die j-te Zahl in der i-ten Zeile für die Distanz zwischen dem i-ten und j-ten Dorf steht. Alle Distanzen sind unterschiedlich, das heisst keine zwei Distanzen zwischen verschiedenen Dörfer sind gleich.

Ausgabe

Gib für den t-ten Testfall eine Zeile im Format “Case #t: S V” aus, wobei S die Distanz ist, die Maus Stofl zurücklegt und V die Distanz von Vladimir.

Limits

  • 2 ≤ N ≤ 100
  • 1 ≤ A, B ≤ N
  • 1 ≤ mij ≤ 10 000

Beispiel

Eingabe:

1
4 1 1
0 1 5 6
1 0 2 10
5 2 0 14
6 10 14 0

Ausgabe:

Case #1: 22 17

Bemerkung:

Stofl nimmt die Route 1 → 4 → 3 → 2, was eine Distanz von 22 ergibt. Vladimir hingegen nimmt 1 → 2 → 3 → 4 und legt eine Distanz von 17 zurück.

Teilaufgabe 2a: Beispiele mit unterschiedlicher Weglänge (10 Punkte)

Maus Stofl möchte wissen ob es möglich ist, die Distanzen zwischen den N Dörfern so zu wählen, dass die Strecke die Stofl zurücklegt genau um D länger ist als die von Maus Vladimir. Beachte dass wie bisher alle Distanzen unterschiedlich sind.

Eingabe

Auf der ersten Zeile steht eine Zahl T, die Anzahl Testfälle. Für jeden Testfall sind auf einer Zeile zwei ganze Zahlen gegeben, die Anzahl Dörfer N und der Distanzunterschied D.

Ausgabe

Für den t-ten Testfall hat die erste Zeile das Format “Case #t: N A B”. N ist in der Eingabe gegeben, A und B entprechen dem Startdorf von Stofl und dem Startdorf von Vladimir. Es folgen N Zeilen mit jeweils N Zahlen: In der i-ten Zeile ist die j-te Zahl die Distanz zwischen Dorf i und Dorf j. Beachte dass alle Distanzen unterschiedlich sein müssen und die Distanz in beide Richtungen die selbe ist (d.h. mij = mji). Die Distanz von einem Dorf zu sich selber soll 0 betragen (d.h. mkk = 0). Für i ≠ j soll 1 ≤ mij ≤ 109 gelten.

Limits

  • 3 ≤ N ≤ 100
  • 1 ≤ D ≤ 1 000

Beispiel

Eingabe:

1
4 5

Ausgabe:

Case #1: 4 1 1
0 1 5 6
1 0 2 10
5 2 0 14
6 10 14 0

Bemerkung:

Das Format entspricht dem von Teilaufgabe 1.

Teilaufgabe 2b: Beispiele mit gleicher Weglänge (10 Punkte)

Nun möchte Stofl wissen, ob es auch für D = 0 möglich ist. Eingabe und Ausgabe bleiben gleich wie in Teilaufgabe 2a.

Limits

  • 3 ≤ N ≤ 100
  • D = 0

Teilaufgabe 3 (60 Punkte)

Im Allgemeinen müssen die Distanzen zwischen den Dörfern nicht unterschiedlich sein. Falls es mehrere nächste oder entfernteste Dörfer gibt, wählen Maus Stofl und Maus Vladimir ein beliebiges Dorf aus (du kannst ihre Wahl nicht beeinflussen). Auch kann es vorkommen, dass die Distanzen zweier Städte 0 sind.

Beweise nun, dass auch wenn die Distanzen beliebig sind, Maus Stofl nie schneller als Maus Vladimir ist. Formal: Gegeben sind N Dörfer (N ≥ 3) wobei jedes Dorf mit jedem anderen mit bestimmten ganzzahligen Distanz  ≥ 0 verbunden ist. Beweise, dass die Distanz, die Maus Stofl zurücklegt, grösser oder gleich der Distanz ist, die Maus Vladimir zurücklegt.

Oder bezogen auf die vorherigen Teilaufgabe, es gibt kein Beispiel für D < 0.

Der Beweis ist nicht offensichtlich. Du kannst nicht einfach schreiben, dass es klar ist, weil Vladimir immer kürzere Wege nimmt. Vielleicht bringt sich Vladimir in eine Lage, in der er nur noch sehr teure Wege nehmen kann. Versuche deine Argumente möglich klar und präzise zu formulieren. Wir erwarten keinen streng mathematischen Beweis, allerdings sollten deine Argumente gut begründet und aufeinander aufbauend sein.

Hilfssätze

Um dir eine Hilfe zu geben, haben wir den Beweis in Hilfssätze unterteilt. Du musst diesem Schema nicht folgen, es soll dir aber einen Hinweis geben, wie du vorgehen könntest.

1 2 3 4 5

Hilfssatz 1: Distanzen sind entweder 0 (blau) oder 1 (rot). Die roten Verbindungen treffen sich in genau einem Punkt.

  • Hilfssatz 1: Dörfer haben entweder Distanz 1 oder 0 zueinander. Zusätzlich berühren sich alle Verbindungen mit Distanz 1 in genau einem Punkt (siehe Bild).
  • Hilfssatz 2: Dörfer haben entweder Distanz 1 oder 0 zueinander. Die Einschränkungen aus Hilfssatz 1 gelten nicht mehr.
  • Hilfssatz 3: Die Dörfer haben beliebige Distanz zueinander (dies ist der volle Beweis).

Für jeden gelösten Hilfssatz erhältst du 20 Teilpunkte. Wenn du Hilfssatz 3 beweist, kannst du Hilfssatz 2 als gegeben annehmen (du bekommst dann die Punkte für Hilfssatz 3, nicht aber für Hilfssatz 2). Umgekehrt kannst du auch Hilfssatz 2 direkt (ohne Hilfssatz 1) beweisen und erhältst automatisch auch Punkte für Hilfssatz 1.

Genauer: Wenn du Hilfssatz i direkt löst, hast du automatisch alle Hilfssätze  ≤ i gelöst. Wenn du Hilfssatz i beweist, darfst du Hilfssätze  < i als gegeben annehmen, diese werden dann aber nicht automatisch gelöst. Für jeden gelösten Hilfssatz erhältst du bis zu 20 Punkte.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Rennen

Jedes Jahr findet in Kazan (Russland) der grosse Käsepreis statt. Dies ist eines der grössten Formel 1 Rennen der Welt für Mäuse. Maus Stofl wird nächsten Sommer zusammen mit der Schweizer Delegation an die IOI in Kazan reisen und an diesem Prestigeträchtigen Rennen teilnehmen. Hilf ihm dabei, zu gewinnen.

Das Spiel

sample

Ein Spieldurchlauf

Jeder Spieler steuert ein Fahrzeug und gespielt wird auf einer aus Quadraten bestehenden Karte. Das Spiel läuft in mehreren Runden ab. In jeder Runde teilt jeder Spieler zuerst mit, auf welches Quadrat er fahren möchte. Nachdem alle Spieler ihren Zug mitgeteilt haben, fahren alle gleichzeitig. Dabei gibt es jedoch eine Einschränkung: der Geschwindigkeitsvektor (der Vektor zwischen den zwei vorherigen Positionen bzw. der Vektor zwischen der letzten und der nächsten Position) darf sich höchstens um 1 pro Richtung ändern. Auf der Strecke befinden sich verschiedene Checkpoints, die in beliebiger Reihenfolge besucht werden müssen, bevor das Ziel angefahren werden kann (die Zielfelder dürfen natürlich auch schon vorher befahren werden, aber der Spieldurchlauf ist dann nicht fertig). Es können mehrere Spieler zur selben Zeit auf dem selben Feld stehen.

Zusätzlich hat jeder Spieler je einen Käse sowie eine Mäusefalle zur Verfügung. Der Käse bewirkt, dass die Spieler in der Nähe für eine kurze Zeit ihren Geschwindigkeitsvektor nicht mehr ändern können, die Mäusefalle bringt alle Spieler in der Nähe zum Stillstand.

Einige Bemerkungen zu Käsen und Mäusefallen (im Folgenden zusammen als Objekte bezeichnet):

  • Die Objekte können zu einem beliebigen Zeitpunkt gelegt werden und sie wirken am Ende der Runde, nachdem alle Spieler bewegt wurden.
  • Die Objekte wirken nur in einer Runde, anschliessend werden sie wieder entfernt.
  • Es können beliebig viele Objekte in einer Runde eingesetzt werden, solange die Maximalanzahl für das gesamte Spiel nicht überschritten wird.
  • Jeder Spieler hat 1 Käse und 1 Mäusefalle pro Spiel.
  • Die Objekte können auf einem beliebigen Feld gelegt werden, es muss nicht in der Nähe des Spielers liegen.
  • Die Objekte wirken für alle Spieler, auch für denjenigen, der es eingesetzt hat.
  • Die Objekte wirken bis in einem Abstand von 2 Feldern. Stell Dir ein Quadrat mit Seitenlänge 5 vor, wo auf dem mittleren Feld das Objekt liegt. Alle Felder in diesem Quadrat sind vom Objekt betroffen.
  • Der Käse wirkt für betroffene Spieler während 2 Runden. Angenommen der Käse wird in Runde i gelegt und Spieler A ist am Ende der Runde in dem Quadrat des Käses, so kann er in der Runde i + 1 und i + 2 seinen Geschwindigkeitsvektor nicht verändern.
  • An manchen Orten im Server bzw. dessen Dokumentation ist von “Bomb” sowie “Freezer” die Rede. Hiermit sind Mäusefallen sowie Käse gemeint.

Eine Runde läuft in folgender Reihenfolge ab:

  1. Alle Spieler geben an, auf welches Feld sie fahren möchten. Sie müssen dabei die Beschränkung betreffend Geschwindigkeitsvektor einhalten. Spieler können auch Objekte einsetzen.
  2. Alle Spieler werden auf das angegebene Feld verschoben.
  3. Die eingesetzten Objekte werden ausgewertet und allfällige Folgen auf die Spieler angewandt.

Fährt ein Spieler aus der Rennstrecke, wird er auf den zuletzt besuchten Checkpoint zurückgesetzt und die Geschwindigkeit auf 0/0 gesetzt. Es ist auch erlaubt, gezielt aus der Rennstrecke zu fahren, also auf ein blockiertes Feld oder ein Feld ausserhalb der Karte (warum auch immer man das tun würde…).

Was ist ein Vektor

sample

Der Ausgangsvektor (2 / 1) lässt sich bei jedem Zug
um eins in jeder Dimension ändern.

Wenn Du bereits in der Schule gelernt hast, was ein Vektor ist, kannst du diesen Abschnitt überspringen.

Ein Vektor kann man sich als Pfeil vorstellen, der in eine bestimmte Richtung zeigt. Um eine solche Richtung darzustellen, werden mehrere Zahlen zusammen gefasst, was dann Vektor genannt wird. In unserem Fall haben wir zwei Dimensionen: die Autos haben eine Position auf der X-Achse (“rechts-links”) sowie auf der Y-Achse (“oben-unten”). Deshalb hat auch der Vektor den wir für die Geschwindigkeit brauchen, zwei Zahlen. Dieser sagt aus, um wie viele Felder sich das Auto pro Runde bewegt. Die erste Zahl steht für die X-Achse, die zweite Zahl für die Y-Achse.

Für die Y-Achse gibt es zwei Konventionen: entweder werden die Zahlen nach oben grösser oder nach unten grösser. In der Schule wirst du wahrscheinlich die erste Variante lernen, was vermutlich auch intuitiver ist: die Höhe über Meer steigt nach oben, ebenso steigen z.B. die Nummern der Stockwerke in einem Hochhaus umso höher man kommt. In der Informatik wird jedoch meistens die zweite Variante verwendet. So ist z.B. die Position eines Programmfensters als Distanz zu der oberen linken Ecke gespeichert (und somit wird die Zahl für die Y-Achse umso grösser je weiter unten ein Fenster liegt). Sinn macht dies z.B. in einem Texteditor, bei dem die Zeilennummern nach unten grösser werden. Wir verwenden in dieser Aufgabe die zweite Variante, also dass die Zahlen nach unten grösser werden.

Beispiel: Angenommen, das Auto befindet sich an der Position (5 / 8) (d.h. 5 Häuschen rechts vom Nullpunkt, 8 Häuschen unter dem Nullpunkt. Der Nullpunkt liegt im oberen linken Ecken der Karte). Wenn das Auto momentan eine Geschwindigkeit von (2 / 3) hat, wird es in der nächsten Runde an der Position (7 / 11) sein. Der vom Geschwindigkeitsvektor dargestellte Pfeil zeigt 2 Felder nach Rechts und 3 Felder nach Unten. Wenn man diesen Pfeil nun bei der aktuellen Position hinlegt, zeigt er genau auf das Zielfeld: (7 / 11).

Du kannst den Geschwindigkeitsvektor um 1 pro Richtung pro Runde verändern. D.h. wenn du momentan mit einem Geschwindigkeitsvektor von (2 / 3) unterwegs bist, hast du 9 Möglichkeiten, eine Geschwindigkeit zu wählen:

  • Die Geschwindigkeit beibehalten: (2 / 3)
  • Die Geschwindigkeit auf der X-Achse um 1 Verändern: (1 / 3), (3 / 3)
  • Die Geschwindigkeit auf der Y-Achse um 1 Verändern: (2 / 2), (2 / 4)
  • Die Geschwindigkeit in beiden Richtungen um 1 Verändern: (1 / 2), (1 / 4), (3 / 2), (3 / 4)

Eingabe und Ausgabe

Das Programm wird für jedes Spiel einzeln gestartet. Die Kommunikation läuft über Std I/O. Um die Aufgaben lösen zu können, benötigst du das von uns zur Verfügung gestellte Programm, das du am Ende dieser Beschreibung herunterladen kannst. In diesem Abschnitt wird auch alles Wichtige erklärt, wie dieses zu verwenden ist.

Auf der ersten Zeile stehen W (Breite der Karte), H (Höhe der Karte) und P (Anzahl Spieler). Es folgen H Zeilen mit jeweils W Zeichen. Das i-te Zeichen in der j-ten Zeile entspricht dem Element an der Position (i / j). Die Zeichen haben folgende Bedeutung:

Zeichen Bedeutung
. freies Feld
# Wand
= Start
$ Ziel
a bis z Checkpoint

Daraufhin gibt der Spieler X Y aus, seine gewünschte Startposition (ein beliebiges Feld, das mit = markiert ist).

Zu Beginn jeder Runde gibt der Server eine einzelne Zeile mit 1 aus. Es folgen P Zeilen, der aktuelle Zustand der anderen Spieler:

N X Y VX VY B F

Die ID des Spielers (N, die Spieler sind von 0 bis P-1 nummeriert, dein Programm hat immer die ID 0), die aktuelle Position (X Y), die aktuelle Geschwindigkeit (VX VY) sowie die Anzahl verbleibender Mäusefallen (B) und Käse (F). Die Spieler sind nach ID sortiert.

Auf der nächsten Zeile folgt B F, die Anzahl gelegter Mäusefallen sowie Käse. Es folgen B + F Zeilen mit X Y N, die Position des Objekts sowie die ID des Spielers, der das Objekt gelegt hat. Die ersten B Zeilen sind Mäusefallen, die verbleibenden sind Käse.

Anschliessend soll das Programm die gewünschte(n) Aktion(en) ausgeben. Zuerst allfällige Mäusefallen / Käse mit B X Y bzw. F X Y. Die letzte Zeile beschreibt das gewünschte Ziel mit M X Y (das Fahrzeug soll auf die Position (X / Y) fahren). Der Geschwindigkeitsvektor darf sich hierbei um höchstens 1 pro Richtung ändern. Sei die alte Position (AX / AY), die neue Position (NX / NY) und der ursprüngliche Geschwindigkeitsvektor (VX / VY), dann gilt: |(NX - AX) - VX| <= 1 und |(NY - AY) - VY| <= 1.

Vorsicht: Falls das Fahrzeug von einem Käse oder einer Mäusefalle beeinflusst wird, kann der eigene Geschwindigkeitsvektor vom Erwarteten abweichen.

Beispiel

> 50 20 2
> ##################################################
> #######..................................#########
> ####......................................aa######
> ###.........##........#############....aaaaaaa####
> ###===.....##########################aaaaaaaaaa###
> ###=======###########################aaaaaaaaa.###
> ###....===###########################aaaaa......##
> ###......############################a.........###
> ###.....###############################.........##
> ###.....###############################........###
> ##$$$$$$################################.......###
> ##$$$$$$################################.......###
> ##$$$$$$################################.......###
> ##.......##############################........###
> ###.......#########################bbbb........###
> ##.........######................bbbbbbb.......###
> ##................................bbbbbbb....#####
> ###................................bbbbbbb..######
> ##########..................#######bbbbbbb.#######
> ##################################################

< 3 4
> 1
> 0 3 4 0 0 1 1
> 1 3 4 0 0 1 1
> 0 0
< M 3 3
> 1
> 0 3 3 0 -1 1 1
> 1 3 3 0 -1 1 1
> 0 0
< M 4 3
> 1
> 0 4 3 1 0 1 1
> 1 4 3 1 0 1 1
> 0 0
< M 4 2
> 1
> 0 4 2 0 -1 1 1
> 1 4 2 0 -1 1 1
> 0 0
< B 37 18
< M 4 3
> 1
> 0 4 3 0 1 0 1
> 1 4 3 0 1 1 1
> 1 0
> 37 18 0
< M 4 5
> 1
> 0 4 5 0 2 0 1
> 1 4 5 0 2 1 1
> 0 0
...
< M 7 8
> 1
> 0 7 8 0 2 0 1
> 1 15 9 0 2 1 0
> 0 0
< M 6 10
> 0

Teilaufgabe 1: finde einen Weg (20 Punkte)

Du spielst alleine und Du musst es irgendwie ins Ziel schaffen.

Du musst die Aufgabe mit einem Programm lösen, welches den Weg zur Laufzeit berechnet (d.h. Du darfst nicht von Hand einen Weg bestimmen und diesen fest in deinem Programm speichern). Lass ein Spiel mit deinem Programm spielen und lade die generierte Datei replay.txt hoch. Am Ende der Aufgabenbeschreibung ist erklärt, wie du das Programm ausführen kannst.

Verwende diese Karte als Eingabe.

Limits

  • P = 1
  • 1 ≤ w ≤ 200
  • 1 ≤ h ≤ 100

Teilaufgabe 2: finde den optimalen Weg (30 Punkte)

sample

Eine kleine Karte, auf der sich ein optimaler Pfad finden lässt.

Du spielst alleine und Du sollst einen möglichst optimalen Weg finden. Sei O die optimale Anzahl an Runden für die gegebene Karte und Dein Programm benötigte R Runden, so erhältst Du a − (R ⁄ O) + 1⋅30 Punkte (für a = 2).

Du musst die Aufgabe mit einem Programm lösen, welches den Weg zur Laufzeit berechnet (d.h. Du darfst nicht von Hand einen Weg bestimmen und diesen fest in deinem Programm speichern). Lass ein Spiel mit deinem Programm spielen und lade die generierte Datei replay.txt hoch.

Verwende diese Karte als Eingabe.

Limits

  • p = 1
  • 1 ≤ w ≤ 20
  • 1 ≤ h ≤ 20

Teilaufgabe 3: Kreativturnier (50 Punkte)

Du spielst gegen die anderen Teilnehmer der SOI. Am SOI Tag werden die Programme gegeneinander in einem Turnier antreten, um die besten Programme zu bestimmen. Du erhältst Punkte anhand dieser Rangliste.

Limits

  • 2 ≤ p ≤ 20
  • 1 ≤ w ≤ 103
  • 1 ≤ h ≤ 103

Einsendung für Live Turnier

sample

Ein Wettbewerb zwischen mehreren Spielern.

Während der ersten Runde gibt es ein Live Turnier mit verschiedenen Karten. Dieses Turnier gibt keine Punkte, aber Du kannst dich mit anderen Teilnehmern bereits während der Runde vergleichen. Es gibt keinerlei Einschränkungen darüber, wie Du zu einer Lösung kommst, sei dies von Hand oder mit einem Programm. Verwende hierzu das hierfür zur Verfügung gestellte Server-Programm und spiele ein Spiel mit der gewünschten Karte (beachte: es darf nur ein Spieler spielen, damit das Spiel ausgewertet werden kann). Lade anschliessend die generierte Datei replay.txt hier hoch.

Wenn Du möchtest, kannst Du auch eigene Karten erstellen und uns diese per Mail schicken, dann können wir die Karte zum Live Turnier hinzufügen. Wie genau eine Karte aufgebaut sein muss steht in usage.md, das dem Server-Programm beiliegt.

Die momentan aktiven Karten:

Live Turnier Rangliste

Definitive Einsendung

Lade hier den Quellcode hoch, der schlussendlich zählen soll und für die Rangliste und das Turnier am SOI Tag verwendet werden soll. Du darfst bis zu drei Programme einsenden, das beste davon wird dann für die Rangliste verwendet. Packe diese Programme alle in ein ZIP-Archiv und sende dieses ein.

Zusätzliche Karten

Tipps

Für interaktive Aufgaben ist es wichtig, dass Du nach jeder Runde den Ausgabenpuffer flushst, um sicherzustellen, dass deine Ausgabe für den Server sichtbar wird.

Benutze folgende Befehle:

  • C/C++: fflush(stdout);
  • C++: cout << flush; (nicht nötig, wenn danach direkt eingelesen wird)
  • Pascal: flush(output);
  • In anderen Sprachen gibt es ähnliche Befehle.

Desweiteren ist es beim Lesen der Eingabe wichtig, dass dein Programm nicht auf mehr Zeichen wartet als der Server Dir als Eingabe zur Verfügung stellt. Insbesondere Leerzeichen oder Zeilenenden in C format strings sind eine häufige Fehlerquelle. Zum Beispiel, wenn Du die letzte Variable im Input mit “scanf("%d ", &x);” liest, wird die scanf-Funktion auf das nächste Zeichen warten, das kein Leerzeichen oder Zeilenende ist. Allerdings wirst Du ein solches Zeichen erst erhalten, wenn Du deinen nächsten Zug bereits angegeben hast. Um dies zu lösen, benutze stattdessen “scanf("%d", &x);”, also keine nicht-druckbaren Zeichen nach dem “%d”.

Beispiel-Bots, Server und Visualisation

Während der Ersten Runde werden wir das folgende Material zur Verfügung stellen:

  • Beispiel-Bots in verschiedenen Programmiersprachen.
  • Ein Server-Programm, das Du benutzen kannst, um dein eigenes Programm gegen deines und andere Programme sowie gegen dich selbst antreten zu lassen.
  • Eine Visualisierung, die simulierte Spiele darstellt.
  • Weitere Karten, auf denen du deine Bots testen kannst.

Du kannst diese hier herunterladen.

Kurzanleitung

Um den Server ausführen zu können, benötigst Du Java (Version 7 oder höher). Das eigentliche Server Programm befindet sich in der Datei server.jar, die restlichen Dateien sind Konfigurationsdateien, Beispielkarten sowie Beispiel-Bots. Du kannst den Server per Doppelklick auf server.jar starten, wo Du dann ein Menu hast, oder über die Konsole (Windows: Cmd, Mac: Terminal, Linux: Shell) mit Argumenten starten. Mit der ersten Variante hast Du nicht ganz alle Optionen, für das einfache Testen eines Bots oder auch das Generieren der Log Datei für die ersten beiden Subtasks sollte dies jedoch reichen. Wenn Du das Programm über die Konsole startest, verwende hierzu den Befehl java -jar server.jar arguments, wobei Du arguments durch die gewünschten Argumente ersetzt. Eine ausführliche Erklärung aller möglichen Argumente, wie auch weiteren Informationen, findest Du in der beiliegenden Datei usage.md.

Um ein Spiel von Hand zu spielen, benutze die Maus, um ein Feld auszuwählen, die Tasten M (fahren), B (Mäusefalle legen) und F (Käse legen) um die nächste Aktion auszuwählen. Mit PageUp und PageDown kannst Du zoomen, mit den Pfeiltasten die Ansicht verschieben.

Zögere nicht, uns Fragen zu dieser Aufgabe, der Programmierung oder der Webseite per E-Mail (info@soi.ch) zu stellen.

Versuche

# Aufgabe Subtask Punktzahl Verdikt

Rangliste

RankUsernameTotal (600)cablecar (100)gotthard (100)matryoshka (100)waterslide (100)salesman (100)racing (100)
loading ...