Erste Runde SOI 2019

Übersicht

Hier siehst du, welche Aufgaben du bereits gelöst hast. Lass dich nicht aufhalten und such dir oben eine Aufgabe aus, die du lösen willst!

Eine Einführung geben wir dir gerne während einem der Workshops.

AufgabeSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
mergeball (0/100)0/200/200/200/200/20
ceremony (0/100)0/100/200/200/100/40
touristtrap (0/100)0/200/200/300/30
pipeline (0/100)0/150/150/100/60
storytelling (0/100)0/200/200/150/150/30
tankgolf (0/100)0/100

An der ersten Runde der SOI 2019 gibt es 6 knifflige Aufgaben zu lösen. Jede Aufgabe besteht aus verschiedenen Teilaufgaben, die unterschiedlich viele Punkte geben. In einem anonymisierten Ranking siehst du deine ungefähre Position im Wettbewerb.

Es gibt zwei Arten von Teilaufgaben sowie ein spezieller Aufgabentyp.

Praktische Teilaufgaben

Die meisten Teilaufgaben sind praktisch. Das bedeutet, dass du ein Programm entwerfen sollst, welches eine Eingabe in Textform animmt und eine Ausgabe in Textform ausgibt.

Wenn du Python benutzt, ist dieses Tutorial vielleicht nützlich: Die erste Runde in Python lösen.

Dazu schreibst du auf deinem Computer ein Programm, das die Aufgabe löst. Du kannst dazu eine beliebige Programmiersprache wählen. Bei jeder Aufgabe findest du einige kleine Beispiele mit denen du dein Programm von Hand testen kannst. Sobald du denkst, dass dein Programm funktioniert, kannst du auf der Webseite auf “Download Input” klicken. Daraufhin wird eine Textdatei mit vielen Testfällen heruntergeladen. Du hast nun fünf Minuten Zeit, um diese mit deinem Programm zu lösen. Die Ausgabe zusammen mit dem Quelltext deines Programmes kannst du dann auf der Webseite hochladen. Du siehst dann direkt, ob deine Einsendung korrekt ist.

Kleiner Tipp: Anstatt die ganze Eingabe von Hand einzugeben, kannst du deinem Programm eine Eingabedatei zum Einlesen geben. Gib in einem Terminal “meinprogramm < meineeingabedatei.txt” ein. Dein Programm wird sich so verhalten, als ob du alle Werte in der Datei “meineeingabedatei.txt” von Hand eingegeben hättest. Bemerkung: Datei-Umleitung mit “<” funktioniert auf jedem Linux-ähnlichen System, aber auch auf Mac und Windows. Das Windows-Terminal heisst “Command Promt” oder “Eingabeaufforderung”.

Sende bitte keine kompilierten Programme, sondern lediglich den Programmcode. Versuche dich nach Möglichkeit auf nur eine Quelltextdatei zu beschränken um Übersicht und Kompilieren nicht zusätzlich zu komplizieren. Falls sie aus mehreren Dateien bestehen sollte, kannst du ein Archiv (.zip, .xz, usw.) einsenden.

Wenn etwas nicht stimmt, kannst du den Fehler beheben und es nochmal versuchen; es gibt keinen Abzug für viele Einsendungen. Nach dem Wettbewerb überprüfen die Organisatoren den Code nach Betrugsversuchen und geben dir ein kurzes Feedback.

Theoretische Teilaufgaben

Die vierte und fünfte Aufgabe enthalten neben praktischen Teilaufgaben auch theoretische. Hier liegt das Augenmerk mehr auf den mathematischen Aspekten, die mit logischen Überlegungen analysiert werden sollen, um anschliessend einen Lösungsansatz in Worte zu fassen. Auch hier lädst du deine Lösung hoch, typischerweise entweder als pdf-Datei oder als Archiv.

Bewertet werden deine Einsendungen nach der ersten Runde. Das Bewertungsschema steht jeweils in der Aufgabenstellung. Deine Punkte erfährst du vor dem SOI-Tag.

Kreativaufgabe

Die letzte Aufgabe ist die Kreativaufgabe. Dein Programm tritt interaktiv gegen die Programme der anderen Teilnehmer an. Die Aufgabe ist so gewählt, dass sie nicht optimal gelöst werden kann, aber auch dass einfache Ansätze sehr erfolgreich sein können. Am SOI-Tag führen wir ein Kreativaufgaben-Turnier durch und zeigen dir, wie dein Programm abgeschnitten hat. Nicht nur die Sieger erhalten Punkte, sondern bereits einfache Programme.

Auch hier kannst du deine Lösung als Archiv hochladen, dein Abschneiden erfährst du am SOI-Tag.

Schmelzball

Maus Stofl hat seit kurzem ein neues Lieblingsspiel: Schmelzball. In diesem Spiel befinden sich unterschiedlich grosse Kugeln auf einem horizontalen Stab. Sobald sich zwei gleich grosse Kugeln berühren, verschmelzen sich beide in eine neue Kugel doppelter Grösse. Wenn es mehrere Möglichkeiten gibt, kann Stofl selbst entscheiden, welche zwei Bälle er zuerst verschmelzen möchte, solange kein anderer Ball sich dazwischen befindet.

Nach einigem Herumprobieren stellt Maus Stofl fest, dass es abhängig von der Startkonfiguration nicht immer möglich ist, alle Kugelgrössen zu erreichen. Da es aber sehr viele Startkonfigurationen gibt, kann Stofl diese nicht alle alleine testen. Du musst für Maus Stofl ein Programm schreiben, dass ihm bei seinem Vorhaben hilft.

Teilaufgabe 1: Endstand mit zwei Kugeln (20 Punkte)

Sehr häufig kommt es vor, dass zwei gleich grosse Kugeln auf einem Balken sind. Dein erstes Programm sollte Stofl helfen, herauszufinden, wie gross die Kugeln jeweils werden, nachdem er sie verbunden hat.

Eingabe

Die erste Zeile enthält die Anzahl Spielkonfigurationen T. Es folgen T Spielkonfigurationen, die jeweils aus zwei Zeilen bestehen. Die erste Zeile enthält die Anzahl Kugeln N, die zweite Zeile besteht aus N Zahlen pi, die die jeweilige Grösse der i-te Kugel angeben.

