Erste Runde SOI 2018

Ü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 4
sushi (0/100)0/100/300/100/50
wagashi (0/100)0/200/300/250/25
cheesepatrol (0/100)0/100/200/200/50
hanabi (0/100)0/150/150/300/40
mahjong (0/100)0/250/250/200/30
samurai (0/100)0/100

An der ersten Runde der SOI 2018 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 dritte, 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.

Sushi

Maus Stofl ist zu Gast in einem Sushi-Restaurant in Tsukuba, Japan, wo gerade die IOI stattfindet. Er will für die ganze Schweizer Delegation Sushi bestellen und hat sich die gewünschten Mengen von den jeweiligen Sushi-Sorten notiert.

Heute hat es aber ein Spezialangebot! Wer zu einem Sushi noch eine Flasche Sake bestellt, bekommt ein zweites Sushi gratis. Maus Stofl und seine Freunde sind alle Abstinenzler. Sie würden allerdings auch Alkohol bestellen, wenn sie dadurch profitieren.

Insgesamt werden N Stück Sushi bestellt. Der Preis für das i-te Stück beträgt pi Yen. Eine Flasche Sake kostet S Yen. Beim Spezialangebot wird jeweils das teurere Sushi (und eine Flasche Sake) in Rechnung gestellt.

Teilaufgabe 1: Happy Hour (10 Punkte)

Es hat soeben die Happy Hour angefangen. Alle Flaschen Sake sind jetzt gratis (S = 0). Maus Stofl hat nicht gezögert und bereits eine kleine Bestellung von genau zwei Sushi (N = 2) abgegeben. Nun möchte er wissen, ob er den optimalen Gesamtpreis erreicht hat.

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 Stück vom bestellten Sushi N (hier immer 2) und den Preis für eine Flasche Sake S (hier immer 0). Die zweite Zeile besteht aus N Zahlen pi, die den jeweiligen Preis für das i-te Stück Sushi angeben.

Ausgabe

Gib für den i-ten Testfall eine einzige Zeile “Case #i: P” aus, wobei P den minimalen Gesamtpreis für die jeweilige Bestellung darstellt.

Limits

  • die Anzahl Testfälle: 1 ≤ T ≤ 100
  • die Anzahl Stück vom bestellten Sushi: N = 2
  • der Preis für eine Flasche Sake: S = 0
  • der Preis vom i-ten Stück Sushi: 1 ≤ pi ≤ 103

Beispiel

Eingabe:

2
2 0
16 42
2 0
100 64

Ausgabe:

Case #0: 42
Case #1: 100

Teilaufgabe 2: Mehr Sushi (30 Punkte)

Wegen dem hervorragenden Geschmack möchte Maus Stofl nochmals Sushi bestellen. Er will zunächst den optimalen Gesamtpreis ermitteln, muss aber schnell handeln — die Happy Hour ist ja bald vorbei…

Eingabe/Ausgabe

Wie in Teilaufgabe 1.

Limits

  • die Anzahl Testfälle: 1 ≤ T ≤ 100
  • die Anzahl Stück vom bestellten Sushi: 1 ≤ N ≤ 103
  • der Preis für eine Flasche Sake: S = 0
  • der Preis vom i-ten Stück Sushi: 1 ≤ pi ≤ 103

Beispiel

Eingabe:

1
6 0
16 42 42 42 16 42

Ausgabe:

Case #0: 100

Teilaufgabe 3: Die Happy Hour vorbei (10 Punkte)

Die Happy Hour ist nun vorbei und Maus Stofl möchte noch etwas Sushi (N = 2) bestellen.

Eingabe/Ausgabe

Wie in Teilaufgabe 1.

Limits

  • die Anzahl Testfälle: 1 ≤ T ≤ 100
  • die Anzahl Stück vom bestellten Sushi: N = 2
  • der Preis für eine Flasche Sake: 0 ≤ S ≤ 103
  • der Preis vom i-ten Stück Sushi: 1 ≤ pi ≤ 103

Beispiel

Eingabe:

1
2 32
16 42

Ausgabe:

Case #0: 58

Teilaufgabe 4: Mehrere Delegationen (50 Punkte)

Es sind kürzlich weitere IOI-Delegationen ins Restaurant hineingekommen. Maus Stofl möchte daher eine (grosse) Bestellung für alle abgeben. Kannst du für ihn den Gesamtpreis finden.

Eingabe/Ausgabe

Wie in Teilaufgabe 1.

Limits

  • die Anzahl Testfälle: 1 ≤ T ≤ 100
  • die Anzahl Stück vom bestellten Sushi: 1 ≤ N ≤ 104
  • der Preis für eine Flasche Sake: 0 ≤ S ≤ 105
  • der Preis vom i-ten Stück Sushi: 1 ≤ pi ≤ 105

Beispiel

Eingabe:

1
6 32
16 42 42 42 16 42

Ausgabe:

Case #0: 180

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

Wagashi

Um bei der IOI-Vorbereitung zusätzlichen Anreiz zu schaffen, hat Maus Stofl den Teilnehmern für jede gelöste Aufgabe ein Wagashi, eine traditionelle japanische Süssigkeit, versprochen. Jeder Teilnehmer, der die i-te Aufgabe gelöst hat, erhält ein Wagashi der Sorte i.

Die Teilnehmer wollten sich möglichst viele Wagashi verdienen und lösten überdurchschnittlich viele Aufgaben. Stofl hat nun Bedenken, dass das SOI Budget aufgrund der Wagashi-Aktion überschritten werden könnte.

Stofl möchte nun wissen, wie viel die Wagashi insgesamt kosten. Stofl mag Wagashi auch sehr, es macht ihm also nichts aus, überschüssige Wagashi zu kaufen, sofern er dadurch Kosten sparen kann.

Teilaufgabe 1: Wagashi einzeln bestellen (20 Punkte)

