Erste Runde SOI 2017

Ü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!

Informationen zur Teilnahme an der Schweizer Informatikolympiade findest du hier.

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

AufgabeSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5Subtask 6
numberriddle (0/100)0/250/250/250/25
superpowers (0/100)0/200/200/200/200/20
cupsort (0/100)0/100/200/200/200/30
funny (0/100)0/100/100/100/250/100/35
dissertation (0/100)0/100/200/200/200/30
submarine (0/100)0/250/250/50

Zahlenrätsel

Maus Amir liebt Rätsel und Mathematik. Wenn er alleine Zug fährt, denkt er sich kleine Rätselspiele aus, um sich die Zeit zu vertreiben. Sein Lieblingsrätsel ist das Zahlenrätsel. Das Ziel des Spiels ist das Erzeugen einer Gleichung aus zufällig gewählten Zahlen. Das Spiel kann beliebig in der Schwierigkeit variiert werden; Amir bevorzugt eine eher einfache Variante. Er denkt sich eine Liste von Zahlen aus und versucht durch das Einfügen von ‘+’ und ‘-‘ einen bestimmten Wert zu erreichen. Dabei verwendet er immer alle Zahlen und das ‘-‘ verwendet er ausschliesslich als Operator und nicht als Vorzeichen.

Teilaufgabe 1: Aufwärmrunde (25 Punkte)

Maus Amir fängt immer mit einer einfachen Aufgabe an. Er wählt das zufällige Zahlenpaar n0, n1 und einen Zielwert R. Nun versucht er entweder durch Addition der beiden Werte oder durch Subtraktion des zweiten vom ersten Wert, die Zahl R zu erreichen.

Eingabe

Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus zwei Zeilen. Die erste Zeile enthält zwei Ganzzahlen N, die Anzahl zufällig gewählter Zahlen und R, der Zielwert. Die zweite Zeile enthält N Ganzzahlen ni, die Zahlen die Amir zueinander addiert oder voneinander subtrahiert.

Ausgabe

Für den i-ten Testfall wird eine einzelne Zeile mit “Case #i: YES” erwartet, wenn R erreicht wird, ansonsten wird “Case #i: NO” erwartet.

Limits

  • T = 100
  • N = 2
  • 0 ≤ R = 15
  • 0 ≤ ni ≤ 10

Beispiel

Eingabe:

3
2 5
2 3
2 5
8 3
2 6
2 8

Ausgabe:

Case #1: YES
Case #2: YES
Case #3: NO

Bemerkung:

Die ersten zwei Testfälle sind lösbar mit 2 + 3 = 5 und 8 − 3 = 5.
Beim dritten Fall haben wir 2 + 8 = 10 oder 2 − 8 =  − 6 beide sind ungleich 6.

Teilaufgabe 2: Eine Subtraktion (25 Punkte)

Maus Amir ist sehr gut im Kopfrechnen. Mehrere dutzend Zahlen zu addieren ist für ihn ein Kinderspiel. Allerdings mag er lieber Additionen als Subtraktionen. Wie zuvor denkt er sich zufällige Zahlen aus. Unter Verwendung aller Zahlen und höchstens einer Subtraktion, ist es möglich den Wert R zu erreichen?

Eingabe

Das Eingabeformat ist gleich wie bei Teilaufgabe 1. Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus zwei Zeilen. Die erste Zeile enthält zwei Ganzzahlen N, die Anzahl zufällig gewählter Zahlen und R, der Zielwert. Die zweite Zeile enthält N Ganzzahlen ni, die Zahlen die Amir zu einander addiert oder voneinander subtrahiert.

Ausgabe

Das Ausgabeformat ist gleich wie bei Teilaufgabe 1. Für den i-ten Testfall wird eine einzelne Zeile mit “Case #i: YES” erwartet wenn R erreicht wird, ansonsten wird “Case #i: NO” erwartet.

Limits

  • T = 100
  • 2 ≤ N ≤ 100
  • 0 ≤ R = 10 000
  • 0 ≤ ni ≤ 100

Beispiel

Eingabe:

3
2 5
2 3
3 5
3 8 10
3 5
8 3 10

Ausgabe:

Case #1: YES
Case #2: YES
Case #3: NO

Bemerkung:

Case #1: 2 + 3 = 5 ist noch immer möglich.
Case #2: 3 − 8 + 10 = 5 es wird nur eine Subtraktion verwendet.
Case #3:  − 8 + 3 + 10 = 5 ist nicht erlaubt. Das “ − ” müsste als Vorzeichen verwendet werden.

Teilaufgabe 3: Zwei Subtraktionen (25 Punkte)

Maus Amir weiss, dass es um so wahrscheinlicher ist eine Gleichung zu finden, je mehr Operationen zugelassen werden. Trotz seiner Abneigung gegenüber Subtraktionen, kann er sich durchringen bis zu zwei Subtraktionen in die Gleichung einzubauen. Wie zuvor wählt Amir zufällige Zahlen und platziert Operatoren dazwischen. Ist es möglich, unter Verwendung aller Zahlen, mit höchstens zwei Subtraktionen den Zielwert R zu erreichen?

Eingabe

Das Eingabeformat ist gleich wie bei Teilaufgabe 1. Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus zwei Zeilen. Die erste Zeile enthält zwei Ganzzahlen: N, die Anzahl zufällig gewählter Zahlen und R, den Zielwert. Die zweite Zeile enthält N Ganzzahlen: ni, die Zahlen die Amir zueinander addiert oder voneinander subtrahiert.

Ausgabe

Das Ausgabeformat ist gleich wie bei Teilaufgabe 1. Für den i-ten Testfall wird eine einzelne Zeile mit “Case #i: YES” erwartet, wenn R erreicht wird. Ansonsten wird “Case #i: NO” erwartet.

Limits

  • T = 100
  • 2 ≤ N ≤ 100
  • 0 ≤ R = 10000
  • 0 ≤ ni ≤ 100