Ausgabe

Gib für die t-te der T Spielkonfigurationen “Case #t: k” aus, wobei k die Grösse der resultierenden Kugel ist.

Limits

  • T = 100
  • N = 2
  • 1 ≤ pi ≤ 106
  • p0 = p1

Beispiele

Eingabe:

2
2
5 5
2
7 7

Ausgabe:

Case #0: 10
Case #1: 14

Teilaufgabe 2: Alle zu einer (20 Punkte)

Für die nächsten Spiele, die du bekommst will Maus Stofl nur wissen, ob er alle Kugeln zu einer verschmelzen kann. Er betrachtet zunächst nur Spiele, bei welchen alle Kugeln gleich gross sind.

Eingabe

Das gleiche Eingabeformat wie bei Teilaufgabe 1.

Ausgabe

Gib die t-te Spielkonfiguration “Case #t: s” aus, wobei s “Single” ist, wenn sich alle Kugeln zu einer verschmelzen lassen, oder “Multiple” ist, falls mehrere Kugeln übrig bleiben.

Limits

  • T = 100
  • 1 ≤ N ≤ 1000
  • 1 ≤ pi ≤ 106
  • p0 = p1 = … = pN − 1, d.h. alle Kugeln sind gleich gross.

Beispiele

Eingabe:

2
5
3 3 3 3 3
4
7 7 7 7

Ausgabe:

Case #0: Multiple
Case #1: Single

Bemerkung:

Case #0: Egal, wie Stofl die Kugeln verschmilzt, es bleiben immer mindestens 2 Kugeln übrig, z.B. 12 3. Case #1: Beginnt Stofl mit den inneren zwei Siebnern, so erreicht er den Zustand 7 14 7 und kann keine weiteren Kugeln verschmelzen. Stellt er sich jedoch etwas geschickter an, so kann er alle Kugeln zu einer einzelnen Kugel 28 verschmelzen.

Teilaufgabe 3: Alle zu einer – Teil 2 (20 Punkte)

Diese Teilaufgabe ist gleich wie Teilaufgabe 2, nur dass am Anfang nicht mehr alle Kugeln gleich gross sein müssen.

Eingabe

Das gleiche Eingabeformat wie bei Teilaufgabe 1.

Ausgabe

Das gleiche Ausgabeformat wie bei Teilaufgabe 2.

Limits

  • T = 100
  • 1 ≤ N ≤ 1000
  • 1 ≤ pi
  • Die Summe aller pi ist höchstens 109.

Beispiele

Eingabe:

2
5
3 3 6 6 6
4
7 7 11 11

Ausgabe:

Case #0: Single
Case #1: Multiple

Bemerkung:

Case #0: Nachdem die beiden 3 grossen Kugeln verschmolzen worden sind, kann Stofl die vier 6 grossen Kugeln verschmelzen. Case #1: 22 und 14 lassen sich nicht verschmelzen, somit bleiben zwei zurück.

Teilaufgabe 4: Bis ans Ende (20 Punkte)

Nun kennt Maus Stofl das Spiel schon ziemlich gut und will selber eines basteln. Zu Beginn hat es nur eine Grösse von Kugeln.

Stofl möchte nun im Voraus wissen, welche Grössen von Kugeln bei seinem Spiel entstehen können. Um zu vermeiden, dass sich seine Spieler sich an zu grossen Kugeln erschrecken, ist es verboten, Kugeln zu erreichen, die Grösser als C sind.

Schreibe ein Programm, dass alle möglichen Grössen  ≤ C von Kugeln, die entstehen können, in sortierter Reihenfolge ausgibt.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle, die jeweils aus zwei Zeilen bestehen. Die erste Zeile enthält die Anzahl Grössen von Kugeln N und die maximale Grösse C, die die Kugeln erreichen dürfen. Die zweite Zeile besteht aus N Zahlen pi, die jeweiligen Grössen der Kugeln, die Maus Stofl besitzt.

Ausgabe

Gib für den t-ten der T Testfälle “Case #t: K x0 x1 xK − 1” aus, wobei K die Anzahl der Grössen ist, die entstehen können und kleiner gleich C sind, gefolgt von diesen K Zahlen, in aufsteigender Reihenfolge sortiert.

Limits

  • T = 100
  • N = 1
  • 1 ≤ C ≤ 109
  • 1 ≤ pi ≤ 109

Beispiele

Eingabe:

2
1 20
5
1 50
7

Ausgabe:

Case #0: 3 5 10 20
Case #1: 3 7 14 28

Teilaufgabe 5: Bis ans Ende und noch viel weiter! (20 Punkte)

Maus Stofl hat jetzt mehrere Kugelgrössen und kann damit noch komplexere Spiele basteln.

Eingabe

Gleiches Format wie Teilaufgabe 4.

Ausgabe

Gleiches Format wie Teilaufgabe 4.

Limits

  • T = 100
  • 1 ≤ N ≤ 100
  • 1 ≤ C ≤ 1018
  • 1 ≤ pi ≤ 1018

Beispiele

Eingabe:

2
2 30
5 10
4 50
3 6 7 123

Ausgabe:

Case #0: 3 5 10 20
Case #1: 8 3 6 7 12 14 24 28 48

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

Zeremonie

Dieses Jahr findet die Maus-Informatikolympiade, genau wir ihr menschliches Gegenstück, in Baku, Aserbaidschan statt. Die Organisatoren haben Maus Stofl darum gebeten, ihnen bei den Vorbereitungen der Eröffnungszeremonie zu helfen.

Genauer gesagt, wurde er dafür eingeteilt, das grosse Feuerwerk zu organisieren, welches dazu da ist, die Delegationen von überall auf der Welt zu beeindrucken. Stofl ist Experte, was Feuerwerke angeht, und ist darum sicher, dass er eine grossartige Show hinzaubern wird. Es gibt nur ein kleines Problem: Er muss dafür sorgen, dass jeder einen guten Platz finden kann, um das Feuerwerk zu beobachten.

Seine Idee ist folgende: Es gibt viele neue Gebäude und Wolkenkratzer in Baku, und er würde gerne das Feuerwerk vom Dach eines dieser Gebäude abfeuern, und die Teilnehmer die Show von einem anderen Dach aus bestaunen lassen. Da es so viele Delegationen gibt, wird natürlich nicht jeder auf einem einzigen Dach Platz haben. Stofl will so viele geeignete Dächer wie möglich finden, um so viele Teilnehmer wie möglich unter idealen Bedingungen unterzubringen.