Stofl weiss bei jeder Aufgabe, wie viele Teilnehmer diese gelöst haben. Er hat sich auch schon bei einem lokalen Wagashi-Geschäft nach den Preisen erkundigt. Er fragt sich nun, ob er die Wagashi dort bestellen kann, ohne das Budget zu überschreiten. Berechne den minimalen Geldbetrag C, sodass Stofl für C Yen genügend Wagashi bestellen kann.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle in folgendem Format: Die erste Zeile enthält N, die Anzahl gelösten Aufgaben. Auf der zweiten Zeile folgen N Zahlen ai – die i-te Aufgabe wurde von ai Mäusen gelöst. Es folgt die dritte Zeile mit N Zahlen ci – das i-te Wagashi kostet ci Yen.

Ausgabe

Gibt für den i-ten Testfall eine einzelne Zeile mit “Case #i: C” aus, wobei C die Kosten in Yen ist.

Limits

  • T ≤ 100
  • 1 ≤ N ≤ 1 000
  • 1 ≤ ai ≤ 1 000
  • 1 ≤ ci ≤ 1 000

Beispiel

Eingabe:

3
2
3 1
7 2
5
1 2 4 8 7
3 3 2 2 12
1
1
1

Ausgabe:

Case #0: 23
Case #1: 117
Case #2: 1

Bemerkung:

Im ersten Testfall bezahlt Stofl für die 3 Wagashi der ersten Sorte je 7 Yen und für das einzelne Wagashi der zweiten Sorte 2 Yen, gesamthaft also 23 Yen.

Teilaufgabe 2: Das Wagashi-Paket (30 Punkte)

Da die Wagashi das SOI-Budget deutlich überschritten haben, hat sich Stofl nach einer Preisreduktion erkundet und ist auf das Wagashi-Paket gestossen. Das Paket kostet K Yen und enthält pi Wagashi der Sorte i. Das Paket kann auch mehr als einmal bestellt werden. Berechne den minimalen Geldbetrag C, sodass Stofl für C Yen genügend Wagashi bestellen kann.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle in folgendem Format: Die erste Zeile enthält N, die Anzahl gelösten Aufgaben, sowie K, der Preis des Wagashi-Pakets Auf der zweiten Zeile folgen N Zahlen ai – die i-te Aufgabe wurde von ai Mäusen gelöst. Es folgt die dritte Zeile mit N Zahlen ci – das i-te Wagashi kostet ci Yen, gefolgt von der vierten Zeile bestehend aus N Zahlen pi – das Wagashi-Paket enthält pi Wagashi der i-ten Sorte.

Ausgabe

Gleich wie bei Teilaufgabe 1.

Limits

  • T ≤ 100
  • 1 ≤ N ≤ 1 000
  • 1 ≤ K ≤ 109
  • 1 ≤ ai ≤ 1 000
  • 1 ≤ ci ≤ 109
  • 1 ≤ pi ≤ 1 000

Beispiel

Eingabe:

2
3 5
7 3 2
1 4 1
3 2 1
1 5
8
2
2

Ausgabe:

Case #0: 11
Case #1: 16

Bemerkung:

Im ersten Testfall bestellt Stofl 2 Wagashi-Pakete für je 5 Yen, sowie ein einzelnes Wagashi der ersten Sorte. Das überschüssige vierte Wagashi der zweiten Sorte kann Stofl selber essen. Im zweiten Testfall ist das Wagashi-Paket überteuert, folglich bestellt Stofl alle Wagashi einzeln.

Teilaufgabe 3: Wagashi bei Verwandten bestellen (25 Punkte)

Da die Teilnehmer von der Wagashi-Aktion sehr erfreut waren, plant Stofl, bei einem deutlich grösseren Trainingsanlass wieder Wagashi für jede gelöste Aufgabe zu verteilen. Um Kosten zu sparen, plant er, die Wagashi bei seinen Japanischen Verwandten bestellen. Dann müsste er nur die Transportkosten bezahlen, welche von der Wagashi-Sorte unabhängig sind. Es besteht weiterhin die Möglichkeit, ein oder mehrere Wagashi-Pakete zu bestellen. Stofl will nun wissen, wie viel er für die Wagashi budgetieren muss. Berechne den minimalen Geldbetrag C, sodass Stofl für C Yen genügend Wagashi bestellen kann.

Eingabe

Gleich wie bei Teilaufgabe 2.

Ausgabe

Gleich wie bei Teilaufgaben 1, 2.

Limits

  • T ≤ 100
  • 1 ≤ N ≤ 5⋅105
  • 1 ≤ K ≤ 109
  • 1 ≤ ai ≤ 107
  • 1 ≤ ci ≤ 105
  • Alle ci sind gleich.
  • 1 ≤ pi ≤ 107

Beispiel

Eingabe:

1
4 13
9 3 4 7
3 3 3 3
3 5 2 1

Ausgabe:

Case #0: 50

Bemerkung:

Stofl bestellt 2 Wagashi Pakete, 3 Wagashi der ersten Sorte und 5 Wagashi der vierten Sorte.

Teilaufgabe 4: Viele Wagashi zu unterschiedlichen Preisen (25 Punkte)

Stofls Verwandte waren von der Idee, so viele Wagashi selbst herzustellen, nicht sehr erfreut. Stofl wird die Wagashi also wieder zu unterschiedlichen Preisen bestellen müssen. Es bleibt ihm nicht mehr viel Zeit bis zur GV, bei welcher das Budget festgelegt wird. Berechne den minimalen Geldbetrag C, sodass Stofl für C Yen genügend Wagashi bestellen kann.

Eingabe

Gleich wie bei Teilaufgaben 2, 3.

Ausgabe

Gleich wie bei Teilaufgaben 1, 2, 3.

Limits

  • T ≤ 100
  • 1 ≤ N ≤ 5⋅105
  • 1 ≤ K ≤ 109
  • 1 ≤ ai ≤ 107
  • 1 ≤ ci ≤ 105
  • 1 ≤ pi ≤ 107

Beispiel

Eingabe:

2
3 22
8 1 12
7 31 2
3 4 2
4 41
13 9 2 19
5 2 3 6
3 2 1 4

Ausgabe:

Case #0: 74
Case #1: 189

Bemerkung:

Stofl bestellt im ersten Testfall 2 Wagashi-Pakete und im zweiten Testfall 4 Wagashi-Pakete.

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

Käsepatrollie