Beispiel

Eingabe:

2
3 5
16 8 3
3 8
16 10 2

Ausgabe:

Case #1: YES
Case #2: YES

Bemerkung:

Case #1: 16 − 8 − 3 = 5
Case #2: 16 − 10 + 2 = 8 weniger Subtraktionen sind noch immer erlaubt.

Teilaufgabe 4: Unzählige Möglichkeiten (25 Punkte)

Maus Stofl erfährt von Amirs Spiel und sie beginnen, es miteinander zu spielen. Anders als in den vorangehenden Teilaufgaben sind nun beliebig viele Subtraktionen möglich. Es müssen weiterhin alle Zahlen verwendet werden.

Maus Stofl ist ein MOI (Mouse Olympiad in Informatics) Teilnehmer. Durch das Studieren der Unterlagen und die Teilnahme an Workshops kennt er eine elegante Lösung.

Eingabe

Das Eingabeformat ist gleich wie bei Teilaufgabe 1. Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus zwei Zeilen. Die erste Zeile enthält zwei Ganzzahlen: N, die Anzahl zufällig gewählter Zahlen und R, den Zielwert. Die zweite Zeile enthält N Ganzzahlen: ni, die Zahlen die Amir zueinander addiert oder voneinander subtrahiert.

Ausgabe

Das Ausgabeformat ist gleich wie bei Teilaufgabe 1. Für den i-ten Testfall wird eine einzelne Zeile mit “Case #i: YES” erwartet, wenn R erreicht wird. Ansonsten wird “Case #i: NO” erwartet.

Limits

  • T = 100
  • 2 ≤ N ≤ 100
  • 0 ≤ R ≤ 10 000
  • 0 ≤ ni ≤ 100

Beispiel

Eingabe:

4
3 5
16 8 3
3 8
16 10 2
3 8
4 2 2
3 8
2 4 6

Ausgabe:

Case #1: YES
Case #2: YES
Case #3: YES
Case #4: NO

Bemerkung:

Case #1: 16 − 8 − 3 = 5
Case #2: 16 − 10 + 2 = 8
Case #3: 4 + 2 + 2 = 8
Case #4:  − 2 + 4 + 6 = 8 ist nicht erlaubt. Das “ − ” darf nicht als Vorzeichen verwendet werden.

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

Superkräfte

Maus Stofl hat ein Gerät erfunden, mit dem er Superhelden dazu bringen kann, die Seite zu wechseln (die “Guten” werden zu “Bösen” und umgekehrt). Er hat nun vor, dieses Gerät am nächsten Superhelden Kongress einzusetzen. Hilf ihm bei seinem Vorhaben, damit die bösen Superhelden in Zukunft keine Chance mehr haben.

Jeder Superheld hat eine Stärke k (eine Ganzzahl). Wenn er gut ist, ist k > 0, falls er böse ist, gilt k < 0. Wendet Stofl nun sein Gerät auf einen Superhelden an, ist seine Stärke neu  − k. Um nun zu bestimmen, wer die Überhand hat, summiert Stofl alle Kräfte auf. Hilf ihm dabei, dass diese Summe S möglichst gross wird.

Teilaufgabe 1 (20 Punkte)

Du musst genau C mal einen Superhelden auswählen, der die Seite wechselt. Du kannst einen Helden mehrmals auswählen.

Eingabe

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

Für jeden Testfall folgt nun eine Zeile. Auf dieser Zeile steht eine Zahl C (s. Beschreibung), dann eine Zahl N (die Anzahl Superhelden), gefolgt von N durch Leerzeichen getrennte Zahlen, die Stärken der Superhelden.

Ausgabe

Gib für jeden Testfall eine Zeile im Format “Case #i: S” aus, wobei i der Nummer des Testcases (für den ersten Testcase ist i = 1) entspricht und S der gesuchten Summe.

Limits

  • T = 100
  • 0 ≤ C ≤ 104
  • 1 ≤ N ≤ 104
  • 1 ≤ |k| ≤ 106

Beispiele

Eingabe:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Ausgabe:

Case #1: 15
Case #2: 15
Case #3: 17

Bemerkung:

Wir wählen jeweils die Superhelden mit folgenden Stärken:
Case #1: -3, 1, -7
Case #2: 1, 1
Case #3: -7, 1, 1, 3, 3

Teilaufgabe 2 (20 Punkte)

Du musst genau C verschiedene Superhelden auswählen, die die Seite wechseln.

Eingabe

Die Eingabe ist gleich wie in Teilaufgabe 1.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 1.

Achtung: Die gesuchte Summe kann teilweise zu gross für eine 32-Bit Zahl sein (verwende z.B. in C++ daher long long int statt int).

Limits

  • T = 100
  • 0 ≤ C ≤ 104
  • 1 ≤ N ≤ 104
  • C ≤ N
  • 1 ≤ |k| ≤ 106

Beispiele

Eingabe:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Ausgabe:

Case #1: 15
Case #2: 9
Case #3: -3

Bemerkung:

Wir wählen jeweils die Superhelden mit folgenden Stärken:
Case #1: -3, 1, -7
Case #2: 1, 2
Case #3: -7, 1, 2, 3, 4

Teilaufgabe 3 (20 Punkte)

Du musst genau C aufeinanderfolgende Superhelden auswählen, die die Seite wechseln. Die Superhelden stehen in einer Linie, d.h. der erste und der letzte Held sind nicht benachbart.

Eingabe

Die Eingabe ist gleich wie in Teilaufgabe 2.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 2.

Limits

  • T = 100
  • 0 ≤ C ≤ 106
  • 1 ≤ N ≤ 106
  • C ≤ N
  • 1 ≤ |k| ≤ 106

Beispiele

Eingabe:

3
3 5 4 -3 1 2 -7
2 5 1 2 3 4 5
5 5 -7 1 2 3 4

Ausgabe:

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

Bemerkung:

Wir wählen jeweils die Superhelden mit folgenden Stärken:
Case #1: 1, 2, -7
Case #2: 1, 2
Case #3: -7, 1, 2, 3, 4

Teilaufgabe 4 (20 Punkte)

Du kannst eine beliebige Anzahl aufeinanderfolgende Superhelden auswählen, die die Seite wechseln.

Eingabe

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

Für jeden Testfall folgt nun eine Zeile. Auf dieser Zeile steht eine Zahl N (die Anzahl Superhelden), gefolgt von N durch Leerzeichen getrennte Zahlen, die Stärken der Superhelden.

Ausgabe

Gib für jeden Testfall eine Zeile im Format “Case #i: S” aus, wobei i der Nummer des Testcases (für den ersten Testcase ist i = 1) entspricht und S der gesuchten Summe.

Limits

  • T = 100
  • 1 ≤ N ≤ 104
  • 1 ≤ |k| ≤ 106

Beispiele

Eingabe:

3
5 4 -3 1 2 -7
5 1 2 3 4 5
5 -7 1 2 3 4

Ausgabe:

Case #1: 11
Case #2: 15
Case #3: 17

Bemerkung:

Wir wählen jeweils die Superhelden mit folgenden Stärken:
Case #1: -3, 1, 2, -7
Case #2: Wir wählen keinen Superhelden
Case #3: -7

Teilaufgabe 5 (20 Punkte)

Das selbe wie bei Teilaufgabe 4, aber es gibt mehr Superhelden.

Eingabe

Die Eingabe ist gleich wie in Teilaufgabe 4.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 4.

Limits

  • T = 100
  • 1 ≤ N ≤ 106
  • 1 ≤ |k| ≤ 106

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

Becher sortieren

Maus Stofl macht bei einem Bechersortier-Wettbewerb mit, wo er N Becher auf dem Tisch vor sich hat und sie nach einem bestimmten Muster sortieren muss. Er kann zwei nebeneinander stehende Becher sehr schnell vertauschen. Aber um den Wettbewerb zu gewinnen reicht das nicht, er muss auch die Anzahl solcher Vertauschungen minimieren, die er braucht um die verlangte Reihenfolge zu erreichen. Deshalb bittet er dich um Hilfe, um die kleinstmögliche Anzahl Vertauschungen in den verschiedenen Runden des Wettbewerbs zu bestimmen.

Teilaufgabe 1: Höchstens ein Zug (10 Punkte)

Alle Becher sind entweder blau oder rot. Stofl muss die roten Becher links von den blauen bringen. Ist dies mit  ≤ 1 Zug möglich? Die Farben rot und blau sind als die Zahlen 0 und 1 dargestellt in der Eingabe.

Eingabe

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

Für jeden Testfall folgen nun zwei Zeilen. Auf der jeweils ersten Zeile steht eine Zahl N, die Anzahl Becher auf dem Tisch. Auf der jeweils zweiten Zeile folgen N durch Leerzeichen getrennte Zahlen ci, i von 1 bis N, Zahlen für die Farben der Becher.

Ausgabe

Gib für jeden Testfall eine Zeile aus, nämlich “Case #i: YES” falls es mit  ≤ 1 Zügen möglich ist, “Case #i: NO” sonst.

Limits

  • T = 100
  • 1 ≤ N ≤ 104
  • 0 ≤ ci ≤ 1 für alle i von 1 bis N

Beispiele

Eingabe:

3
5
0 0 1 0 1
5
1 1 1 0 1
4
0 0 0 0

Ausgabe:

Case #1: YES
Case #2: NO
Case #3: YES

Bemerkung:

Case #1: vertausche den dritten und vierten Becher
Case #2: unmöglich mit nur einem Zug
Case #3: ist schon in der gewünschten Reihenfolge

Teilaufgabe 2: Zwei Farben (20 Punkte)

Wieder sind alle Becher blau oder rot und Stofl muss alle roten links von den blauen hinstellen. Aber jetzt will er die genaue kleinstmögliche Anzahl Vertauschungen dafür wissen.

Eingabe

Das Eingabeformat ist gleich wie in Teilaufgabe 1.

Ausgabe

Gib für jeden Testfall eine Zeile im Format “Case #i: S” aus, wobei i der Nummer des Testfalls (für den ersten Testfall ist i = 1) entspricht und S der gesuchten Anzahl.

Limits

Die Limits sind gleich wie in Teilaufgabe 1.

Beispiele

Eingabe:

3
5
0 0 1 0 1
5
1 1 1 0 1
4
0 0 0 0

Ausgabe:

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

Bemerkung:

Case #1: vertausche den dritten und vierten Becher
Case #2: vertausche den dritten und vierten Becher, dann den zweiten und dritten, dann den ersten und zweiten
Case #3: ist schon in der gewünschten Reihenfolge

Teilaufgabe 3: Verschiedene Farben (20 Punkte)

Dieses Mal haben alle Becher verschiedene Farben und Stofl muss sie in der Reihenfolge des Regenbogens anordnen. Für die Zahlen in der Eingabe bedeutet dies, dass er sie in aufsteigender Reihenfolge sortieren muss.

Eingabe

Die Eingabe ist gleich wie in Teilaufgabe 2.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 2.

Limits

  • T = 100
  • 1 ≤ N ≤ 104
  • 0 ≤ ci ≤ 106 für alle i von 1 bis N

Beispiele

Eingabe:

2
3
10 5 6
4
1 2 4 3

Ausgabe:

Case #1: 2
Case #2: 1

Bemerkung:

Case #1: vertausche den ersten und zweiten Becher, dann den zweiten und dritten
Case #2: vertausche den dritten und vierten Becher

Teilaufgabe 4: Allgemeiner Fall (20 Punkte)

Alles ist gleich wie in Teilaufgabe 3, ausser dass mehrere Becher die gleiche Farbe haben können.

Eingabe

Die Eingabe ist gleich wie in Teilaufgabe 3.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 3.

Limits