Obwohl es viele Gebäude zur Auswahl gibt, sind nicht alle ideal: Das Problem ist, dass all diese Gebäude unterschiedliche Höhen haben, und Stofl ist sich nicht sicher ob das Feuerwerk von jedem Dach in der Stadt sichtbar ist, da andere Gebäude die Sicht versperren können. Als Faustregel hat er das folgende Kriterium gewählt, um zu bestimmen ob die Sicht ideal ist: Ein Dach bietet gute Sicht des Feuerwerks, genau dann wenn alle Gebäude, die zwischen diesem Dach und dem Gebäude, von dem das Feuerwerk gestartet wird, strikt kleiner als das Gebäude des Daches sind. Kein Teilnehmer darf von dem Gebäude aus zusehen, wo die Organisatoren die Raketen ablassen, aus offensichtlichen Sicherheits- und Haftungsgründen.

Der Einfachheit halber denken wir uns die Wolkenkratzer als alle in einer Reihe stehend. Es gibt N Wolkenkratzer. Die Höhe des i-ten Wolkenkratzers ist hi. Vom j-ten Wolkenkratzer hat man ideale Sicht auf ein Feuerwerk, das vom i-ten Wolkenkratzer startet, dann und nur dann wenn i und j unterschiedlich sind, und es kein k gibt für das sowohl min(i, j) < k < max(i, j) als auch hk ≥ hj zutrifft.

Achtung: für Teilaufgaben 2, 3 und 5 kann es lang dauern, um deine Lösung zu bewerten. Sei bitte geduldig.

Teilaufgabe 1: Starte das Feuerwerk vom westlichsten Gebäude (10 Punkte)

Maus Stofl würde gerne wissen, ob seine einfache Idee funktioniert. Er will die Feuerwerke vom westlichsten Gebäude abfeuern, und die Teilnehmer auf anderen Dächern platzieren, die die Organisation gemietet hat und von denen aus man eine ideale Sicht hat. Allerdings ist er nicht sicher ob es genügend Gebäude gibt, die so eine Sicht bieten. Hilf ihm, herauszufinden, wie viele es genau sind.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. T Testfälle folgen, jeder aus zwei Zeilen bestehend. Die erste Zeile enthält die Anzahl Wolkenkratzer N und i, den Index des Wolkenkratzers, von dem aus das Feuerwerk gestartet wird (immer 0 in dieser Teilaufgabe). Die zweite Zeile enthält N Zahlen hj, für die Höhe des j-ten Wolkenkratzers.

Ausgabe

Für den i-ten Testfall, gebe eine einzige Zeile “Case #i: M” aus, wo M die Gesamtzahl von Wolkenkratzern ist, die eine ideale Sicht auf das Feuerwerk bieten.

Limits

  • Die Anzahl Testfälle: T = 100
  • Die Anzahl Wolkenkratzer: 1 ≤ N ≤ 100
  • Der 0-basierte Index des Gebäudes, von dem aus das Feuerwerk gestartet wird: i = 0
  • Die Höhe des j-ten Wolkenkratzers für jedes j: 1 ≤ hj ≤ 103

Beispiel

Eingabe:

1
6 0
3 2 4 4 6 5

Ausgabe:

Case #0: 3

Bemerkung:

Gebäude #1, #2 und #4 bieten eine ideale Sicht. Beachte, dass die Höhe von Gebäude #0 egal ist. Gebäude #3 hat keine ideale Sicht, weil Gebäude #2 die gleiche Höhe hat, und auch #5 nicht, weil Gebäude #4 grösser ist.

Teilaufgabe 2: Mehr verfügbare Gebäude (20 Punkte)

Leider hat Maus Stofl mit deinen Resultaten von Teilaufgabe 1 festgestellt, dass es nicht genügend Wolkenkratzer mit idealer Sicht gibt. Zum Glück hat er die Besitzer anderer Gebäude kontaktiert, und viele davon sind einverstanden, ihr Dach für die Nacht auszuleihen. Kannst du Stofl wieder helfen, diesmal die vielen neuen Gebäude einschliessend?

Eingabe

Gleich wie in Teilaufgabe 1.

Ausgabe

Gleich wie in Teilaufgabe 1.

Limits

  • Die Anzahl Testfälle: T = 100
  • Die Anzahl Wolkenkratzer: 1 ≤ N ≤ 1 000 000
  • Der 0-basierte Index des Gebäudes, von dem aus das Feuerwerk gestartet wird: i = 0
  • Die Höhe des j-ten Wolkenkratzers für jedes j: 1 ≤ hj ≤ 109

Teilaufgabe 3: Starte von einem anderen Gebäude (20 Punkte)

Bedauerlicherweise ist Stofl in Schwierigkeiten mit den Behörden geraten: Sie lassen ihn das Feuerwerk nicht von dem Gebäude aus starten, welches er ursprünglich dafür geplant hatte. Stattdessen haben sie ihm ein neues Gebäude zugewiesen, für das er die Bewilligung zum Starten von Feuerwerken erhält. Kannst du ihm helfen, die Anzahl Wolkenkratzer, die jetzt eine ideale Sicht bieten, zu berechnen?

Eingabe

Gleich wie in Teilaufgabe 1 und 2, aber i ist nicht mehr immer 0.

Ausgabe

Gleich wie in Teilaufgabe 1 und 2.

Limits

  • Die Anzahl Testfälle: T = 100
  • Die Anzahl Wolkenkratzer: 1 ≤ N ≤ 1 000 000
  • Der 0-basierte Index des Gebäudes, von dem aus das Feuerwerk gestartet wird: 0 ≤ i < N
  • Die Höhe des j-ten Wolkenkratzers für jedes j: 1 ≤ hj ≤ 109

Beispiel

Eingabe:

1
9 4
5 3 2 4 3 2 3 3 1

Ausgabe:

Case #0: 4

Bemerkung:

Gebäude #0, #3, #5 und #6 bieten eine ideale Sicht.