Maus Stofl exportiert Käse nach Japan, wo er ihn mit viel Profit verkauft. In letzter Zeit haben aber seine Einnahmen in Tōkyo abgenommen. Stofl vermutet, dass jemand auf den Strassen mit Käse dealt. Um dieses Problem zu beheben, will Stofl Privatdetektive anstellen.

Tōkyo besteht aus m Strassen und n Kreuzungen. Die i-te Strasse ist zwischen den Kreuzungen ai und bi. Zwei Kreuzungen sind durch höchstens eine Strasse verbunden und jede Strasse verbindet zwei verschiedene Kreuzungen. Ein Privatdetektiv kann entweder entlang einer Strasse stehen und diese bewachen, oder aber an einer Kreuzung stehen und genau zwei Strassen, die durch diese Kreuzung gehen, beobachten, mit jedem Auge eine.

Maus Stofl möchte nun, dass jede Strasse von mindestens einem Privatdetektiv überwacht wird und dabei möglichst wenige Privatdetektive angestellt werden. Hilf Maus Stofl, die minimale Anzahl der benötigten Privatdetektive und eine passende Platzierung zu finden!

Für Teilaufgaben 1-3:

Eingabe

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

Es folgen die T Testfälle. Pro Testfall gibt es zwei Zahlen n, die Anzahl der Kreuzungen, und m, die Anzahl der Strassen. Danach folgen m Zeilen, die jeweils zwei Zahlen ai und bi enthalten, die die durch die i-te Strasse verbundene Kreuzungen beschreiben.

Ausgabe

Gib für den t-ten der T Testfälle “Case #t: ” aus, gefolgt von p, die minimale Anzahl der Detektive, die Stofl anstellen muss. Es folgen p Zeilen, jede bestehend aus entweder einer oder zwei Zahlen, die Nummer(n) der Strasse(n), die der i-te Detektiv bewacht.

Limits

  • Für jede Teilaufgabe gilt: T = 100, 0 ≤ m ≤ (n)(n − 1) ⁄ 2 und 0 ≤ ai, bi < n (für 0 ≤ i < m)
  • Für Teilaufgabe 1 und 2 gilt: 0 ≤ n ≤ 103
  • Für Teilaufgabe 3 gilt: 0 ≤ n ≤ 102

Teilaufgabe 1 (10 Punkte)

Zunächst möchte Stofl nur die Strassen von Shibuya, einem Stadtviertel von Tōkyo überwachen lassen. Shibuya besteht aus einer grossen Kreuzung vor dem Bahnhof und einigen Strassen, die von dieser Kreuzung wegführen. Shibuya ist also ein Stern Sm.

Schreibe ein Programm, das eine optimale Platzierung von Detektiven findet.

Eingabe:

1
4 3
0 1
0 2
0 3

Ausgabe:

Case #0: 2
0 1
2

Bemerkung:

Die Kreuzung 0 ist im Zentrum des Sterns und jede andere Kreuzung ist genau einmal damit durch eine Strasse verbunden.
image/svg+xml 1 2 3 2 1 0 0

Teilaufgabe 2 (20 Punkte)

Nun möchte Stofl den Bezirk Edogawa überwachen. Die Stadtverwaltung von Tōkyo hat entschieden, in Edogawa Verkehrsmessungen durchzuführen. Dazu wurden systematisch Strassen gesperrt, sodass es zwischen je zwei Orten in Edogawa genau einen Pfad gibt.

Schreibe ein Programm, das Detektive in Edogawa optimal platziert. Beachte, dass gesperrte Strassen nicht in der Eingabe erscheinen.

Eingabe:

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

Ausgabe:

Case #0: 4
6
5 4
2 3
0 1
image/svg+xml 7 5 4 4 2 5 6 1 2 3 1 0 6 3 0

Teilaufgabe 3 (20 Punkte)

Nachdem die Detektive in Shibuya und Edogawa nichts gefunden haben, möchte Stofl nun ganz Tōkyo überwachen. Tōkyo ist gross und kompliziert, zusätzlich hat die Regierung in der Bucht Inseln angehäuft, die nur per Boot oder U-Bahn erreichbar sind. Insbesondere heisst das, dass der Graph nicht zusammenhängend sein muss.

Schreibe wieder ein Programm, das Detektive optimal platziert.

Eingabe:

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

Ausgabe:

Case #0: 4
6 4
2 5
1 3
0
Case #1: 3
0
1
2
image/svg+xml 1 2 3 2 1 0 0

image/svg+xml 7 5 4 4 2 5 6 1 2 3 1 0 6 3 0

Teilaufgabe 4 (50 Punkte)

Beschreibe die Lösungsidee und begründe die Korrektheit deiner Lösungen der Teilaufgaben 1-3. Für jede Begründung gibt es jeweils gleich viele Punkte wie die ursprüngliche Teilaufgabe. Da eine Lösung einer Teilaufgabe auch die vorherigen Teilaufgaben löst, reicht es, wenn du über die Lösung der schwierigsten Teilaufgabe argumentierst, d.h. wenn du Korrektheit des Programmes der Teilaufgabe 3 beweist, erhältst du 50 Punkte.

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

Hanabi

Im Sommer möchte Stofl seine Ferien gerne in Japan verbringen. Ihm gefallen besonders die fantastischen Feuerwerke (“hanabi” auf Japanisch), welche in Japan sehr häufig und einzigartig sind. Stofl möchte nun seine Reise so planen, dass er möglichst viele Feuerwerke zu sehen bekommt.

Du kannst annehmen, dass Japan aus n verschiedenen Städten besteht, welche von 0 bis n − 1 durchnummeriert sind. Die Städte sind mit m Strassen, welche jeweils in beide Richtungen befahrbar sind, miteinander verbunden. Für jede Strasse hast du die beiden Städte, welche sie verbindet, gegeben sowie die Zeit die man benötigt um von einer zur anderen Stadt zu gelangen. Du kannst annehmen, dass das Strassennetzwerk zusammenhängend ist – d.h. Zwischen zwei beliebigen Städten existiert immer ein Weg (möglicherweise als Sequenz mehrerer Strassen).