Die Limits sind gleich wie in Teilaufgabe 3.

Beispiele

Eingabe:

2
4
10 5 5 6
5
2 1 2 4 3

Ausgabe:

Case #1: 3
Case #2: 2

Bemerkung:

Case #1: vertausche den ersten und zweiten Becher, dann den zweiten und dritten, und schliesslich den dritten und vierten
Case #2: vertausche den ersten und zweiten Becher, dann den vierten und fünften

Teilaufgabe 5: Viele Becher (30 Punkte)

Nun muss Stofl eine riesige Anzahl Becher ordnen. Die gewünschte Reihenfolge ist dieselbe wie in Teilaufgaben 3 und 4.

Eingabe

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

Für jeden Testfall folgen nun zwei Zeilen. Auf der jeweils ersten Zeile steht eine Zahl K, die Anzahl Bechergruppen (siehe unten). Auf der jeweils zweiten Zeile folgen K Paare von Zahlen ni und ci, i von 1 bis K, welche die Bechergruppen beschreiben. Eine Bechergruppe besteht aus ni Bechern, die alle dieselbe Farbe ci haben.

Ausgabe

Die Ausgabe ist gleich wie in Teilaufgabe 4.

Limits

  • T = 100
  • 1 ≤ K ≤ 106
  • 1 ≤ ni ≤ 106 für alle i von 1 bis K
  • 1 ≤ Ki = 1ni ≤ 1010
  • 0 ≤ ci ≤ 109 für alle i von 1 bis K
  • 0 ≤ S < 263

Beispiele

Eingabe:

2
3
1 10 2 5 1 6
4
5 1 3 2 2 4 2 3

Ausgabe:

Case #1: 3
Case #2: 4

Bemerkung:

Case #1: alle Becher ausgeschrieben: 10 5 5 6; vertausche den ersten und zweiten Becher, dann den zweiten und dritten, dann den dritten und vierten
Case #2: alle Becher ausgeschrieben: 1 1 1 1 1 2 2 2 4 4 3 3

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

Seltsame Funktion

Maus Ali hat auf seinem alten Computer eine seltsame C++98-Quelldatei gefunden, die er schon vor Jahren geschrieben haben muss. In der Datei befindet sich die folgende Funktion:

long long funny(long long a, long long b) {
    long long x = 1;
    while (x < b) {
        x *= 2;
    }
    long long s = x%b;
    while (a >= b) {
        a = (a & (x-1)) + s*(a/x);
    }
    return a;
}

Maus Ali hat dummerweise keine Ahnung mehr, was er sich gedacht hat, als er diese Quelldatei geschrieben hat. Allerdings ist er sich bei aller Bescheidenheit gleichzeitig halt schon auch ziemlich sicher, dass der Code genial sein muss.

Es wäre ja nun schade, wenn die in diesem Code verborgenen Erkenntnisse für die Nachwelt verloren gingen. Findest du vielleicht heraus, was die Funktion funny berechnet?

Maus Ali hat den Code in idiomatisches Python übersetzt, in der Hoffnung, er würde dann vielleicht einfacher verständlich. Jedoch wurde er dabei leider auch nicht klüger, aber vielleicht ist die übersetzte Version ja für dich hilfreich:

def funny(a, b):
    x = 1
    while x < b:
        x = 2*x
    s = x%b
    while a >= b:
        a = (a & (x-1)) + s*(a//x)
    return a

Teilaufgabe 1: Kleine Werte mit Terminierungsgarantie (10 Punkte)

Berechne das Resultat von funny(a, b) für einige kleine Eingabewerte. Es wird garantiert, dass funny(a, b) für alle (a, b) in der Eingabe ein Resultat zurückgibt.

Eingabe

Auf der ersten Zeile der Eingabe steht eine Zahl T, die Anzahl Paare (a, b), für welche du funny(a, b) berechnen sollst. Dann folgen T Zeilen, mit je zwei ganzen Zahlen a und b getrennt durch ein einzelnes Leerzeichen.

Ausgabe

Gib für jeden Testfall eine Zeile im Format “Case #i: R” aus, wobei i der Nummer des Testfalles (für den ersten Testfall ist i = 1) entspricht, und R das Resultat von funny(a, b) ist.

Limits

  • T = 100
  • 0 ≤ a ≤ 100
  • 0 ≤ b ≤ 100
  • funny(a, b) gibt ein Resultat zurück.

Beispiele

Eingabe:

3
1 2
20 11
100 64

Ausgabe:

Case #1: 1
Case #2: 9
Case #3: 36

Teilaufgabe 2: Kleine Werte (10 Punkte)

Berechne das Resultat von funny(a, b) für einige kleine Eingabewerte. Wenn funny(a, b) für bestimmte Eingabewerte (a, b) aus irgendeinem Grund kein Resultat zurückgibt, gib stattdessen “NOTHING” aus. (R ist also nicht mehr unbedingt eine Zahl.)

Eingabe

Gleich wie in Teilaufgabe 1.

Ausgabe

Gleich wie in Teilaufgabe 1, nur dass auch “NOTHING” stehen kann.

Limits

  • T = 100
  • 0 ≤ a ≤ 100
  • 0 ≤ b ≤ 100

Beispiele

Eingabe:

3
1 3
20 12
100 65

Ausgabe:

Case #1: 1
Case #2: 8
Case #3: NOTHING

Teilaufgabe 3: Grössere Werte mit Terminierungsgarantie (10 Punkte)

Berechne das Resultat von funny(a, b) nun auch für grössere Eingabewerte. Es wird garantiert, dass funny(a, b) für alle (a, b) in der Eingabe ein Resultat zurückgibt.

Eingabe

Gleich wie in Teilaufgabe 1.

Ausgabe

Gleich wie in Teilaufgabe 1.

Limits

  • T = 100
  • 0 ≤ a ≤ 1018
  • 0 ≤ b ≤ 1018
  • funny(a, b) gibt ein Resultat zurück.

Beispiele

Eingabe:

3
1124615 3132478
20239832878787237 12563819465217352
1000000000000000000 18014398509481984

Ausgabe:

Case #1: 1124615
Case #2: 7676013413569885
Case #3: 9208081978490880

Teilaufgabe 4: Theoretische Argumentation für Teilaufgabe 3 (25 Punkte)

Erkläre, wieso deine Lösung für Teilaufgabe 3 für alle nichtnegativen ganzen Zahlen (a, b) (sodass funny(a, b) ein Resultat zurückgibt) korrekt ist (also insbesondere auch für Zahlen die grösser als 1018 sind). Analysiere ausserdem die Laufzeit deiner Lösung. Versuche deine Argumente möglichst klar und präzise zu formulieren. Wir erwarten keinen streng mathematischen Beweis, allerdings sollten deine Argumente gut begründet und aufeinander aufbauend sein.

Für diese theoretische Teilaufgabe sollst du annehmen, dass der Datentyp long long beliebige ganze Zahlen darstellen kann, aber die Grundoperationen (wie z.B. <, <=, +, -, *, /, %, & und =) trotzdem in konstanter Zeit ausgeführt werden.

Für diese Teilaufgabe kannst du nur Punkte erhalten, wenn deine Lösung für Teilaufgabe 3 für alle (a, b) (mit a ≥ 0 und b ≥ 0 sodass funny(a, b) ein Resultat zurückgibt) korrekt ist und eine Laufzeit von höchstens O(loga + logb) hat. (Du kannst für Teilaufgabe 3 beliebig oft einsenden, und wir zählen nur die letzte korrekte Einsendung, also ist es kein Problem, wenn deine erste Lösung für Teilaufgabe 3 diese Bedingungen zunächst nicht erfüllt. Für diese Teilaufgabe werden wir nur die letzte Einsendung korrigieren.)

Lösungen die nicht in konstanter Zeit laufen erhalten nicht alle Punkte für diese Teilaufgabe.

Teilaufgabe 5 (10 Punkte)

Berechne das Resultat von funny(a, b) für grosse Eingabewerte. Wenn funny(a, b) für bestimmte Eingabewerte (a, b) aus irgendeinem Grund kein Resultat zurückgibt, gib stattdessen “NOTHING” aus.

Eingabe

Gleich wie in Teilaufgabe 2.

Ausgabe

Gleich wie in Teilaufgabe 2.

Limits

  • T = 100
  • 0 ≤ a ≤ 1018
  • 0 ≤ b ≤ 1018

Beispiele

Eingabe:

3
1124615 3132479
20239832878787237 12563819465217353
1000000000000000000 18014398509481985

Ausgabe:

Case #1: 1124615
Case #2: 7676013413569884
Case #3: NOTHING

Teilaufgabe 6 (35 Punkte)

Erkläre, wieso deine Lösung für Teilaufgabe 5 für alle nichtnegativen ganzen Zahlen (a, b) korrekt ist (also insbesondere auch für Zahlen die grösser als 1018 sind). Analysiere ausserdem die Laufzeit der Lösung. Versuche deine Argumente möglichst klar und präzise zu formulieren. Wir erwarten keinen streng mathematischen Beweis, allerdings sollten deine Argumente gut begründet und aufeinander aufbauend sein.

Für diese theoretische Teilaufgabe sollst du annehmen, dass der Datentyp long long beliebige ganze Zahlen darstellen kann, aber die Grundoperationen (wie z.B. <, <=, +, -, *, /, %, & und =) trotzdem in konstanter Zeit ausgeführt werden.

Für diese Teilaufgabe kannst du nur Punkte erhalten, wenn deine Lösung für Teilaufgabe 5 für alle (a, b) (mit a ≥ 0 und b ≥ 0) korrekt ist und eine Laufzeit von höchstens O(loga + logb) hat. (Du kannst für Teilaufgabe 5 beliebig oft einsenden, und wir zählen nur die letzte korrekte Einsendung, also ist es kein Problem, wenn deine erste Lösung für Teilaufgabe 5 diese Bedingungen zunächst nicht erfüllt. Für diese Teilaufgabe werden wir nur die letzte Einsendung korrigieren.)

Lösungen, die ausser für die Berechnung von x nur konstante Zeit brauchen bekommen mehr Punkte, als Lösungen ohne diese Eigenschaft. Die volle Punktzahl wird nur an Lösungen vergeben, deren Laufzeit insgesamt in o(log(min(a, b))) ist (also Lösungen deren Laufzeit strikt langsamer als logarithmisch wächst).

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

Stofls Abschlussarbeit

Nach jahrelangem Abmühen hat Maus Stofl endlich seine Doktorarbeit fertiggestellt. Als er sie zuende geschrieben hatte, sendete er eine Kopie ans Druckerzentrum um sie ausdrucken und sie zu einem Buch binden zu lassen. Aber das Druckerzentrum hat seine Arbeit sehr schlecht erledigt. Nicht nur haben sie die Arbeit einseitig gedruckt, also jede Seite auf einem anderen Blatt Papier. Viel schlimmer ist, dass sie irgendjemand die Seiten komplett durcheinander gebracht hat. Die Seiten im Buch sind völlig falsch sortiert!

Jetzt ist es kurz vor dem Abgabetermin und Stofl hat keine Zeit mehr, die Arbeit erneut ausdrucken zu lassen. Er hat sich schnell dazu entschieden, das vorhandene Buch zu reparieren, in dem er einige Seiten herausreisst. Niemand wird es merken, wenn ein paar Seiten ausgelassen werden, sofern die übrigen Seiten in korrekter Reihenfoleg sind.

Zum Beispiel könnte er vom Buch, in welchem die Seiten in der Reihenfolge 1, 5, 3, 2, 4 sind, die Seiten 2 und 5 herausreissen. Die übrigen Seiten sind danach richtig sortiert: 1 < 3 < 4.

Natürlich möchte Stofl eine möglichst lange Abschlussarbeit abgeben und nur wenig Seiten herausreissen.

In den folgenden Teilaufgaben wird die Anzahl gedruckter Seiten mit N, sowie die Reihenfolge der Seitenzahlen im ausgedruckten Buch mit a1, a2, …, aN bezeichnet.

Teilaufgabe 1: Zweiseitige Abschlussarbeit (10 Punkte)

Bestimme, ob Stofl eine Abschlussarbeit mit mindestens zwei Seiten einreichen kann.

Eingabe

Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus zwei Zeilen. Die erste Zeile des Testfalls besteht aus einer Zahl N, die darauffolgende Zeile enthält N leerzeichengetrennte verschiedene Ganzzahlen a1, a2, …, aN.

Ausgabe

Gib für den i-ten Testfall eine Zeile mit “Case #i: YES” aus, falls Stofl eine Abschlussarbeit einreichen kann, die aus mindestens zwei Seiten besteht. Falls er das nicht kann, gebe “Case #t: NO” aus.

Limits

  • T = 100
  • 2 ≤ N ≤ 1000
  • 1 ≤ ai ≤ N
  • Alle ai sind verschieden.

Beispiel

Eingabe:

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

Ausgabe:

Case #1: YES
Case #2: YES
Case #3: NO

Bemerkung:

Case #1: Durch Entfernen von zwei Seiten kann Stofl eine Abschlussarbeit mit vier Seiten einreichen: 1, 3, 4, 6.
Case #2: Es gibt genau eine gültige Lösung: Entferne Seite 3 und sende Abschlussarbeit ein, welche die Seiten 1 und 2 enthält.
Case #3: Die beiden einzigen Seiten sind verkehrt und es gibt keine Möglichkeit, das zu ändern.

Teilaufgabe 2: Längstmögliche Abschlussarbeit (20 Punkte)

Bestimme die grösstmögliche Anzahl Seiten, die Stofl einreichen kann.

Eingabe

Das Eingabeformat ist gleich wie in Teilaufgabe 1.

Ausgabe

Gib für den i-ten Testfall eine Zeile mit “Case #i: M” aus, wobei M die maximale Anzahl Seiten ist, die Stofl einreichen kann.

Constraints

  • T = 100
  • 2 ≤ N ≤ 10 000
  • 1 ≤ ai ≤ N
  • Alle ai sind verschieden

Examples

Eingabe:

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

Ausgabe:

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

Bemerkung:

Case #1: Durch Herausreissen von zwei Seiten kann Stofl eine Abschlussarbeit mit vier Seiten einreichen: 1, 3, 4, 6.
Case #2: Eine optimale Lösung benutzt die Seiten 1, 3, 4, 7. Falls du Seite 5 nehmen würdest, könntest du höchstens noch zwei weitere Seiten nehmen.
Case #3: Stofl muss mindestens eine der beiden Seiten herausreissen.

Teilaufgabe 3: Alle Möglichkeiten (20 points)

In Teilaufgabe 2 hast du Stofl geholfen, die maximale Anzahl Seiten M zu bestimmen, welche er einreichen kann. Jetzt möchter er genau das tun: Eine Abschlussarbeit mit genau M Seiten einreichen. Interessanterweise kann es manchmal mehrere Möglichkeiten geben, diese M Seiten auszuwählen. Bestimmt, auf wie viele Arten Stofl eine gültige Abschlussarbeit auswählen kann.

Eingabe

Das Eingabeformat ist gleich wie in Teilaufgaben 1 und 2.

Ausgabe

Gib für den i-ten Testfall eine Zeile mit “Case #i: K” aus, wobei K die Anzahl verschiedene Möglichkeiten ist, wie Stofl seine Abschlussarbeit zusammenstellen kann. Beachte, dass wir nur an der längstmöglichen Abschlussarbeit interessiert sind.

Da diese Zahl sehr gross werden kann, gib sie modulo 109 + 7 aus.

Limits

  • T = 100
  • 2 ≤ N ≤ 5 000
  • 1 ≤ ai ≤ N
  • Alle ai sind verschieden

Beispiel

Eingabe:

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

Ausgabe:

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

Bemerkung:

Case #1: Es gibt vier verschiedene Möglichkeiten, wie Stofl eine vier Seiten behalten kenn: (1,3,5,6), (1,3,4,6), (1,2,5,6) und (1,2,4,6).
Case #2: Stofl kann höchstens vier seiten behalten und es gibt genau eine solche Möglichkeit: (1,3,4,7).
Case #3: Stofl kann eine der beiden Seiten auswählen. Seine Abschlussarbeit wird dann entweder (1) oder (2) sein.

Teilaufgabe 4: Rekonstruierung (20 points)

Stofl hat seine Abschlussarbeit nun endlich eingereicht. Er erinnert sich daran, dass das Buch aus N Seiten bestand. Er erinnert sich ausserdem daran, was wir oben beschrieben hatten: Er hat einige (oder keine) Seiten entfernt um eine längstmögliche Abschlussarbeit zu erhalten. Er kann sich auch noch an die Zahl K erinnern, die du in Teilaufgabe 3 berechnet hast – die Anzahl Möglichkeiten, auf die er auswählen konnte, welche Seiten er behalten möchte. Er erinnert sich an den genauen Wert von K, nicht (K mod (109 + 7)).

Stofl möchte nun das Buch rekonstruieren, das er ganz am Anfang hatte. Hilf ihm: Finde eine Permutation der Seiten 1, 2, …, N so dass es genau K Möglichkeiten gibt, eine längstmögliche Abschlussarbeit auszuwählen.

Eingabe

Die erste Zeile enthält eine Ganzzahl T, die Anzahl Testfälle. Jeder Testfall besteht aus einer einzigen Zeile mit den Ganzzahlen N und K, getrennt durch ein Leerzeichen.

Ausgabe

Gib für den i-ten Testfall eine Zeile mit “Case #i: a1 a2 ... aN” aus, wobei a1, …, aN eine mögliche Anordnung der N Seiten des ausgedruckten Buches ist. Falls es mehrere Lösungen gibt, kannst du eine beliebige ausgeben.

Limits

  • T = 100
  • 200 ≤ N ≤ 1 000
  • 1 ≤ K ≤ 1018

Beispiel

Eingabe:

3
6 4
7 1
2 2

Ausgabe:

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

Bemerkung:

Dies sind die gleichen Testfälle die in Teilaufgabe 2 vorkamen. Es gibt auch andere richtige Ausgaben, zum Beispiel wäre in Testfall #2 auch die Reihenfolge (1,2,3,7,4,5,6) richtig.

Teilaufgabe 5: Rekonstruierung mit wenig Seiten (30 Punkte)

Einige Jahre später denkt Stofl an die Geschichte aus Teilaufgabe 4 zurück, wo er versucht hatte, das Buch zu rekonstruieren. Er kann sich noch an K (der Anzahl Möglichkeiten, die er hatte, die Seiten auszuwählen), aber nicht mehr an N.

Gegeben, K möchte er ein N finden, so dass es eine Permutation der Seiten 1, 2, …, N gibt, die eine gültige Abschlussarbeit erzeugen. Und er möchte einen möglichst kleinen Wert für N finden.

Das ist eine theoretischer Teilaufgabe.

Beschreibe einen Algorithmus, der für einen Wert K eine Zahl N und eine Permutation von 1, 2, …, N berechnet. Erkläre, wieso der Algorithmus korrekt ist und welche Laufzeit- und Speicherkomplexität er hat.

Erforsche wie N von K abhängt. Definiere die Funktion f(K) = N als das Ergebnis deines Algorithmus. Um Punkte zu erhalten sollte deine Funktion die Bedingung f(K) ≤ C⋅log(K) + D für Konstanten C und D erfüllen. Lege die Werte von C und D fest und zeige, dass die Ungleichung erfüllt ist. (Anders formuliert, f(K) = O(log(k)) und wir sind an C = max(f(K) ⁄ log(K)) interessiert.) Versuche, C so klein wie möglich zu wählen.

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

U-Boot

Maus Stofl ist Käselieferant und liefert seine Produkte auch an abgelegene Orte. Unter anderem auch mit Schiffen über den grossen Teich. Doch Maus Joël gönnt Maus Stofl seinen Erfolg nicht. Daher hat er sich U-Boote zugelegt und möchte die Käselieferungen unterwegs versenken. Hilf den Beiden, ihren Konflikt auszutragen.

Kreativitätsaufgabe

Aufgabe

Schreibe ein Programm, das die Schiffe von Maus Stofl bzw. die U-Boote von Maus Joël steuert. Es spielen dann jeweils zwei Programme gegeneinander, eines spielt die Schiffe und das andere die U-Boote.

Das Spielfeld ist als ein rechteckiges Gitter gegeben. Jedes Feld ist entweder Wasser oder Land. Zusätzlich sind einige Wasser Felder als Startpunkte und einige als Zielpunkte markiert. Auf jedem Feld kann sich höchstens ein Objekt (= Schiff oder U-Boot) pro Spieler befinden.

Jedes Schiff startet auf einem der Startfelder, jedes U-Boot auf einem Zielfeld. Das Ziel der Schiffe ist es, dass möglichst viele ein Zielfeld erreichen. Das Ziel der U-Boote ist hingegen, dass möglichst wenig Schiffe ein Zielfeld erreichen, indem sie sie unterwegs versenken.

Die beiden Spieler wechseln sich jeweils ab, die Schiffe beginnen. In jeder Runde darf jedes Objekt genau eine Aktion durchführen:

  • Stehen bleiben.
  • Bewegen. Die euklidische Distanz zwischen den beiden Feldern darf dabei höchstens rm sein (d.h. (sx − dx)2 + (sy − dy)2 ≤ r2m) und das Zielfeld muss frei sein. Es dürfen dabei Landfelder übersprungen werden.
  • Angreifen (nur U-Boote). Die euklidische Distanz zwischen U-Boot und dem angegriffenen Feld darf dabei höchstens ra sein (d.h. (sx − dx)2 + (sy − dy)2 ≤ r2a).

Die U-Boote sehen ein Schiff nur, wenn es höchstens rv von einem U-Boot entfernt ist. Die Schiffe sehen ein U-Boot genau dann, wenn es in dieser Runde ein Schiff versenkt hat. Greift ein U-Boot ein Feld an, auf dem sich ein Schiff befindet, versinkt dieses sofort. Fährt ein Schiff auf ein Zielfeld, verschwindet es sofort und es können weitere Schiffe in der selben Runde auf dieses Feld fahren. Versenkte sowie sich am Ziel befindliche Schiffe können nicht mehr bewegt bzw. angegriffen werden.

Protokoll

Die Kommunikation zwischen Program und Server erfolgt über Stdin / Stdout. Alle Koordinaten sind 0 basiert, der Ursprung befindet sich oben links, die y-Koordinaten werden nach unten grösser.

Zu Beginn erhält das Programm allgemeine Informationen über das Spiel:

Eine Zeile mit m s t r2m r2v r2a, die Seite m die es spielen soll (0 = Schiffe, 1 = U-Boote), die Anzahl Schiffe s, die Anzahl U-Boote t, die drei Radien für bewegen, sehen und angreifen jeweils im Quadrat (dies erlaubt es dir, die Distanz mit Ganzzahlen statt mit Kommazahlen zu überprüfen: (sx − dx)2 + (sy − dy)2 ≤ r2m). Auf der nächsten Zeile stehen w h, die Breite w sowie die Höhe h des Spielfeldes. Es folgen h Zeilen mit je w Zeichen (# = Land, . = Wasser, s = Startfeld, d = Zielfeld).

Anschliessend gibt das Programm für jedes seiner Objekte (= Schiff oder U-Boot) eine gültige Startposition x y (d.h. ein s Feld für ein Schiff bzw. ein d Feld für ein U-Boot) aus, jeweils ein Objekt pro Zeile (d.h. insgesamt s bzw. t Zeilen).

Je nach Seite unterscheidet sich das Protokoll für die einzelnen Runden. Am Ende des Spiels wird für sl bzw. sv (s.u.) -1 ausgegeben und dein Programm soll sich daraufhin korrekt beenden.

Um einen Debug Punkt anzuzeigen kann jederzeit D x y ausgegeben werden. Eine solche Ausgabe zählt natürlich nicht als Aktion.

Schiff

Input: Eine Zeile mit sl, der Anzahl in der letzten Runde versunkenen Schiffe. Es folgen sl Zeilen mit je vier Ganzzahlen x y u v, die Koordinaten eines versenkten Schiffes x y sowie die Koordinaten u v des U-Bootes, welches das Schiff versenkt hat.

Output: Für jedes noch verbleibende Schiff (d.h. nicht versenkt und nicht bereits am Ziel) eine Zeile mit der gewünschten Aktion (M für bewegen) und den Zielkoordinaten der Aktion. Falls sich ein Schiff nicht bewegen soll, wird M x y mit den aktuellen Koordinaten ausgegeben. Die Reihenfolge der Schiffe muss in jeder Runde gleich bleiben, versenkte bzw. am Ziel befindliche Schiffe werden einfach ausgelassen.

U-Boot

Input: Eine Zeile mit sv, die Anzahl momentan sichtbarer Schiffe. Es folgen sv Zeilen mit je zwei Ganzzahlen x y, die Koordinaten eines Schiffes. Die Reihenfolge ist zufällig und in jeder Runde anders.

Output: Für jedes U-Boot eine Zeile mit der gewünschten Aktion (A für angreifen, M für bewegen) und den Zielkoordinaten der Aktion. Die Reihenfolge der U-Boote muss in jeder Runde gleich bleiben.

Limits

  • 0 ≤ m ≤ 1
  • 1 ≤ s, t ≤ 1000
  • 1 ≤ rm, rv, ra ≤ 106
  • 2 ≤ w, h ≤ 1000

Dein Programm sollte auf diesen Limits ein komplettes Spiel innert “nützlicher Frist” spielen können (d.h. innert Minuten und nicht Stunden). Hat ein Programm zu lange, verliert es das aktuelle Spiel.

Beispiel

> 1 10 2 9 25 9
> 100 100
[...]
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss.............................................dddd.............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss............................................dddddd............................................sss
> sss.............................................dddd.............................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
> sss..............................................................................................sss
[...]
< 52 49
< 49 52
> 0
< M 54 47
< M 47 52
> 0
< M 51 47
< M 47 55
[...]
> 1
> 49 37
< M 49 44
< M 52 65
[...]
> 0
< M 52 47
< M 49 70
> 1
> 50 43
< M 52 45
< M 50 68
> 2
> 51 44
> 50 43
< A 51 44
< M 51 68
> 1
> 49 42
< M 53 45
< M 50 67
[...]
> 0
< M 26 65
< M 45 73
> 0
< M 25 64
< M 47 75
> 0
< M 23 66
< M 49 75
> -1

Teilaufgabe 1 : Finde einen Weg (25 Punkte)

Wir vergessen Maus Joël für den Moment und helfen Maus Stofl. Schreibe ein Programm, das alle Schiffe ans Ziel bringt. Die U-Boote werden nicht angreifen. Verwende :SUB1 als U-Boot Kommando, um dein Programm zu testen.

Verwende folgende Werte für die Einstellungen in submarine.txt:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command path/to/your/program.exe
submarine_command :sub1
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

Teilaufgabe 2: Versenke alle Schiffe (25 Punkte)

Wir wollen nun Maus Joël helfen. Alle Schiffe fahren zufällig auf dem Spielfeld umher und werden kein Zielfeld anfahren. Versenke alle Schiffe. Verwende :SUB2 als Schiff Kommando, um dein Programm zu testen.

Verwende folgende Werte für die Einstellungen in submarine.txt:

map path/to/downloaded/map.txt
log logconfig.txt
ship_count 10
submarine_count 3
ship_command :sub2
submarine_command path/to/your/program.exe
radius_move 9
radius_view 25
radius_attack 9
time_limit 50
round_limit 10000
sleep_time 100
---

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. Dein Programm muss beide Seiten spielen können.

Das Turnier findest du nun hier.

Karten

Um dein Programm zu testen, liegen dem Server mehrere Karten bei. Diese Karten werden allerdings nicht unbedingt für das Turnier verwendet.

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.
  • Einige 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 submarine.jar, die restlichen Dateien sind Konfigurationsdateien, Beispielkarten sowei Beispiel-Bots.

Wenn du auf submarine.jar doppelklickst, wird das Spiel wie in submarine.txt (s.u.) angegeben simuliert. du kannst den Server über die Konsole (Windows: Cmd, Mac: Terminal, Linux: Shell) starten, um Argumente mitgeben zu können (java -jar submarine.jar arguments). Welche Argumente zur Verfügung stehen (und auch viele weitere Informationen), findest du in usage.md.

In der Datei submarine.txt kannst du die meisten Einstellungen vornehmen, wie z.B. welche Programme du ausführen möchtest. Das Meiste sollte einfach verständlich sein, mehr Informationen sind in usage.md zu finden.

FAQ

Welches Command muss ich verwenden?

  • Python ship_command python path/to/file.py
  • Java ship_command java -jar program.jar oder ship_command java package.MainClass
  • kompiliertes Programm ship_command ./path/to/program

Ich habe mehrere Source Files

Packe all deine Source Files einfach in ein .zip.

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)numberr… (100)
numberriddle
superpo… (100)
superpowers
cupsort (100)funny (100)dissert… (100)
dissertation
submarine (100)
loading ...