Teilaufgabe 4: Finde das Gebäude mit optimaler Sichtbarkeit (10 Punkte)

Maus Stofl hat alle Probleme gelöst, die er mit der Administration hatte, und sie lassen ihn jetzt jedes Gebäude nutzen, um sein Feuerwerk abzufeuern. Das gibt Stofl eine gute Gelegenheit, um etwas bei den Kosten zu sparen, in dem er das am meisten sichtbare Gebäude wählt. Er überlegt sich auch, nur die ursprünglich geplanten Gebäude einzusetzen, um noch ein wenig mehr zu sparen. Hilf ihm, herauszufinden wie viele Gebäude eine ideale Sicht haben, wenn er den Standort der Abschussrampen optimal wählt.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. T Testfälle folgen, jeder aus zwei Zeilen bestehend. Die erste Zeile enthält die Anzahl Wolkenkratzer N. Die zweite Zeile enthält N Zahlen hj, für die Höhe des j-ten Wolkenkratzers.

Ausgabe

Für den i-ten Testfall, gebe eine einzige Zeile “Case #i: M” aus, wo M die maximale Gesamtzahl von Wolkenkratzern ist, die eine ideale Sicht auf das Feuerwerk bieten, wenn dieses vom optimalen Wolkenkratzer gestartet wird.

Limits

  • Die Anzahl Testfälle: T = 100
  • Die Anzahl Wolkenkratzer: 1 ≤ N ≤ 100
  • Die Höhe des j-ten Wolkenkratzers für jedes j: 1 ≤ hj ≤ 109

Beispiel

Eingabe:

1
9
5 3 2 4 3 2 3 3 1

Ausgabe:

Case #0: 5

Bemerkung:

Das optimale Gebäude, um das Feuerwerk zu starten, ist #6. Wenn Stofl dieses wählt, bieten Gebäude #0, #3, #4, #5 und #7 eine ideale Sicht.

Teilaufgabe 5: Finde das Gebäude mit optimaler Sichtbarkeit mit vielen Gebäuden (40 Punkte)

Da sich herausgestellt hat, dass die Konfiguration mit weniger Gebäuden nicht genügend Plätze mit idealer Sicht für jeden Teilnehmer bietet, hat Stofl entschieden, jedes Gebäude zu benützen, das er kann, ohne Rücksicht auf Kosten. Kannst du ihm helfen, zu berechnen, wie viele er im besten Fall verwenden kann, genau wie in der letzten Teilaufgabe, aber mit viel mehr Wolkenkratzern?

Eingabe

Gleich wie in Teilaufgabe 4.

Ausgabe

Gleich wie in Teilaufgabe 4.

Limits

  • Die Anzahl Testfälle: T = 100
  • Die Anzahl Wolkenkratzer: 1 ≤ N ≤ 1 000 000
  • Die Höhe des j-ten Wolkenkratzers für jedes j: 1 ≤ hj ≤ 109

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

Touristenfalle

Maus Stofl besucht gerade Baku, die Hauptstadt Aserbaidschans. Baku hat eine sehr schöne Altstadt, die aber auch schwer zu navigieren ist, da sie aus vielen engen Gassen besteht, die fast ein Labyrinth bilden. Darum hat sich Stofl für eine Führung durch die Stadt entschieden. Im weiteren Verlauf der geführten Tour bekam Stofl aber das Gefühl, dass sie durch einen Laden gehen und etwas kaufen müssen, um die Führung fortzusetzen. Stofl ist sehr geizig und würde, wenn möglich, lieber kein Geld ausgeben, und würde darum lieber stattdessen die Besichtigung vorzeitig abbrechen.

Es stellt sich die Frage, ob es möglich ist, aus der Altstadt herauszukommen, ohne durch ein Gebäude zu gehen (die allesamt Läden sind). Zum Glück hat Maus Stofl ein Handy mit GPS das seine genaue Position anzeigt, ausserdem hat er sich im Voraus eine Karte der Altstadt Bakus heruntergeladen. Kann er der Touristenfalle entkommen?

Teilaufgabe 1: ASCII-Karte (20 Punkte)

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle, jeder im folgenden Format: Auf der ersten Zeile jedes Testfalls stehen die Zahlen w, h, x und y (w, h ≥ 1, 0 ≤ x < w, 0 ≤ y < h), die Grösse Bakus Altstadt und Stofls Position.

Es folgen h Zeilen je mit w Zeichen. Das i-te Zeichen der j-ten Zeile beschreibt, ob es an Position x = i, y = j ein Gebäude hat: # für ein Gebäude, _ für kein Gebäude.

Ausgabe

Gib für jeden Testfall 0 ≤ t < T eine Zeile “Case #t: p” aus, wobei p entweder “POSSIBLE” oder “IMPOSSIBLE” ist, je nachdem ob es möglich ist, ein Grenzfeld mit x = 0, y = 0, x = w − 1 oder y = h − 1 zu erreichen.

Limits

w, h ≤ 100

Beispiel

Eingabe:

2
10 8 2 4
########__
#____###__
#_#_____##
#_#__##_##
#__####__#
########_#
##_______#
##_#######
8 7 1 1
######_#
#___##_#
#___##__
#___##_#
####___#
######_#
######_#

Ausgabe:

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

Bemerkung:

Case 0: Stofl ist am Ende der L-förmigen Strasse links und kann zum südlichen Ausgang laufen.

Case 1: Stofl ist auf dem Platz im Nordwesten, aber dieser ist nicht zur Strasse im Osten verbunden.

Teilaufgabe 2: Vektorkarte (20 Punkte)

Der Herausgeber der Karte, die Stofl braucht, hat das Kartenformat aktualisiert, da grössere Karten viel Platz beanspruchten. Nun werden die Strassen als eine Reihe von Rechtecken dargestellt.

Eingabe

Das Kartenformat ist jetzt anders. Statt h Zeilen mit w Zeichen wird jetzt folgendes Format gebraucht:

Eine Zeile mit r, der Anzahl der Strassen, gefolgt von r Zeilen die je eine Strasse beschreiben. Die i-te dieser Zeilen enthält die vier Zahlen xi, yi, wi und hi (0 ≤ xi, yi, 1 ≤ wi, hi, xi + wi ≤ w, yi + hi ≤ h). Die Position x, y ist von der Strasse #i bedeckt, falls xi ≤ x ≤ xi + wi − 1 und yi ≤ y ≤ yi + hi − 1. Die Strassen können sich, müssen sich aber nicht überlappen, wie zum Beispiel an einer Kreuzung.