Zusätzlich bist du im Besitz einer Liste mit allen k Feuerwerkvorstellung, welche in Japan während Stofl’s Reise stattfinden. Für jede Vorstellung kennst du die Stadt, wo das Feuerwerk stattfinden wird sowie die Startzeit und die Länge der Vorstellung. Die Feuerwerke sind ebenfalls von 0 bis k − 1 durchnummeriert.

Um ein Feuerwerksvorstellung zu sehen (und auch zu geniessen), muss Stofl während der ganzen Vorstellung in der Austragungsstadt sein. Er kann nicht später ankommen und nicht vor Ende der Vorstellung abreisen, da er ansonsten den Start, resp. das grande finalissima verpassen würde. Er kann jedoch genau zur Startzeit anreisen und genau am Ende der Vorstellung wieder abreisen.

Deine Aufgabe ist es eine Reiseroute für Stofl zu planen, sodass er möglichst viele Feuerwerke sehen kann. Die Reise darf irgendwo in Japan beginnen und kann an einem beliebigen (anderen) Ort wieder aufhören. Da Stofl lange Ferien hat, kommt es ihm auch nicht drauf an wann die Reise beginnt und sie wieder zu Ende ist.

Teilaufgabe 1: Zwei Städte (15 Punkte)

In dieser Teilaufgabe kannst du annehmen, dass es nur zwei Städte gibt (n = 2) und maximal k ≤ 100 Feuerwerke.

Eingabe

Alle Teilaufgaben haben das gleiche Eingabeformat.

Auf der ersten Linie der Eingabe steht eine einzige Zahl t (1 ≤ t ≤ 100) – danach folgen t verschiedene Testfälle

Jeder Testfall beginnt mit einer Linie aus drei Ganzzahlen n, m und k (n ≥ 2, m ≥ n − 1, k ≥ 1).

Die zweite Line besteht aus einer Ganzzahl 0 oder 1, dem vorgegebenen Genauigkeitslevel der Ausgabe

Danach folgen m Linien, welche das Strassennetzwerk in Japan beschreiben. Die i-te dieser m Linien besteht jeweils aus drei Ganzzahlen ai, bi und ti (0 ≤ ai, bi ≤ n − 1, ti > 0) – die zwei Städte, welche durch die i-te Strasse verbunden werden und die Zeit um die Strecke zurückzulegen.

Du kannst annehmen, dass für jede Strasse gilt ai ≠ bi und dass alle unsortierten Paare (ai, bi) verschieden sind. Sprich: Die zwei Städte sind verschieden und es gibt maximal eine Strasse zwischen ihnen.

In den folgenden k Linien der Eingabe werden die Feuerwerke beschrieben. Die j-te dieser k Linien enthält das Zahlentripel cj, sj und dj – die Stadt wo das Feuerwerk stattfindet, die Startzeit (sj ≥ 0) sowie die Dauer ( dj >= 0).

Falls es mehrere Feuerwerke in der gleichen Stadt gibt, werden sie sich nie überlappen: Eine der beiden wird immer strikt nach der anderen beginnen.

Die Beschreibung der Feuerwerke ist in zufälliger Reihenfolge.

Du darfst annehmen, dass alle Eingabedaten in einen 32-bit signed integer passen.

Ausgabe

Für jeden Testfall sollst du eine Linie ausgeben falls g = 0 oder zwei Linien falls g = 1.

Für den i-ten Testfall soll auf der ersten Line die Zeichenkette “Case #i: h” stehen, wobei h die maximale Anzahl Feuerwerke ist, welche Stofl sehen kann.

Falls die Eingabe g = 1 ist, sollst du eine zweite Linie mit dem optimalen Reiseplan ausgeben.

Genauer gesagt sollst du h durch Leerzeichen getrennte Zahlen f1, …, fh ausgeben: Eine mögliche Liste von h Feuerwerksvorstellungen, welche Stofl in dieser Reihenfolge besuchen kann.

Beachte, dass die Testfälle 0 basiert sind!

Eingabe:

1
2 1 5
1
0 1 1
0 1 1
0 2 1
1 2 2
1 9 1
1 4 2

Ausgabe:

Case #0: 4
0 1 4 3

Bemerkung:

Beachte, dass wir hier die Feuerwerke auflisten, welche Stofl sehen kann.

Teilaufgabe 2: Zwei Feuerwerke (15 Punkte)

In dieser Aufgabe kannst du annehmen, dass n ≤ 100, k = 2, und g = 1. Zusätzlich weisst du, dass die beiden Feuerwerke in zwei verschiedenen Städten stattfinden.

Eingabe

Gleich wie in der ersten Teilaufgabe.

Ausgabe

Da g = 1 garantiert ist, sollst du in dieser Teilaufgabe genau zwei Linien für jeden Testfall ausgeben.

Das Ausgabeformat ** ist aber nicht das gleiche wie in der ersten Teilaufgabe**.

Wie in allen Teilaufgaben, deine Aufgabe ist es die Anzahl Feuerwerke, welche Stofl sehen kann, zu maximieren. Nun möchten wir ihm aber nur den Reiseplan ausgeben.

Auf der ersten Zeile des i-ten Testfalls soll immer die Zeichenkette “Case #i: l” stehen, l ≤ 100 ist die Anzahl Städte, welche Stofl besichtigen sollte um möglichst viele Feuerwerk zu sehen. Die zweite Linie der Ausgabe sollte den optimalen Reiseplan enthalten: l durch Leerzeichen getrennte Ganzzahlen c1, …, cl eine mögliche Liste von Städten, welche Stofl in dieser Reihenfolge besuchen kann.

Es gibt zwei Möglichkeiten:

  • Falls Stofl nur ein Feuerwerk sehen kann, sollte deine Ausgabe l = 1 sein und c1 sollte eine der beiden Städten mit Feuerwerken sein.
  • Falls Stofl beide Feuerwerke sehen kann sollte c1 die Stadt sein mit der früheren und cl mit der späteren Startzeit sein. Zusätzlich soll die Reihenfolge der Städte so sein, dass Stofl das ganze erste Feuerwerk sehen kann. Anschliessend die Städte in dieser Reihenfolge besucht und noch rechtzeitig zum zweiten Feuerwerk in cl eintrifft.