Ausgabe

Gleich wie in Teilaufgabe 1.

Limits

w, h ≤ 100, r ≤ 100

Beispiel

Eingabe:

2
10 8 2 4
10
1 1 1 4
2 4 1 1
2 1 3 1
3 2 2 2
3 2 5 1
7 2 1 3
8 4 1 3
2 6 7 1
2 6 1 2
8 0 2 2
8 7 1 1
4
1 1 3 3
4 4 2 1
6 0 1 7
6 2 2 1

Ausgabe:

Case #0: POSSIBLE
Case #1: IMPOSSIBLE

Bemerkung:

Dies sind die gleichen Eingaben wie im Beispiel für Teilaufgabe 1, nur im neuen Format. 8 7 1 1 ist die erste Zeile der zweiten Teilaufgabe.

Teilaufgabe 3: Grössere Karte (30 Punkte)

Dies ist die gleiche Teilaufgabe wie Teilaufgabe 2, aber mit grösseren Eingaben.

Eingabe

Gleich wie in Teilaufgabe 2.

Ausgabe

Gleich wie in Teilaufgaben 1 und 2.

Limits

w, h ≤ 109, r ≤ 103

Teilaufgabe 4: Noch grössere Karte (30 Punkte)

Dies ist die gleiche Teilaufgabe wie Teilaufgaben 2 und 3, aber mit noch grösseren Eingaben. Achtung: Lies den Abschnitt Bewertung.

Eingabe

Gleich wie in Teilaufgaben 2 und 3.

Ausgabe

Gleich wie in den vorigen Teilaufgaben.

Bewertung

Da mit den möglichen Limits in diesem Contest-Format auch optimierte Bruteforce-Lösungen durchkommen, werden wir manuell alle Einsendungen durchsehen und behalten uns vor, nachträglich einer akzeptierten Einsendung 0 Punkt zu vergeben.

Wir erwarten eine Lösung in O(rlogr) (oder mit ein paar zusätzlichen Log-Faktoren).

Update (2018-09-16): Vorher stand hier O(nlogn). Wir erwarten, dass die Lösung quasilinear in r, der Anzahl Strassen, läuft. Es reicht nicht, quasilinear in der Kartengrösse oder in der Anzahl Überschneidungen zu sein (welche im schlimmsten Fall Θ(r2) gross sein kann).

Um zu testen, ob deine Lösung die Vorgaben erfüllt, kannst du eine vorgenerierte Eingabe hier herunterladen: touristtrap-sub4-large.in und touristtrap-sub4-large.out. Deine Lösung sollte dafür zwischen 2 und 10 Minuten benötigen.

Limits

w, h ≤ 109, r ≤ 105

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

Pipeline

Azerbaijan ist der Geburtsort der Ölindustrie. Um ihr Öl in der ganzen Welt zu verteilen, wurde kürzlich die Baku—Tiflis—Ceyhan (BTC) Pipeline geöffnet. Jetzt bist du für ein noch ehrgeizigeres Projekt verantwortlich: Die Erzurum—Tulcea—Herisau (ETH) Pipeline, welche Baku via der BTC und ETH Pipeline direkt mit der Schweiz verbinden.

Die Hauptschwierigkeit bei so langen Pipelines ist, den Ölfluss ständig aufrecht zu erhalten. Um das Öl vorwärts zu schieben, planst du, P Pumpstationen zu bauen. Dafür hast du N mögliche Bauplätze identifiziert. Die Geschwindigkeit des Öls hängt entscheidend von der Distanz zwischen zwei Pumpstationen ab. Der längste Abschnitt ohne Pumpstation wird der Engpass der ganzen Pipeline. Im Öljargon wird die Länge der längsten Strecke ohne Pumpe “longest thrust circumvent” (LTC) genannt. Dein Ziel ist es, die LTC zu minimieren.

Teilaufgabe 1: Fixe LTC (15 Punkte)

Du kennst N und L (die maximal erlaubte LTC), sowie die möglichen Bauplätze (x0, x1, …, xN − 1, wo xi der i-te potenzielle Standort für eine Pumpstation ist). Berechne die minimale Anzahl von Pumpstationen P, die für eine LTC von höchstens L nötig ist.

Die Pipeline beginnt bei x0 und endet bei xN − 1. Aus technischen Gründen muss an den beiden Orten x0 und xN − 1 immer eine Pumpstation stehen.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. T Testfälle folgen, jeder mit N und L in der ersten und x0, x1, …, xN − 1 in der zweiten Zeile. Die Orte sind in aufsteigender Reihenfolge angegeben.

Ausgabe

Für den i-ten Testfall, gebe eine Zeile “Case #i:” aus, gefolgt von entweder:

  • einer Zahl P ≤ 9000 gefolgt von P Zahlen p0 < p1 < … < pP − 1. P ist die minimale Anzahl von Pumpstationen, die nötig ist, und pi ist der Ort der i-ten Pumpstation. Wenn es mehrere Lösungen mit P Stationen gibt, gib irgendeine davon aus.
  • einfach eine Zahl P > 9000 wenn mehr als 9000 Pumpstationen nötig sind.
  • Impossible”, wenn es unmöglich ist, die Pumpstationen so zu bauen dass die LTC höchstens L ist.

Limits

  • T = 100
  • 1 ≤ N ≤ 100 000
  • 1 ≤ L ≤ 109
  • 0 ≤ x0 < x1 < … < xN − 1 ≤ 109

Beispiel

Eingabe:

4
6 4
2 4 6 7 11 12
3 3
1000 1003 1007
1 3
5
5 2
0 1 2 3 4

Ausgabe:

Case #0: 5 2 4 7 11 12
Case #1: Impossible
Case #2: 1 5
Case #3: 3 0 2 4

Bemerkung:

In Case #0 wäre 5 2 6 7 11 12 eine andere Möglichkeit gewesen.

Grosse Eingabe:

Eingabe:

2
9000 1
0 1 2 3 ... 8999
9001 1
0 1 2 3 ... 8999 9000