Beachte, dass wenn Stofl beide Feuerwerke sehen kann musst du den Wert für l NICHT optimieren. Du musst auch die Reisezeit NICHT optimieren. Falls es mehrere Lösungen gibt, gib eine davon aus.

Beachte, dass t 0 basiert ist!

Eingabe:

1
5 5 2
1
0 1 1
0 2 2
1 3 3
2 3 1
3 4 1
0 1 1
4 8 2

Ausgabe:

Case #0: 4
0 1 3 4

Bemerkung:

Beachte, dass wir hier die Städte auflisten, welche Stofl besuchen soll.

Teilaufgabe 3: Wenige Feuerwerke (30 Punkte)

In dieser Teilaufgabe kannst du annehmen, dass n ≤ 500 ist. Zusätzlich gilt, dass es in jeder Stadt höchstens ein Feuerwerk gibt.

Eingabe

Gleich wie in Teilaufgabe 1 und 2.

Ausgabe

Gleich wie in Teilaufgabe 1.

Beachte: Für das Generieren der Dateien und der Bewertung deiner Antwort werden etwa 10 Sekunden benötigt.

Teilaufgabe 4: Viele Feuerwerke (40 Punkte)

Dies ist eine theoretische Teilaufgabe. In jeder Stadt können es nehrere Feuerwerke stattfinden, welche sich nicht überlappen. Die Anzahl Feuerwerke ist um einiges grösser als die Anzahl Städte (z.B. k ≤ 100 000).

Entwickle einen möglichst schnellen Algorithmus, der solche Probleme lösen kann!

Beschreibe die Idee deiner Lösung, argumentiere, wieso sie korrekt ist und was ihre asymptotische Laufzeit und Speichernutzung ist.

Um viele Punkte zu erzielen wird erwartet, dass deine Lösung detailliert genug beschrieben wird und entweder ihre Implementierung damit offensichtlich ist oder du einen (Pseudo-)Code anhängst. Eine Erklärung, was der (Pseudo-)Code macht, ist ebenfalls notwendig.

Eingabe

Du kannst annehmen, dass die Eingabe in gleichem Format wie in Teilaufgaben 1, 2 und 3 gegeben sind.

Output

Du kannst annehmen, dass die Ausgabe in gleichem Format wie in Teilaufgaben 1, 2 und 3 geschieht.

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

Mahjong

Eines der populärsten Gesellschaftsspiele in Japan ist japanisches Mahjong, ein Legespiel mit Spielsteinen.

In dieser Aufgabe geht es um ein Solospiel, das man mit Mahjong-Steinen spielen kann.

Konkret hat es N Spielsteine, der Einfachheit halber von 0 bis N − 1 nummeriert, und drei Ablagestapel. Jeder der Ablagestapel besteht aus einer beliebigen Anzahl aufeinanderliegender Spielsteine (möglicherweise ist er auch leer, dann besteht er aus 0 Spielsteinen). Anfangs sind alle Steine auf die Stapel verteilt.

Folgendes wäre eine mögliche Anordnung für N = 6:

|0| | |
|5| |4|
|2|1|3|
+-+-+-+

Auf dem ersten Stapel liegen 3 Steine, zuoberst die 0, in der Mitte die 5 und ganz unten die 2. Der zweite Stapel besteht aus einem einzigen Stein, der 1 und der letzte Stapel hat oben die 4 und unten die 3.

Eine weitere Möglichkeit für N = 3 ist hier abgebildet:

| | | |
|2| | |
|0| |1|
+-+-+-+

Hier wäre der zweite Stapel leer.

Es gibt nur eine Art von erlaubten Spielzügen: Du kannst den obersten Stein eines nicht leeren Stapels auf einen beliebigen anderen Stapel legen.

Das hier ist ein erlaubter Spielzug, der die 1 entfernt und auf den ersten Stapel legt:

| | | |      |1| | |
|2| | |  =>  |2| | |
|0| |1|      |0| | |
+-+-+-+      +-+-+-+

Das hier nicht, da die 2 unten in den dritten Stapel eingefügt wurde und nicht draufgelegt wurde:

| | | |      | | | |
|2| | |  =>  | | |1|
|0| |1|      |0| |2|
+-+-+-+      +-+-+-+

Ziel des Spiels ist es, durch wiederholtes Ausführen dieser Spielzüge alle Steine sortiert auf einem der Stapel liegen zu haben. Für N = 4 ist dies genau bei einer der folgenden Anordnungen erreicht:

|0| | |      | |0| |     | | |0|
|1| | |      | |1| |     | | |1|
|2| | |      | |2| |     | | |2|
|3| | |      | |3| |     | | |3|
+-+-+-+      +-+-+-+     +-+-+-+

Dies sind auch alle möglichen Anordnungen für N = 4. Sortiert heisst hier, dass die 0 zuoberst liegen muss und der grösste Stein zuunterst.

Teilaufgabe 1 (25 Punkte)

Gegeben eine Anordnung der n Steine, gib eine mögliche Zugfolge aus, um sie in eine der drei Endpositionen zu bringen.

Beachte, dass die von dir berechnete Zugreihenfolge nicht die kürzest mögliche sein muss. Damit die Ausgabe nicht zu gross wird, erlauben aber höchstens 100 000 Züge und garantieren, dass es immer mit weniger als 100 000 Zügen möglich ist.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle in folgendem Format:

Die erste Zeile des Testfalls enthält N, die Anzahl Steine. Es folgt eine zweite Zeile mit A, der Anzahl Steine auf dem ersten Stapel, gefolgt von A Zahlenwerten a0, …, aA − 1, den Werten auf dem ersten Stapel. Die dritte Zeile ist analog, zuerst kommt B, dann B Zahlenwerte b0, …, bB − 1 mit den Werten auf dem zweiten Stapel. Die vierte Zeile enthält C, gefolgt von C Zahlenwerten c0, …, cC − 1.

Die Steine a0, b0 und c0 sind jeweils die obersten Steine, die Steine aA − 1, bB − 1 und cC − 1 jeweils die untersten.