Ausgabe:

Case #0: 9000 0 1 2 ... 8999
Case #1: 9001

Bemerkung:

Die Punkte sind nur zur Veranschaulichung. Du kannst die Eingabedatei hier herunterladen.

Teilaufgabe 2: Fixe Anzahl Pumpen (15 Punkte)

Diese Mal weisst du N und P, die Anzahl Pumpen und mögliche Bauplätze. Berechne die minimale LTC, die du erreichen kannst.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. T Testfälle folgen, jeder mit N und P in der ersten und x0, x1, …, xN − 1 in der Zweiten Zeile.

Ausgabe

Für den i-ten Testfall, gebe zwei Zeilen aus. Die erste Zeile sollte “Case #i: L” sein, wobei L die minimale LTC ist, die du durch optimale Platzierung der P Pumpstationen erreichen kannst.

In der zweiten Zeile, falls P ≤ 9000, gebe genau P Zahlen p0, p1, …, pP − 1 aus, die Standorte der Pumpen. Ist P ≥ 9001, gebe “Over 9000” anstatt der Standorte der Pumpstationen aus. P steht hier für den Wert aus der Eingabe.

Limits

  • T = 100
  • 1 ≤ N ≤ 100 000
  • min(2, N) ≤ P ≤ N
  • 0 ≤ x0 < x1 < … < xN − 1 ≤ 109

Beispiel

Eingabe:

4
6 5
2 4 6 7 11 12
3 2
1000 1003 1007
1 1
5
5 4
0 1 2 3 4

Ausgabe:

Case #0: 4
2 6 7 11 12
Case #1: 7
1000 1007
Case #2: 0
5
Case #3: 2
0 1 2 4

Bemerkung:

In Case #3 ist die Pumpe am Ort 1 (oder 3) eigentlich für nichts, da sie die LTC nicht beeinflusst. Aber du musst genau P Pumpstationen bauen.

Grosse Eingabe:

Eingabe:

2
9000 9000
0 1 2 3 ... 8999
9001 9001
0 1 2 3 ... 8999 9000

Ausgabe:

Case #0: 1
0 1 2 ... 8999
Case #1: 1
Over 9000

Bemerkung:

Die Punkte sind nur zur Veranschaulichung. Du kannst die Eingabedatei hier herunterladen.

Teilaufgabe 3: An der BTC entlanglaufen (10 Punkte)

Die neue geplante Pipeline ist so lang, dass du dir unmöglich alle N möglichen Bauplätze merken kannst. Noch schlimmer, weder P noch die LTC sind fix. Du kennst nur eine obere Schranke M der LTC, in anderen Worten, du willst auf keinen Fall eine LTC grösser als M.

Um mit diesen Zahlen umgehen zu können, schreibst du ein Programm. Du gibst dem Programm M, die maximale LTC, die du erlaubst. Dann liest das Programm alle N möglichen Bauplätze in aufsteigender Reihenfolge. Am Schluss gibt es dir M Zahlen: Die i-te Zahl (0-basiert) sagt dir die minimale Anzahl Pumpen, die du brauchst, um eine LTC von höchstens i + 1 zu garantieren.

Bevor du dir die ETH Pipeline vornimmst, läufst du der kleineren BTC entlang. Für die BTC ist die Eingabe klein genug, dass dein Programm alle Zahlen speichern kann. Die letzte Teilaufgabe hingegen wird genau gleich sein, ausser dass sie über die ETH ist, und du dass darum nicht mehr tun kannst. Um dir etwas Arbeit zu ersparen, empfehlen wir dir, die letzte Teilaufgabe zu lesen, bevor du diese hier löst (aber du darfst diese Teilaufgabe auf jede beliebige Art lösen).

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. T Testfälle folgen, jeder mit N und M in der ersten und x0, x1, …, xN − 1 in der zweiten Zeile.

Ausgabe

Für den i-ten Testfall, gebe eine einzige Zeile “Case #i:” aus, gefolgt von M Zahlen “p0, p1, …, pM − 1”, wo pi die minimale Anzahl Pumpstationen ist, die du brauchst um eine LTC von höchstens i + 1 zu erreichen. Wenn das unmöglich ist, gebe stattdessen  − 1 aus.

Limits

  • T = 100
  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 250
  • 0 ≤ x0 < x1 < … < xN − 1 ≤ 109

Beispiel

Eingabe:

4
6 10
2 4 6 7 11 12
3 7
1000 1003 1007
1 1
5
5 4
0 1 2 3 4

Ausgabe:

Case #0: -1 -1 -1 5 3 3 3 3 3 2
Case #1: -1 -1 -1 3 3 3 2
Case #2: 1
Case #3: 5 3 3 2

Teilaufgabe 4 (Theoretisch): An der ETH entlanglaufen (60 Punkte)

Jetzt geht es ums eigentliche: die ETH. Da wir den Speichergebrauch deines Programms nicht überprüfen können, ist dies eine theoretische Teilaufgabe. Beschreibe einen Algorithmus, der Teilaufgabe 3 löst und untersuche dessen Laufzeit und Speicherbedarf.

Optimiere zuerst den Speicherbedarf, und die Laufzeit an zweiter Stelle. Siehe Bewertung für mehr Einzelheiten.

Gebe ein Dokument (PDF bevorzugt) ab, welches beschreibt

  • wie dein Algorithmus funktioniert,
  • warum dein Algorithmus korrekt ist, und
  • wie viel Speicher und Zeit er benötigt.

Limits

  • N und M sind Variablen, d.h. du solltest sie in deiner Analyse verwenden. Du kannst davon ausgehen, dass N viel grösser als M ist.
  • Die xi sind sortiert (0 ≤ x0 < x1 < … < xN − 1) aber können beliebig gross werden. Du kannst annehmen, dass arithmetische Grundoperationen (Addition, Subtraktion, Multiplikation, Division, und Vergleiche) eine Zeiteinheit benötigen und dass das Speichern einer Zahl eine einzige Speicherzelle belegt.

Bewertung

Der Speichergebrauch deiner Datenstruktur sollte nur von M abhängen, nicht von N. Ziele auf O(M) Speicher, aber es ist auch ok wenn du ein wenig mehr benötigst.

Wenn alles andere korrekt ist, geben wir dir Punkte anhand folgender Tabelle.

Speicherbedarf Laufzeit Maximale Punktzahl
O(M) O(NM) 20
O(M1.5) O(NM0.75) 40
O(M) O(NM0.75) 50
O(MlogM) O(NM0.5logM) 50
O(M) O(NM0.5(logM)2) 60

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

Märchenstunde

Maus Stofl hat Aserbaidschan erkundet, um dir erzählen zu können, was es dort alles zu sehen und erleben gibt wenn du an der IOI 2019 teilnimmst. Heute hat er den bekannten Feuerberg Yanar Dag besucht – ein Ort, wo Steine und Wasser spontan zu brennen beginnen. Maus Stofl hat eine Übernachtung bei Maus Yusif organisiert. Die Gastfreundschaft der aserbaidschanischen Mäuse versetzte Stofl in Staunen, als sich Yusifs gesamte Familie zu Stofls Ehren versammelte.

Für das Nachtessen sitzen alle N Mäuse (inklusive Stofl) um einen runden Tisch. In Aserbaidschan ist es Tradition, sich vor dem Essen Geschichten zu erzählen. Diese Erzählungen müssen sehr strikten Regeln folgen (besonders in der Anwesenheit eines Gastes):

  • Jede Maus muss seinen Nachbarn genau eine Geschichte erzählen.
  • Eine Geschichte muss ohne Unterbrechungen erzählt werden.
  • Wenn eine Maus eine Geschichte erzählt, müssen beide Nachbarn zuhören – d.h. sie können zur selben Zeit nicht selbst eine Geschichte erzählen.
  • Die Mäuse sind gute Zuhörer: eine Maus kann beiden Nachbarn gleichzeitig zuhören.
  • Essen wird erst serviert, sobald alle Geschichten erzählt wurden.

Die Mäuse sind bereits sehr hungrig und möchten möglichst bald essen.

Du erhältst positive Ganzzahlen t0, …, tN − 1 – die Längen (in Sekunden) der Geschichten, welche die N Mäuse erzählen möchten. Die Längen sind in der Reihenfolge gegeben, in der die Mäuse um den Tisch sitzen. Finde den optimalen Zeitplan für die Märchenstunde.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T.

T Testfälle folgen, jeder hat folgendes Format: Die erste Zeile eines jeden Testfalles enthält eine Ganzzahl N: die Anzahl Mäuse am Tisch. Die zweite Zeile enthält N leerzeichengetrennte Ganzzahlen: die Zahlen t0, …, tN − 1.

Ausgabe

Gib für jeden Testfall zwei (Teilaufgaben 1 und 2) bzw. eine (Teilaufgaben 3 und 4) Zeilen aus:

  • Eine Zeile der Form “Case #t: X” wobei t die Nummer des Testfalles ist (0 ≤ t < T) und X die kürzeste Zeit (in Sekunden) in der alle N Mäuse ihre Geschichten erzählen können.
  • In Teilaufgaben 1 und 2: Eine Zeile mit N leerzeichengetrennten Ganzzahlen y0, …, yN − 1 mit folgender Bedeutung: Maus i soll yi Sekunden nach Beginn des Abendessens mit dem Erzählen ihrer Geschichte beginnen.

Falls mehrere optimale Lösungen existieren kannst du eine beliebige davon ausgeben.

Limits

  • Für alle Testfalle: T = 100.

Beispiele

Eingabe:

2
5
1 1 1 1 1
6
2 3 1 2 2 1

Ausgabe:

Case #0: 3
0 1 2 0 1
Case #1: 5
0 2 0 1 3 2

Teilaufgabe 1 (20 Punkte)

  • 2 ≤ N ≤ 8, ti ≤ 32 für alle i.

Teilaufgabe 2 (20 Punkte)

  • 2 ≤ N ≤ 100, t0 = 0 und ti ≤ 100 für alle i.

Teilaufgabe 3 (15 Punkte)

  • 2 ≤ N ≤ 105, N ist gerade, ti ≤ 109 für alle i.

Teilaufgabe 4 (15 Punkte)

  • 2 ≤ N ≤ 105, N ist ungerade, ti ≤ 109 für alle i.

Teilaufgabe 5 (30 Punkte)

Nehme für diese Teilaufgabe an, dass bei Teilaufgaben 3 und 4 auch gefragt wurde, die y0, …, yN − 1 auszugeben.

Beweise, dass deine Lösungen für Teilaufgaben 3 und 4 korrekt sind und analysiere deren Laufzeit. Ein korrekter Beweis für nur einen der beiden Teilaufgaben (3 oder 4) ist maximal 15 Punkte wert.

Wir empfehlen dir folgende Beweisvorlage (Die kursiven Teile sind von dir zu ergänzen.)

  1. Der Algorithmus sieht aus wie und berechnet dies weil irgendeine Erklärung.

  2. Die Laufzeit und Speicherverbrauch ist O(?) weil es so ist.

  3. Gegeben eine beliebige Eingabe t0, …, tN − 1, der Algorithmus ist sowohl:

    • eine obere Schranke für die optimale Lösung: Die vom Algorithmus berechneten Zahlen y0, …, yN − 1 erfüllen die Einschränkungen infolge meines Beweises. Daher eine optimale Lösung benötigt höchstens X Sekunden.
    • als auch eine untere Schranke für die optimale Lösung: Es ist unmöglich dass eine Lösung weniger als X Sekunden benötigt, da mein Beweis hier steht.

    Die Lösung ist somit optimal.

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

Tankgolf

Um diese Aufgabe zu lösen, musst du dir zuerst den Hostserver zum Spiel herunterladen, damit du deinen Bot lokal testen kannst.

Schau dir auch das Readme zum Hostserver an, dort siehst du, wie du den Server kompilieren kannst. Im Ordner bots/ findest du auch ein paar Beispiel-Bots zum Spiel.

Falls du Probleme beim Kompilieren hast, zögere nicht, Fragen an pascal@soi.ch zu stellen.

Programmiere einen Bot für das Spiel “TankGolf”. Unten folgt eine Beschreibung des Spiels, aber falls du ein Android-Handy hast, kannst du eine ähnliche Version des Spiels auch aus dem Playstore herunterladen.