Beachte, dass A, B und/oder C auch 0 sein können und der Stapel dann leer ist. In diesem Fall hat der Stapel keinen untersten und obersten Stein.

Es gilt A + B + C = N, sowie dass alle 0 ≤ ai, bi, ci < N verschieden sind.

Ausgabe

Gib für den i-ten Testfall eine Zeile “Case #i: M” aus, wobei M die Anzahl Züge ist, die du für deine Lösung benötigst. Es folgen M Zeilen, mit jeweils zwei Zahlen s und t, was bedeutet, dass der oberste Stein von Stapel Nummer s auf Stapel Nummer t gelegt wurde.

Limits

Es gibt T = 100 Testfälle. In allen gilt 3 ≤ N ≤ 100.

In der Ausgabe muss M ≤ 100 000 gelten.

Beispiel

Eingabe:

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

Ausgabe:

Case #0: 3
0 1
0 1
0 1
Case #1: 10
1 0
1 0
1 2
0 2
0 2
0 1
0 1
0 2
1 2
1 2

Bemerkung:

Case #0: Alle Steine liegen auf Stapel Nummer 0 in der verkehrten Reihenfolge (2 zuoberst, 1 in der Mitte und 0 ganz unten). Um die Reihenfolge umzudrehen legen wir sie der Reihe nach auf Stapel 1. Die Stapel verändern sich so:
start: |2 1 0| || ||  → 
0->1:  |1 0|  |2| ||  → 
0->1:  |0|  |1 2| ||  → 
0->1:  || |0 1 2| ||.
Case #1: Hier sind 9 Steine auf die Stapel verteilt. Der Algorithmus der Ausgabe verändert diese wie folgt:
start: |0 1 2|  |3 4 5|  |6 7 8|  → 
1->0:  |3 0 1 2|  |4 5|  |6 7 8|  → 
1->0:  |4 3 0 1 2|  |5|  |6 7 8|  → 
1->2:  |4 3 0 1 2| ||  |5 6 7 8|  → 
0->2:  |3 0 1 2| ||  |4 5 6 7 8|  → 
0->2:  |0 1 2| ||  |3 4 5 6 7 8|  → 
0->1:  |1 2|  |0|  |3 4 5 6 7 8|  → 
0->1:  |2|  |1 0|  |3 4 5 6 7 8|  → 
0->2:  ||  |1 0| |2 3 4 5 6 7 8|  → 
1->2:  ||  |0| |1 2 3 4 5 6 7 8|  → 
1->2:  || || |0 1 2 3 4 5 6 7 8|.

Teilaufgabe 2 (25 Punkte)

Da das Spiel für einige immer zu kompliziert ist, möchtest du eine Anleitung erstellen, wie man es lösen kann. Die Anleitung ist eine Tabelle, welche für jede mögliche Anordnung (abgesehen von der Zielposition) einen Zug empfiehlt.

Jede Anordnung sollte mit deiner Anleitung in die Zielposition zu überführen sein, in dem man deinen empfohlenen Zug ausführt, eine neue Anordnung erhält und für diese einen neuen Zug nachschaut. Das wird wiederholt bis eine Endanordnung erreicht ist.

In deiner Anordnung sollte garantiert sein, dass nach einer endlichen Anzahl Schritte die Zielanordnung erreicht wurde. Man sollte also nicht in einer Endlosschleife stecken bleiben.

Eingabe

Die erste Zeile enthält die Anzahl Testfälle T. Es folgen T Testfälle mit nur einer Zahl N.

Die Eingabe, die du hier herunterladen kannst, ist immer gleich: Es gilt T = 6 und 1 ≤ N ≤ 6. In der Eingabe kommen alle N von 1 bis und mit 6 der Reihe nach aufsteigend sortiert vor.

Ausgabe

Mehrere Zeilen im Format:

  • a0 a1 ai − 1 | ai aj − 1 | aj an − 1: b -> c, falls du von dieser Stellung den obersten Stein von Stapel b auf Stapel c legen möchtest, oder
  • a0 a1 ai − 1 | ai aj − 1 | aj an − 1: done, falls das Spiel schon zu Ende ist (d.h. genau dann wenn alle Steine auf einem Stapel liegen und dieser sortiert ist).

Alle Stellungen müssen verschieden sein und es müssen alle möglichen Stellungen vorkommen. Es gibt (N + 2)! ⁄ 2 verschiedene Stellungen (Das Ausrufezeichen steht für Fakultät, kurz (N + 2) ≠ 1⋅2⋅3⋅4⋅…⋅(N − 1)⋅N⋅(N + 1)⋅(N + 2)).

Limits

Es gilt T = 6 und 1 ≤ N ≤ 6. In der Eingabe kommen alle N von 1 bis und mit 6 der Reihe nach aufsteigend sortiert vor.

Beispiel

Eingabe:

2
1
2

Ausgabe:

Case #0:
0 | |: done
| 0 |: done
| | 0: done
Case #1:
0 1 | |: done
| 0 1 |: done
| | 0 1: done
1 0 | |: 0 -> 1
| 1 0 |: 1 -> 2
| | 1 0: 2 -> 0
0 | 1 |: 0 -> 1
| 0 | 1: 1 -> 2
1 | | 0: 2 -> 0
1 | 0 |: 1 -> 0
| 1 | 0: 2 -> 1
0 | | 1: 0 -> 2

Bemerkung:

Für die Anordnung “0 1 | |” wird zuerst die 1 nach rechts verschoben (4. Regel) und man erhält “0 | 1 |”. Danach die 0 nach rechts (7. Regel) und man erhält “| 1 0 |” und ist fertig.

Teilaufgabe 3 (20 Punkte)

Es gibt eine noch schwierigere Variante des Spiels: Du kennst nicht die vollständige Anordnung eines Stapels, sondern nur den Wert des obersten Steins. (Falls der Stapel leer ist, weisst du, dass er leer ist.) Ebenfalls weisst du nicht, wie hoch der Stapel ist.

Erstelle wieder eine Anleitung, wie in der vorherigen Teilaufgabe.

Da du mit dieser Information nicht wissen kannst, wann das Spiel vorbei ist, wird das Spiel automatisch beendet, sobald alle Steine auf einem Stapel liegen und dieser sortiert ist.

Falls z.B. bei N = 3 nur ein Stapel nicht leer ist und dieser zuoberst eine 0 hat, dann weisst du deshalb, dass der Stapel in der Reihenfolge “0 2 1” ist, denn mit der Reihenfolge “0 1 2” wäre das Spiel schon vorbei.

In dieser Aufgabe sind auch Teilpunkte möglich: Für 3 korrekte Testfälle erhälst du 5 Punkte. Jeder weitere korrekte Testfall gibt 5 zusätzliche Punkte, bis maximal 15 Punkte. Für die volle Punktzahl von 20 Punkten müssen alle Testfälle korrekt gelöst sein.

Eingabe

Gleich wie in Teilaufgabe 2, nur mit T = 8 statt T = 6. Insbesondere ist dir auch hier schon die Eingabe schon im Voraus bekannt.

Ausgabe

Gleich wie in Teilaufgabe 2, nur dass du den Stapel anders beschreibst: Eine Anordnung besteht nun aus 3 “Zahlen”, wobei im Falle eines leeren Stapels die “Zahl” auch “-” sein kann. (Anstatt “-” wird vom Grader auch “-1” akzeptiert.)

Einige Anordnungen fallen nun zusammen, es gibt noch genau 3N + 3N⋅(N − 1) + N⋅(N − 1)⋅(N − 2) verschiedene Anordnungen.

Beispiel

Eingabe:

2
1
2

Ausgabe:

Case #0:
0 - -: 0 -> 1
- 0 -: 0 -> 1
- - 0: 0 -> 1
Case #1:
0 - -: 0 -> 1
- 0 -: 0 -> 1
- - 0: 0 -> 1
1 - -: 0 -> 1
- 1 -: 1 -> 2
- - 1: 2 -> 0
0 1 -: 0 -> 1
- 0 1: 1 -> 2
1 - 0: 2 -> 0
1 0 -: 1 -> 0
- 1 0: 2 -> 1
0 - 1: 0 -> 2

Bemerkung:

Beachte, dass das Spiel im ersten Testfall sowieso immer vorbei ist. Der Zug wird deshalb nie ausgeführt.

Im zweiten Testfall ist das Spiel ebenfalls schon vorbei, wenn nur eine 0 sichtbar ist.

Dies sind Spezialfälle für N ≤ 2. Bei N > 2 tritt dieser Spezialfall aber nicht mehr auf; dann gäbe es eine gültige Anordnung wie z.B. 0 3 1 4 2.

Limits

Es gilt T = 8 sowie 1 ≤ N ≤ 8.

Teilaufgabe 4 (30 Punkte)

Gleich wie Teilaufgabe 3, nur ist dies eine theoretische Aufgabe.

Schreibe eine Funktion f(n, a, b, c), welche für n Spielsteine die drei obersten Zahlen a, b, c der Stapel entgegennimmt (leere Stapel werden mit  − 1 encodiert) und entweder 01, 10, 12, 21, 02 oder 20 zurückgibt (für 0 → 1, 1 → 0, 1 → 2, etc.).

Da die Ausgabe diesmal nicht mehr so gross ist und nicht mehr alle Eingaben berechnet werden, sind im Vergleich zu Teilaufgabe 3 die Limits viel grösser. Du sollst deshalb die asymptotische Laufzeit von f in Abhängigkeit von n optimieren.

Da es eine theoretische Aufgabe ist, sollst du begründen, wieso deine Lösung korrekt ist und welche asymptotische Laufzeit deine Lösung hat. Die Funktion kannst du in einer beliebigen Programmiersprache oder in Pseudocode schreiben.

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

Samurai

Stofl ist von Japanischer Kultur und Geschichte fasziniert. Vor allem interessiert er sich für die Samurai. Er und seine Freunde entscheiden sich, einige der Fähigkeiten der Samurai zu lernen. Damit das Ganze noch mehr Spass macht, haben Stofl und seine Freunde ein Spiel erfunden, das ihnen hilft, diese Fähigkeiten schneller zu lernen.

Es gibt n Mäuse die das Spiel spielen und m Fähigkeiten, die zu lernen sind. Die Fähigkeiten haben verschiedene Schwierigkeiten: um die i-te Fähigkeit zu meistern, muss man si Tage üben.

Am Anfang des Spieles wählt ein Spieler eine Zielfähigkeit t. Jeden Tag wählt jede Maus eine der m Fähigkeiten, die sie an diesem Tag trainieren will. Wer die Zielfähigkeit zuerst meistert, erhält einen Punkt und kann die nächste Zielfähigkeit wählen. Das Ganze geht so weiter, bis jede Fähigkeit von jemandem gemeistert wurde. Wer am meisten Punkte hat, gewinnt.

Falls mehrere Mäuse die Fähigkeit am gleichen Tag lernen, wird der Punkt gleichförmig zwischen ihnen aufgeteilt und der Gewinner mit dem nächsthöheren Index als die letzte Maus, die ein Ziel gewählt hat, darf die nächste Zielfähigkeit auswählen (nach der n − 1-ten Maus kommt wieder Maus 0).

Die Mäuse können eine beliebige Fähigkeit trainieren, nicht nur das Ziel (sonst würde das Spiel keinen Spass machen, weil jeder gleich viele Punkte hätte). Aber man darf keine Fähigkeit meistern, bevor sie als Ziel gewählt wurde (es muss noch mindestens ein Tag Übung übrig sein). Beachte, dass es nicht unbedingt optimal ist, immer die Zielfähigkeit zu üben.

Das Spiel wird mehrere Male gespielt, ohne dass dein Programm neu gestartet wird. So kannst du die anderen Programme analysieren und eine Gegenstrategie entwickeln (wenn du willst. Du kannst auch jedes Spiel separat behandeln).

Protokoll

Die Kommunikation zwischen Programm und Server wird via Stdin / Stdout gemacht.

Am Start erhält dein Programm generelle Informationen über das Spiel:

Eine Zeile mit nm, die Anzahl Mäuse n und die Anzahl Fähigkeiten m. Dein Spieler ist immer die Maus mit der Nummer 0. Auf der nächsten Zeile hat es m Zahlen (mit Leerzeichen getrennt) si, die Schwierigkeiten der Fähigkeiten.