Das Spiel beinhaltet zwei Panzer, die gegeneinander antreten. Die Panzer können mit ihren Kanonen schiessen und dabei Schusswinkel und -intensität wählen. Die Kugeln explodieren wenn sie auf einer Oberfläche einschlagen, und das Ziel ist es, den anderen Panzer mithilfe der Schockwelle der Explosion ab dem Spielfeld zu drängen. Die Panzer wechseln sich ab mit Schiessen, und die Panzer müssen jeweils warten, bis alles wieder zum Stillstand gekommen ist nach dem letzten Schuss, bis wieder jemand schiessen darf. Wenn ein Spieler ab dem Spielfeld fällt, erhält der Gegner einen Punkt und der Spieler respawnt.

Die Aufgabe ist es nun, einen Bot zu schreiben, der, gegeben die aktuellen Positionen und Rotationen der Panzer, einen Schusswinkel und -intensität wählt. Der Schuss wird mit einer kleinen Ungenauigkeit ausgeführt, wobei der Ungenauigkeitsradius abhängig vom Quadrat der Intensität ist. Somit wird dafür gesorgt, dass lange Schüsse riskanter sind als kurze.

Der Server stellt ein paar Funktionen bereit, um die Flugbahn eines Schusses und die Auswirkung des Schusses auf die Panzer vorherzusehen. Dein Bot kann diese Funktionen so oft aufrufen wie du willst, bitte sorge aber dafür, dass dein Panzer nicht länger als ein paar Sekunden für jeden Zug hat. (Die Zeit zum Anzeigen der Visualisierung wird dabei nicht dazugezählt)

Die genaue Beschreibung der Karte findest du in geometry/maps/map1.json, oder du kannst dir die mitgelieferte Visualisierung anschauen. Für den Wettkampf wird genau die selbe Karte verwendet.

Protokoll

Es gibt zwei Arten von Runden: Respawn und Shoot.

Dein Panzer wird sich immer als Spieler A im Protokoll sehen, Spieler B ist also immer der Gegner in den erhaltenen Daten.

Ein Spielstand hat zwei mögliche Darstellungen, eine Version mit mehr Detail, und eine mit weniger Detail:

full:playerA.x playerA.y playerA.angle playerB.x playerB.y playerB.angle last_impact.x last_impact.y scores.playerA scores.playerB
small:playerA.x playerA.y playerA.angle playerB.x playerB.y playerB.angle

Eine Position die nicht auf dem Spielfeld ist wird als -1, -1 dargestellt. Z.B. ein Spieler der ab dem Spielfeld fiel oder die last_impact Position vor dem ersten Schuss sind -1, -1.

Jede Runde startet damit, dass der Server die aktuelle Art der Runde sendet: startrespawn oder startshoot, gefolgt vom Spielstand als full state.

Respawn

Server:startrespawn <full game state>

(Spieler startet eine Abfrage..)

Player:queryrespawn 12.345 so kann der Bot fragen, was würde passieren wenn ich an dieser x-position spawnen würde?
Server:state <full state nach dem Respawnen>

(… null oder mehr Queries insgesamt)

Player:respawn 12.345 respawn an dieser Position

(Runde ist abgeschlossen)

Shoot

Server:startshoot <full game state>

(Spieler startet eine Abfrage..)

Player:queryrespawn 1.13 0.9 so kann der Bot fragen, was würde passieren wenn ich mit diesem Schusswinkel und -intensität schiessen würde?
Server:state <full state nach dem Schuss>

(… null oder mehr Abfragen insgesamt)

Player:shoot 1.13 0.9 Schuss mit diesem Winkel/Intensität durchführen.

(Runde ist abgeschlossen)

Folgende Abfragen sind immer möglich wenn dein Panzer am Zug ist, egal, was für eine Runde gerade aktiv ist

Player:fullqueryshoot <small state> 1.13 0.9 where the player gives a game state and asks what would happen if I shoot with this angle and intensity
Server:state <full resulting state at rest>
Player:fullqueryrespawn <small state> 12.345 where the player gives a game state and asks what would happen if I drop down at this x position
Server:state <full resulting state at rest>

Beispiel-Interaktion

Dieses Beispiel zeigt nur die Kommunikation mit einem der Spieler.

< is server to client and > is client to server

< startrespawn -1 -1 0 -1 -1 0 -1 -1 0 0   # We're player one and thus noone is on the map yet. Bullet hasn't impacted yet. Scores are at zero.
                                           # read as: tank A: (-1, -1) 0 | tank B: (-1, -1) 0 | impact pos: (-1, -1) | scores: 0 0
> respawn 2                                # Spawn at position 2

(other player respawns)

< startshoot 2 1 0 6 1 0 -1 -1 0 0         # Other player has spawned at coordinate 6. We shoot first
> queryshoot -1.13 0.6                     # Simulate shot 1.13 radian to the right
< state 2 1 0 -1 -1 0 7.2 1                # Other player would fall in hole, we wouldn't move. We would get a point.
                                           # read as: tank A: (2, 1) 0 | tank B: (-1, -1) 0 | impact pos: (7.2, 1) | scores: 1 0
> shoot -1.13 0.6                          # Shoot as simulated before.
                                           # What the player doesn't know immediately, but what we see in the next server command is, that the shot
                                           # didn't work out because of the added randomness (impact was at 7.4, 1). We didn't get a point.

(other player shoots)

< startrespawn -1 -1 0 4.6 1 0 1.5 1 0 1   # The other player scored during their turn (last impact was at 1.5, 1). We need to select a respawn position.
> respawn 6

< startshoot 6 1 0 4.6 1 0 1.5 1 0 1       # We get to shoot immediately after respawning, because the other player was the last one to shoot.
...

Einsenden (100 Punkte)

Du spielst gegen die anderen Teilnehmer der SOI. Am SOI-Tag wird dein Programm in einem Wettbewerb teilnehmen, um den besten Bot zu bestimmen. Du darfst bis zu drei Bots einschicken. Dein bester Bot wird für das Ranking verwendet. Erstelle ein zip-Archiv, um mehrere Dateien einzuschicken.

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

RanglisteBenutzernameTotal (600)mergeball (100)ceremony (100)tourist… (100)
touristtrap
pipeline (100)storyte… (100)
storytelling
tankgolf (100)
loading ...