Danach fängt das Spiel an. In jeder Runde erfährst du zuerst die vorherigen Aktionen aller Spieler, dann solltest du ausgeben, was du machst:

Auf der ersten Zeile hat es eine Zahl t, das aktuelle Ziel. Werte von t unter null haben eine besondere Bedeutung (siehe weiter unten). Auf der nächsten Zeile hat es n Zahlen (mit Leerzeichen getrennt) pi, die Fähigkeit, die der i-te Spieler trainierte. p0 wird die Fähigkeit sein, die du in der letzten Runde gewählt hast. Dann sollst du eine Zeile mit r ausgeben, die Fähigkeit, die du trainieren willst.

Bitte beachte, dass es in der ersten Runde des Spieles keine vorhergehende Runde gibt, und somit auch keine Fähigkeiten, die Trainiert wurden. Alle pi sind dann  − 1.

Es gibt einige Sonderwerte für t:

t =  − 1 bedeutet dass du das nächste Ziel wählen darfst. Die nächste Zeile ist gleich wie für eine normale Runde. Du musst dann zwei Zeilen ausgeben, die erste mit t, das neue Ziel, und die zweite mit r, die Fähigkeit, die du trainieren willst.

t =  − 2 bedeutet, dass das Spiel zurückgesetzt wurde und ein neues Spiel beginnt. Alle Parameter bleiben gleich (n, m, si), aber Fortschritt aller Spieler wird zurückgesetzt. Die nächste Zeile ist wie normal (damit du weisst, wer in der letzten Runde was trainierte) aber du musst nichts ausgeben. Die nächste Eingabe ist dann ein neues Spiel mit den gleichen Parametern n, m und si.

t =  − 3 bedeutet, dass die Ausführung vorbei ist. Dein Programm sollte terminieren.

Limits

  • 2 ≤ n ≤ 100
  • 2 ≤ m ≤ 1000
  • 1 ≤ si ≤ 1000
  • 0 ≤ pi < m
  •  − 3 ≤ t < m

Beispiel

> : 3 10
> : 5 8 10 2 6 4 1 9 7 3
> : -1
> : -1 -1 -1
< : 8
< : 0
> : 8
> : 0 3 8
< : 0
[...]
> : 8
> : 5 5 8
< : 2
> : -1
> : 2 0 8
< : 3
< : 4
> : 1
> : 4 3 3
< : 5
[...]
> : 4
> : 7 9 9
< : 7
> : -2
> : 4 7 4
> : 3 10
> : 5 8 10 2 6 4 1 9 7 3
> : 9
> : -1 -1 -1
< : 5
> : 9
> : 5 3 9
< : 0
[...]
> : 7
> : 7 7 7
< : 2
> : -3

Teilaufgabe 1: die Regeln befolgen (25 Punkte)

Schreibe einen Bot der die Regeln befolgt und den Sample Bot besiegen kann.

Teilaufgabe 2: Kreativitätswettbewerb (75 Punkte)

Du spielst gegen die anderen Teilnehmer der SOI. Am SOI-Tag wird dein Programm in einem Wettbewerb teilnehmen, um das beste Programm zu bestimmen. Du darfst bis zu drei Programmen einschicken. Dein bestes Programm wird für das Ranking verwendet. Mach ein zip-Archiv, wenn du mehrere Dateien einschickst.

Tipps

Für interaktive Aufgaben ist es wichtig, nach jedem Zug, den Ausgabebuffer zu flushen, damit der Server deine Ausgabe sieht.

Verwende dafür:

  • C/C++: fflush(stdout);
  • C++: cout << flush; (nicht nötig, wenn du danach mit cin etwas liest)
  • Pascal: flush(output);
  • In anderer Programmiersprachen gibt es ähnliche Befehle.

Dazu ist es wichtig, dass du nicht auf mehr Zeichen vom Server wartest, als du als Input erhältst. Als Beispiel verursachen Leerzeichen oder Zeilenenden in C häufig Fehler. Wenn du also die letzte Variable im Input mit “scanf("%d ", &x);” liest, wird dein Programm auf das nächste Zeichen, dass kein Leerzeichen oder Zeilenende ist. So ein Zeichen erhältst du erst in der nächsten Runde. Um das zu lösen, verwende “scanf("%d", &x);” (keine Leerzeichen nach dem “%d”).

Beispielbots, Server und Visualisierung

Folgendes Material wird zur Verfügung gestellt:

  • Beispielbots in verschiedenen Programmiersprachen
  • Ein Server-Programm, mit dem du dein Programm testen kannst
  • Eine Visualisierung um die simulierten Spiele darzustellen
  • Einige closed-source Spieler. Verwende samurai://soi.ch:9929/name als Spieler-Kommando, wobei name entweder b1, b2, b3, b4 oder b5 sein kann.

Die Ressourcen kannst du hier herunterladen.

Schnellstart

Um den Server auszuführen brauchst du Java (Version 7 oder höher). Das Serverprogramm ist in der Datei samurai.jar und die restlichen Dateien sind Konfigurationsdateien und Beispielbots.

Wenn du samurai.jar ausführst, wird das Spiel in samurai.txt simuliert, mit Spielern aus players.txt. Du kannst den Server in der Konsole (Windows: cmd, Mac: terminal, Linux: shell) auszuführen, um Argumente zu übergeben (java -jar samurai.jar arguments). Du findest mögliche Argumente in der Datei usage.md.

Du kannst die Fähigkeitsstufen in der Datei samurai.jar ändern. Um anzugeben, welche Bots du ausführen willst, kannst du sie in players.txt angeben und die Anzahl Spieler ober anpassen.

Verwende folgende Kommandos, je nach Programmiersprache, die du verwendet hast:

  • Python: python path/to/file
  • Java: java -jar program.jar oder java package.MainClass
  • Kompiliertes Programm (z.B. C++): ./path/to/program

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)sushi (100)wagashi (100)cheesep… (100)
cheesepatrol
hanabi (100)mahjong (100)samurai (100)
loading ...