Erste Runde SOI 2015

Übersicht

AufgabeSubtask 1Subtask 2Subtask 3Subtask 4Subtask 5
congress (0/100)0/100/300/400/20
wordchain (0/100)0/200/300/50
audio (0/100)0/200/400/40
yurt (0/100)0/200/200/300/30
river (0/100)0/200/150/150/200/30
bazaar (0/100)0/100

Käse-Kongress (Praktische Aufgabe)

Am Kasachstanischen Käse-Kongress (KKK) nehmen Mäuse aus M verschiedenen Regionen des Landes teil. Die Regionen sind von 1 bis M durchnummeriert. Aus der i-ten Region stammen je Ni Experten für Schafskäse und Ni Experten für Ziegenkäse. Die Teilnehmer des Kongresses werden nach Tradition in Z Zweierzimmer untergebracht. Dabei ist Z gleich der Summe aller Ni, sodass alle Zimmer vollständig belegt sind. Die Zimmer sind von 1 bis Z durchnummeriert. Um den Austausch zu fördern, will das Organisationskomitee des Kasachstanischen Käse-Kongresses (OKKKK) die Teilnehmer nach einem bestimmten Schema auf die Zimmer aufteilen: In jedem Zimmer soll ein Experte für Schafskäse und ein Experte für Ziegenkäse untergebracht sein, und diese zwei Mäuse sollen aus verschiedenen Regionen stammen. Kannst du dem OKKKK dabei helfen?

Teilaufgabe 1: Zwei Regionen (10 Punkte)

Für diese Teilaufgabe gilt M=2, und dein Programm soll entscheiden, ob eine Aufteilung möglich ist.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl T, die Anzahl der Testfälle. Es folgen T Testfälle. Jeder Testfall besteht aus einer einzelnen Zeile, welche die zwei ganzen Zahlen N1 und N2 enthält, getrennt durch ein einzelnes Leerzeichen.

Ausgabe

Gib für die i-te der T Eingaben Case #i: aus, gefolgt von POSSIBLE falls die Aufteilung erfolgen kann und IMPOSSIBLE andernfalls.

Limits

  • 1≤N1,N2≤1 000 000
  • T=100, d.h. es gibt genau 100 Testfälle

Beispiele

Eingabe:

2
1 1
1 2

Ausgabe:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Erklärung: Im ersten Beispiel ergeben sich zwei Zweierzimmer. Ein Zweierzimmer mit dem Ziegenkäse-Experten aus Region 1 und dem Schafskäse-Experten aus Region 2 und ein Zweierzimmer mit dem Schafskäse-Experten aus Region 1 und dem Ziegenkäse-Experten aus Region 2. Im zweiten Beispiel ist es nicht möglich die Experten so auf Zweierzimmer aufzuteilen, dass nie zwei Experten aus Region 2 im selben Zimmer landen.

Teilaufgabe 2: Mehrere Regionen (30 Punkte)

Für diese Teilaufgabe kann M verschiedene Werte annehmen, und dein Programm soll entscheiden, ob eine Aufteilung möglich ist.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl T. Es folgen T Testfälle. Jeder Testfall besteht aus einer einzelnen Zeile mit der ganzen Zahl M, der Anzahl der Regionen, gefolgt von den M Zahlen Ni, getrennt durch einzelne Leerzeichen.

Ausgabe

Gib für die i-te der T Eingaben Case #i: aus, gefolgt von POSSIBLE falls die Aufteilung erfolgen kann und IMPOSSIBLE andernfalls.

Limits

  • 1≤M≤40 000
  • 1≤Ni≤1 000 000
  • T=100, d.h. es gibt genau 100 Testfälle

Beispiele

Eingabe:

2
3 2 1 1
3 4 2 1

Ausgabe:

Case #1: POSSIBLE
Case #2: IMPOSSIBLE

Teilaufgabe 3: Explizite Aufteilung (40 Punkte)

Für diese Teilaufgabe soll dein Programm die Aufteilung der Mäuse in Zimmer explizit ausgeben, falls eine solche Aufteilung existiert.

Eingabe

Die erste Zeile der Eingabe enthält eine ganze Zahl T. Es folgen T Testfälle. Jeder Testfall besteht aus einer einzelnen Zeile mit der ganzen Zahl M, der Anzahl der Regionen, gefolgt von den M Zahlen Ni, getrennt durch einzelne Leerzeichen.

Ausgabe

Gib für den i-ten Testfall Case #i: IMPOSSIBLE aus, falls keine Aufteilung möglich ist. Andernfalls gib die Zeile Case #i: aus, gefolgt von Z Zeilen, wobei die i-te davon die ganzen Zahlen Ai und Bi enthält. Jede dieser Zeilen beschreibt die Bewohner eines der Z Zweibettzimmer: Im i-ten Zimmer wird ein Experte für Schafskäse aus Region Ai zusammen mit einem Experten für Ziegenkäse aus Region Bi wohnen.

Es kann sehr viele verschiedene mögliche Aufteilungen geben. Dein Programm soll dann einfach eine beliebige davon ausgeben.

Limits

  • 1≤M≤200
  • 1≤Ni≤200
  • T=100, d.h. es gibt genau 100 Testfälle

Beispiele

Eingabe:

3
4 1 1 1 1
3 2 1 1
2 1 2

Ausgabe:

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

Teilaufgabe 4: Mehrere Kategorien (20 Punkte)

Das OKKKK überlegt sich, in zukünftigen Ausgaben des Kongresses je K·Ni Mäuse pro Region einzuladen, mit K≥1. Da sich das Schema, welchem zufolge die Mäuse in Zimmer aufgeteilt wurden, bisher gut bewährt hat, soll es in generalisierter Form weiter bestehen bleiben. Das heisst, für K=2 entspricht dieses neue Schema genau dem bisherigen Schema. Aus jeder Region werden je Ni Mäuse aus K verschiedenen Kategorien anreisen (Zum Beispiel, Experten für Schafskäse, Ziegenkäse, Würzigen Käse, Milden Käse, …). Die Kategorien sind von 1 bis K durchnummeriert. Diese Mäuse sollen dann so in K-Bett-Zimmer aufgeteilt werden, dass in jedem Zimmer keine zwei Mäuse aus derselben Region und keine zwei Mäuse aus derselben Kategorie stammen. (Das bedeutet auch, dass es in jedem Zimmer von jeder Kategorie genau eine Maus geben soll.)

Eingabe

Die erste Zeile der Eingabe enthält die ganze Zahl T. Es folgen T Testfälle. Jeder Testfall besteht aus einer einzelnen Zeile mit den ganzen Zahlen M und K, der Anzahl der Regionen und der Anzahl der Kategorien, gefolgt von den M Zahlen Ni, getrennt durch einzelne Leerzeichen.

Ausgabe

Gib für den i-ten Testfall Case #i: IMPOSSIBLE aus, falls keine Aufteilung möglich ist. Andernfalls gib die Zeile Case #i: aus, gefolgt von Z Zeilen, wobei die i-te davon K ganze Zahlen Ri,j enthält. Jede dieser Zeilen beschreibt die Bewohner eines der Z K-Bett-Zimmer: Im i-ten Zimmer stammt der Experte der Kategorie j aus Region Ri,j.

Limits

  • 1≤M≤200
  • 1≤K·Ni≤400
  • T=100, d.h. es gibt genau 100 Testfälle

Beispiele

Eingabe:

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

Ausgabe:

Case #1:
1 2
2 1
3 1
1 3
Case #2: IMPOSSIBLE
Case #3:
3 1 2
1 2 3
2 3 1

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

Wörterkette (Praktische Aufgabe)

Maus Stofl möchte gerne neuartige Gedichte verfassen, welche aus schönen Wörterketten bestehen. Seine originelle Idee dabei ist, dass er Wörter verwendet, die ineinander vorkommen. Ein Wort kommt in einem anderen vor, wenn alle Buchstaben in der gleichen Reihenfolge enthalten sind. Bach kommt z.B. in belauschen vor, aber nicht in hab.

Teilaufgabe 1: Zwei Wörter (20 Punkte)

Zuerst möchte Stofl Gedichte der Länge 2 verfassen. Dazu will er von zwei Wörtern wissen, ob eines der beiden in dem anderen vorkommt. Hilf ihm, diese Frage zu beantworten.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Gedichte die Stofl verfassen möchte. Es folgen T Zeilen mit jeweils zwei Wörtern.

Ausgabe

Gib für jede der T Eingaben Case #i: aus, gefolgt von YES, falls eines der beiden in dem anderen enthalten ist und NO, falls nicht.

Limits

  • Jedes Wort besteht aus höchstens 10 000 kleingeschriebenen Buchstaben zwischen a und z.
  • T=100, d.h. es gibt genau 100 Gedichte.

Beispiele

Eingabe:

3
bach belauschen
belauschen bach
bach dach

Ausgabe:

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

Teilaufgabe 2: Kurzes Gedicht (30 Punkte)

Stofl hat nun eine Liste aus Wörtern vor sich und versucht, aus zwei davon ein kleines Gedicht zu bilden. Entscheide, ob sich aus zwei der gegebenen Wörtern ein Gedicht bilden lässt.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Gedichte die Stofl verfassen möchte. Es folgen T Eingaben, die jeweils folgendermassen aufgebaut sind: Auf der ersten Zeile steht die Zahl N. Es folgen N Zeilen mit jeweils einem Wort Wi.

Ausgabe

Gib für jede der T Eingaben Case #i: aus, gefolgt von YES, falls ein Gedicht der Länge 2 existiert und NO andernfalls.

Limits

  • 1<N≤400, d.h. es gibt höchstens 400 verschiedene Wörter.
  • Jedes Wort besteht aus höchstens 100 kleingeschriebenen Buchstaben zwischen a und z.
  • T=100, d.h. es gibt genau 100 Gedichte.

Beispiele

Eingabe:

2
5
bach
dachs
belauschen
obacht
dach
4
bach
dach
fach
sache

Ausgabe:

Case #1: YES
Case #2: NO

Teilaufgabe 3: Langes Gedicht (50 Punkte)

Nachdem Stofl die Kunst der kleinen Gedichte gemeistert hat, versucht er sich nun an grösseren. Jedes Gedicht besteht aus einer schönen Wörterkette. Eine Wörterkette ist schön, wenn jedes Wort davon in allen darauffolgenden Wörtern vorkommmt. ah, bach, belauschen ist eine schöne Wörterkette, weil ah sowohl in bach als auch belauschen vorkommt und bach in belauschen. ah, bach, brach, belauschen ist hingegen nicht schön, weil brach nicht in belauschen vorkommt.

Stofl möchte möglichst lange Gedichte und braucht dazu lange Wörterketten. Gegeben eine Liste von Wörtern, finde die Länge der längsten Wörterkette heraus.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Gedichte die Stofl verfassen möchte. Es folgen T Eingaben, die jeweils folgendermassen aufgebaut sind: Auf der ersten Zeile steht die Zahl N. Es folgen N Zeilen mit jeweils einem Wort Wi.

Ausgabe

Gib für jede der T Eingaben Case #i: aus, gefolgt von L, der Länge (Anzahl Wörter) der längsten schönen Wörterkette.

Limits

  • 1<L≤N≤400, d.h. es gibt höchstens 400 verschiedene Wörter und die Lösung ist höchstens so gross wie die Anzahl Wörter.
  • Jedes Wort besteht aus höchstens 100 kleingeschriebenen Buchstaben zwischen a und z.
  • T=100, d.h. es gibt genau 100 Gedichte.

Beispiele

Eingabe:

2
8
bach
dachs
brach
belauschen
obacht
ah
belauschend
dach
3
bach
dach
fach

Ausgabe:

Case #1: 4
Case #2: 1

Bemerkung:

Das einzige mögliche Gedicht mit Länge 4 in Beispiel 1: „ah, bach, belauschen, belauschend“.

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

Audio (Praktische Aufgabe)

Stofl hört sich eine langweilige Audiodatei an. Der Sprecher redet sehr langsam und Stofl fragt sich, ob er die langezogenen Laute nicht verkürzen könnte um schneller fertig zu werden.

Ein Laut ist eine Überlagerung von Wellen mit unterschiedlicher Periodenlänge, was eine neue Welle mit einer längeren Periode ergibt.

Stofl weiss aus seinem Physikunterricht, dass die Periode der resultierenden Welle das kleinste gemeinsame Vielfache der Einzelperioden ist.

Teilaufgabe 1: Einzelne Überlagerung (20 Punkte)

Gegeben sind N Einzelperioden Pj. Gib die Periodendauer der resultierenden Welle Pr für mehrere Testfälle aus.

Input

Die erste Zeile der Eingabe enthält die ganze Zahl L, die Anzahl der Testfälle. Danach folgen L Zeilen. Auf jeder Zeile steht zuerst die Zahl N, die Anzahl von Einzelwellen. Danach folgen N Zahlen P1 bis PN, die Einzelperioden. Diese sind durch Leerzeichen getrennt.

Output

Gib für den i-ten Testfall Case #i: aus, gefolgt von der Zahl Pr, der resultierenden Periodendauer.

Limits

  • 1≤N≤10000
  • Es wird garantiert, dass 1≤Pr≤263
  • L=100 d.h. es gibt genau 100 Testfälle

Beispiele

Eingabe:

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

Ausgabe:

Case #1: 24
Case #2: 8
Case #3: 30

Teilaufgabe 2: Mehrere Überlagerungen (40 Punkte)

Stofl hat sich überlegt, dass sich ein Laut am stärksten verkürzen lässt (und seinen Klang dennoch behält), indem man nur eine Periode voll schwingen lässt und danach noch die Restschwingung anhängt.

Wenn also eine (resultierende) Welle mit der Periode von 5ms insgesamt 124ms lang schwingt, kommt sie auf 24 volle Schwingungen und 4ms Restschwingung (124/5=24 Rest 4). Der Klang wäre aber mit nur einer Schwingung und 4ms Restschwingung erhalten, also könnte man den Abschnitt von 124ms auf 5+4=9ms verkürzen. Stofl will ausserdem nur relevante Teile der Datei hören. Wenn es in einem bestimmten Abschnitt also vollständing still ist, dann soll dieser komplett aus der Datei entfernt werden.

Eine Audio-Datei besteht nun aus N Einzelschwingungen, die alle eine Periode Pe, eine Startzeit Ts und eine Endzeit Te haben und sich entsprechend überlagern. Deine Aufgabe ist es nun, mehrere Dateien so wie oben beschrieben zu verkürzen. Die resultierenden Audio-Dateien werden aus K Abschnitten bestehen (K ist für verschiedene Dateien möglicherweise unterschiedlich), die eine bestimmte Reihenfolge haben. Jeder Abschnitt besteht aus einer bestimmten Periode Pr und Dauer Tr. Merke, dass wenn zwei aufeinanderfolgende Abschnitte dieselbe Periode haben, diese nicht kombiniert werden können. (Denn im Allgemeinen wird der Laut im einen Abschnitt nicht mit jenem im anderen Abschnitt übereinstimmen.)

Eingabe

Die erste Zeile der Eingabe enthält die Zahl L, die Zahl der zu verkürzenden Dateien. Danach folgen die L Dateien: Jede Datei beginnt mit einer Zeile mit der Zahl N, die Anzahl an Einzelschwingungen. Die folgenden N Zeilen beschreiben je eine Einzelschwingung: Sie enthalten für jede Einzelschwingung die ganzen Zahlen Pe, Ts und Te, also die Periode, die Startzeit und die Endzeit dieser Einzelschwingung.

Ausgabe

Du sollst die resultierenden Audio-Dateien wie folgt ausgeben: Die erste Zeile der i-ten Audio-Datei enthält Case #i:. Auf der nächsten Zeile einer Datei stehen zwei Zahlen: K, die Anzahl Abschnitte dieser Datei und Ts, die Zeit, bei der der erste Abschnitt startet. Die folgenden K Zeilen beschreiben die Abschnitte in der Reihenfolge, in der sie abgespielt werden: Eine Zeile besteht aus den zwei Zahlen Pr und Tr, also der resultierenden Periode und der Dauer des Abschnittes.

Limits

  • 1≤N≤1000
  • Für alle Einzelschwingungen gilt 0≤Ts<Te≤109.
  • Es wird garantiert, dass alle 1≤Pr≤263.
  • L=100 d.h. es gibt genau 100 Dateien.

Beispiele

Eingabe:

3
3
15 20 120
2 0 20
6 1 150
2
7 2 101
11 23 123
2
2 1 2
3 3 10

Ausgabe:

Case #1:
4 0
2 1
6 7
30 40
6 6
Case #2:
3 2
7 7
77 78
11 11
Case #3:
2 1
2 1
3 4

Bemerkung:

In der ersten Datei ist von Zeit 0 bis 1 nur die Schwingung mit der Periode 2 aktiv, was sich nicht verkürzen lässt. Von Zeit 1 bis 20 sind zwei Schwingungen mit Periode 2 und 6 aktiv, was eine resultierende Schwingung mit Periode 6 ergibt. Die 20=3· 6+1 Sekunden lassen sich auf 6+1=7 Sekunden verkürzen. Von Zeit 20 bis 120 ist die resultierende Periode 30 (von den Perioden 6 und 30), die 100=3·30 + 10 Sekunden ergeben zusammengefasst 30+10=40. Von 120 bis 150 ist nur noch die Periode 6 aktiv, was auf 6 Sekunden reduziert werden kann.

Teilaufgabe 3: Grosse Dateien und grosse Perioden (40 Punkte)

Die Aufgabenstellung für diese Teilaufgabe entspricht der Aufgabenstellung von Teilaufgabe 3, aber du musst nicht die ganze Datei explizit ausgeben.

Gib stattdessen für den i-ten Abschnitt der Datei Pr modulo M aus, mit M=109+7=1000000007 und Pr der Periode des i-ten Abschnittes in der Datei. a modulo b entspricht dem positiven ganzzahligen Rest bei der Division von a durch b. In anderen Worten, 0≤a modulo b<b und wenn a modulo b=c, dann existiert eine ganze Zahl d sodass a=d·b+c.

(Die verkürzten Abschnittsdauern sind nicht länger wichtig.)

Eingabe

Die erste Zeile der Eingabe enthält die Zahl L, die Zahl der Dateien. Danach folgen die L Dateien: Jede Datei beginnt mit einer Zeile mit der Zahl N, die Anzahl an Einzelschwingungen. Die folgenden N Zeilen beschreiben je eine Einzelschwingung: Sie enthalten für jede Einzelschwingung die Zahlen Pe, Ts und Te, also die Periode, die Startzeit und die Endzeit der Einzelschwingung.

Ausgabe

Die erste Zeile der i-ten Ausgabe enthält Case #i:. Auf der nächsten Zeile einer Datei stehen zwei Zahlen: K, die Anzahl Abschnitte dieser Datei und Ts, die Zeit, bei der der erste Abschnitt startet. Die folgenden K Zeilen beschreiben die Abschnitte in der Reihenfolge, in der sie abgespielt werden: Eine Zeile besteht aus der einzelnen Zahl Pr modulo M, also der resultierenden Periode modulo M.

Limits

  • 1≤N≤10‘000‘000
  • Für alle Einzelschwingungen gilt Pe≤220 und 0≤Ts<Te≤109.
  • L=100 d.h. es gibt genau 100 Dateien

Eingabe:

1
4
1000000007 1 2
1000000008 1 4
1000000009 1 4
1000000010 3 4

Ausgabe:

Case #1:
3 1
0
2
3

Bewertung

Da die Eingabedatei für diese Teilaufgabe sehr gross ist, werden wir diese Aufgabe von Hand korrigieren. Damit du testen kannst, ob deine Lösung kleine Testfälle korrekt behandelt, bieten wir hier dennoch ein Bewertungssystem an. Bitte beachte, dass die automatische Rückmeldung nicht definitiv ist und du allfällige Punkte erst nach Einsendeschluss erhältst.

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

Jurte (Theoretische Aufgabe)

Die Nomadenvölker Kasachstans leben in Jurten. Eine Jurte ist ein traditionelles, grosses, rundes Zelt. Auf deiner Reise entdeckst du einen grossen Lagerplatz dessen N Plätze von 1 bis N durchnummeriert sind. Auf jedem Platz steht genau eine Jurte. Auch die Jurten sind nummeriert von 1 bis N, sodass eigentlich immer ein Jurte und ein Zeltplatz zusammengehört. Doch weil die Jurten mitten in der Nacht in aller Eile aufgestellt wurden, sind die Jurten durcheinander gekommen und stehen nun nicht unbedingt auf dem Zeltplatz mit der gleichen Nummer. Deine Aufgabe ist es nun, die Jurten wieder in die richtige Reihenfolge zu bringen. Dazu kannst du Schritt für Schritt immer zwei beliebige Jurten abbauen, austauschen und wieder aufbauen. Du kannst nie mehr als zwei Jurten auf einmal abbauen, also immer nur zwei Jurten austauschen. Dein Ziel ist es mit so wenig Vertauschungen wie möglich alle Jurten wieder in die richtige Reihenfolge zu bringen.

Diese Aufgabe besteht insgesamt aus vier Teilaufgaben, zwei praktischen (1, 2) und zwei theoretischen (3, 4). Bei den praktischen Teilaufgaben musst du ein Programm schreiben, das die Aufgabe löst und kannst es direkt testen und bewerten lassen. Für die theoretischen Aufgaben erwarten wir eine Erklärung und Begründung deines Lösungsansatzes in Form eines Fliesstextes. Versuche dich und uns davon zu überzeugen, dass deine Idee wirklich funktioniert. Dort muss deine Einsendung nicht zwingend ein lauffähiges Programm enthalten. Eine präzise Erklärung z.B. mit Pseudocode genügt. Beschreibe auch die Laufzeit und den Speicherverbrauch deines Programmes und begründe warum es immer terminiert.

Teilaufgabe 1: Praktischer Teil mit wenigen Zelten (20 Punkte)

In dieser Teilaufgabe stehen auf dem Zeltplatz höchstens 8 Jurten. Deine Aufgabe ist es sie mit möglichst wenigen Vertauschungen in die richtige Reihenfolge zu bringen. Deine Ausgabe wird akzeptiert, sofern du für N Jurten höchstens N Vertauschungen benötigst. Dein Programm muss also nicht zwingend optimal handeln. Wenn zum Beispiel die Zelte schon von Beginn an sortiert sind, dann ist es in Ordnung überhaupt keine Vertauschungen durchzuführen. Du darfst dann aber auch einige Pseudovertauschungen machen, die du gleich wieder rückgängig machst. Dass N Vertauschungen immer genügen, wirst du dir in Teilaufgabe 3 überlegen.

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Testfälle. Es folgen T Zeilen, jede beschreibt einen Testfall. Jede Zeile beginnt mit N, der Anzahl Jurten, gefolgt von N Leerzeichen-getrennte Zahlen, M1 bis MN, wobei Mi die Nummer der Jurte, die zu Beginn auf Zeltplatz i steht.

Ausgabe

Gib für jeden Testfall eine Zeile mit einer möglichen Vertauschabfolge mit N oder weniger Vertauschungen aus. Gib hierfür für den t-ten Testcase Case #t: aus, gefolgt von einer geraden Anzahl Leerzeichen-getrennter Zahlen Mi. Diese bedeuten, dass die Jurte auf dem Platz M2i-1 mit der Jurte auf dem Platz M2i vertauscht wird. (Beispiel: 5 2 3 6 4 3 bedeutet, dass zuerst die Jurten auf Platz 5 und 2 vertauscht werden, anschliessend die Jurten auf den Plätzen 3 und 6 und abschliessend diejenigen auf Platz 4 und 3).

Limits

  • 3≤N≤8, d.h. es gibt zwischen 3 und 8 Jurten.
  • Du darfst höchstens N Vertauschungen durchführen.
  • T=100, d.h. es gibt genau 100 Testfälle.

Beispiele

Eingabe:

2
3 1 3 2
5 4 3 2 5 1

Ausgabe:

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

Illustration des zweiten Beispieles:

yurt_sample1

Teilaufgabe 2: Praktischer Teil mit vielen Zelten (20 Punkte)

In dieser Teilaufgabe stehen auf dem Zeltplatz höchstens 500 Jurten. Deine Aufgabe ist es sie mit möglichst wenigen Vertauschungen in die richtige Reihenfolge zu bringen. Deine Ausgabe wird akzeptiert, sofern du für N Jurten höchstens N Vertauschungen benötigst. Dein Programm muss also nicht zwingend optimal handeln.

Das Format der Ein- und Ausgabe ist identisch mit Teilaufgabe 1.

Limits

  • 3≤N≤500, d.h. es gibt zwischen 3 und 5 000 Jurten.
  • Du darfst höchstens N Vertauschungen durchführen.
  • T=100, d.h. es gibt genau 100 Testfälle.

Beispiele

Eingabe:

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

Ausgabe:

Case #1: 1 5 2 3 4 5
Case #2: 2 3 3 4 2 4 3 4 1 10

Teilaufgabe 3: Theoretischer Teil: höchstens N-1 Vertauschungen (30 Punkte)

Die Steppenmaus Stofl behauptet nun, dass es immer möglich ist N Jurten mit weniger als N (also höchstens N-1) Vertauschungen in die richtige Reihenfolge zu bringen. Beschreibe wie dein Algorithmus die Aufgabe löst und begründe warum du für jede Startaufstellung weniger als N Vertauschungen benötigst.

Wir erwarten hier eine Erklärung und Begründung deines Lösungsansatzes in Form eines Fliesstextes. Versuche dich und uns davon zu überzeugen, dass deine Idee wirklich funktioniert. Für diese und die nächste Teilaufgabe muss deine Einsendung nicht zwingend ein lauffähiges Programm enthalten. Eine präzise Erklärung z.B. mit Pseudocode genügt.

Teilaufgabe 4: Theoretischer Teil: optimale Anzahl Vertauschungen (30 Punkte)

Du bist noch nicht zufrieden damit, dass es dir in weniger als N Vertauschungen gelingt, denn für manche Startaufstellungen geht es auch deutlich besser. Kannst du für deinen Algorithmus begründen, dass er immer optimal vertauscht? Du sollst also begründen, dass jede erdenkliche Lösungsstrategie mindestens so viele Vertauschungen benötigt wie deine.

Hinweis: Du darfst für die einzelnen Teilaufgaben verschiedene Ansätze implementieren und beschreiben. Wenn du eine Lösung für Teilaufgabe 4 findest, ist es aber gut möglich, dass sich mit der selben Idee auch die anderen Aufgaben lösen lassen.

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

Fluss (Theoretische Aufgabe)

In Kasachstan gibt es einige grosse Flüsse. So ist der Fluss Irtysch beispielsweise über 4 000 Kilometer lang. Er entspringt in China, fliesst durch Kasachstan und mündet dann in Russland in den Ob. Entlang des Irtysch gibt es zahlreiche Städte. Sie sind von 1 bis N nummeriert. Jede Stadt hat zwei Stadtteile, einen Teil auf der linken und einen auf der rechten Flussseite, mit einer Brücke dazwischen, welche die beiden Stadtteile verbindet. Bei einer Überschwemmung sind nun leider alle N Brücken eingestürzt.

Um nun übergangsweise wieder Verbindungen über den Fluss herzustellen sind zwischen einigen gegebenen Paaren von Städten Fährverbindgungen geplant. Damit die Fähren in den Städten anlegen können, muss jede Stadt genau eine Schiffsanlegestelle bauen. Eine solche Schiffsanlegestelle kann jeweils auf der linken oder rechten Flussseite der Stadt gebaut werden. Es soll jede Stadt eine solche Schiffsanlegestelle errichten, selbst wenn es gar keine Fährverbindung dahin gibt.

Neue Brücken über den Fluss sind vorerst keine geplant. Wenn man also den Fluss überqueren möchte, muss man zwingend die Fähre benützen. Damit es trotzdem möglichst einfach ist den Fluss zu traversieren, sollen möglichst viele Fährverbindungen über den Fluss fahren, das heisst auf zwei verschiedenen Flussseiten an- und ablegen. Eine Fährverbindung von Stadt A zu Stadt B überquert zum Beispiel den Fluss, wenn die Anlegestelle in A auf der linken und in B auf der rechten Flussseite gebaut wird. Wenn aber beide Anlegestellen auf der gleichen Seite gebaut werden, dann überquert die Fähre den Fluss nicht.

Nun müssen sich die Stadtpräsidentinnen und Stadtpräsidenen entscheiden auf welcher Flussseite sie ihre Anlegestelle bauen möchten. Kannst du ihnen helfen die Anlegestellen so zu bauen, dass möglichst viele Fährverbindungen den Fluss überqueren?

Diese Aufgabe besteht insgesamt aus fünf Teilaufgaben, zwei praktischen (1a, 2a) und drei theoretischen (1b,1c,2b). Bei den praktischen Teilaufgaben musst du ein Programm schreiben, das die Aufgabe löst und kannst es direkt testen und bewerten lassen. Für die theoretischen Aufgaben erwarten wir eine Erklärung und Begründung deines Lösungsansatzes in Form eines Fliesstextes. Versuche dich und uns davon zu überzeugen, dass deine Idee wirklich funktioniert. Dort muss deine Einsendung nicht zwingend ein lauffähiges Programm enthalten. Eine präzise Erklärung z.B. mit Pseudocode genügt. Beschreibe auch die Laufzeit und den Speicherverbrauch deines Programmes und begründe warum es immer terminiert.

Teilaufgabe 1: Nur flussüberquerende Fährverbindungen (Total 50 Punkte)

In dieser ersten Teilaufgabe wollen wir untersuchen, wann es möglich ist, die Anlegestellen so zu wählen, dass alle Fährverbindungen den Fluss überqueren. Dazu machen wir uns die Aufgabe etwas einfacher und nehmen folgendes an:

Wenn man nur mit Fähren von Stadt A zu Stadt B reisen möchte (unabhängig von der Flussseite am Anfang und Ende), so gibt es dazu entweder genau eine oder keine Möglichkeit.

Dies gelte für jedes Paar von Städten A und B. Damit sind auch indirekte Verbindungen gemeint: Wenn es eine Fährverbindung von A nach C und von C nach B gibt, darfst du annehmen, dass es z.B. keine direkte Verbindung von A nach B gibt und auch keine andere Stadt D, die mit A und B verbunden ist.

river_simplification

Teilaufgabe 1a: Implementierung (20 Punkte)

Kannst du ein Programm schreiben, das unter dieser Bedingung die Schiffsanlegestellen so platziert, dass alle Fährverbindungen den Fluss überqueren?

Eingabe

Auf der ersten Zeile steht die Zahl T, die Anzahl Testfälle. Es folgen T Testfälle, jeweils nach folgendem Muster aufgebaut: Auf der ersten Zeile stehen durch ein Leerzeichen getrennt die Zahlen N und M, die Anzahl Städte sowie die Anzahl geplanter Fährverbindungen. Es folgen M Zeilen, die jeweils zwei durch ein Leerzeichen getrennte Zahlen a und b enthält. Diese sagen aus, dass zwischen der Stadt a und der Stadt b eine Fährverbindung geplant ist.

Ausgabe

Gib für jeden der T Testfälle Case #t: aus, gefolgt von N Zeichen, jeweils L oder R. Zeichen Si gibt an, auf welcher Flussseite sich die Stadt i befindet.

Limits

  • 1≤N≤1 000
  • 0≤M≤1 000
  • T=100

Beispiele

Eingabe:

1
6 4
1 2
3 4
3 5
3 6

Ausgabe:

Case #1: LRLRRR

river_sample1a

Teilaufgabe 1b: Begründung (15 Punkte)

Bitte begründe warum dein Programm aus Teilaufgabe 1a korrekt ist? Warum kannst du garantieren, dass immer alle Fährverbindungen den Fluss überqueren? Was ist die Laufzeit und der Speicherverbrauch deines Programmes?

Teilaufgabe 1c: Auflockerung der Bedingung (15 Punkte)

Dein Freund Maus Stofl hat folgendes neues Beispiel gefunden und hat festgestellt, dass es nicht unser vereinfachenden Bedingung entspricht (es gibt zwei Wege von Stadt 1 nach Stadt 4, entweder direkt oder über die Städte 2 und 3), es aber trotzdem möglich ist, dass alle Fährverbindungen den Fluss überqueren.

Beispiel

Eingabe:

1
4 4
1 2
2 3
3 4
4 1

Ausgabe:

Case #1: LRLR

river_sample1c

Kannst du eine bessere Bedingung finden, welche genau beschreibt, wann es möglich ist, dass alle Fährverbindungen den Fluss überqueren? Beschreibe einen Algorithmus der solche Eingaben korrekt löst und analysiere ihn.

Teilaufgabe 2: Mindestens die Hälfte flussüberquerend (Total 50 Punkte)

Lassen wir nun alle Bedingungen weg und betrachten ein beliebige Menge an Fährverbindungen. Maus Stofl hat bereits ein Beispiel gefunden, wo es nicht möglich ist, alle Fährverbindungen über den Fluss verlaufen zu lassen:

Beispiel

Eingabe:

1
4 4
1 2
2 3
1 3
2 4

Ausgabe:

Case #1: LRRL

river_sample2a

Egal wie man die Anlegestellen wählt werden immer höchstens drei von vier Fährverbindungen den Fluss überqueren.

Stofl behauptet nun, dass es aber immerhin so sei, dass man die Anlegestellen immer so wählen kann, dass mindestens die Hälfte aller Fährverbindungen den Fluss überqueren. Stimmt das wirklich? Kannst du einen Algorithmus finden der dies erreicht und begründen wieso?

Teilaufgabe 2a: Implementierung (20 Punkte)

Schreibe ein Programm, das die Anlegestellen so wählt, dass mindestens die Hälfte aller Fährverbindungen den Fluss überquert.

Das Format der Ein- und Ausgabe ist identisch mit Teilaufgabe 1a.

Limits

  • 1≤N≤1 000
  • 0≤M≤1 000
  • T=100

Beispiel

Eingabe:

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

Ausgabe:

Case #1: LRLRL

Teilaufgabe 2b: Begründung (30 Punkte)

Begründe warum dein Algorithmus aus Teilaufgabe 2a korrekt ist. Analysiere die Laufzeit und den Speicherverbrauch.

Hinweis: Du darfst für die einzelnen Teilaufgaben natürlich verschiedene Ansätze implementieren und beschreiben.

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

Basar (Kreativitätsaufgabe)

Maus Stofl war diesen Sommer in Alamaty, der grössten Stadt in Kasachstan. Er war sehr beeindruckt vom Bazaar, wo er einige Diamanten gekauft hat. Diese Diamanten kann man jedoch nicht einfach so kaufen, sondern sie werden mittels einer speziellen Auktion verkauft: Alle Interessierten wählen eine bestimmte Menge an Goldstücken aus, die sie bieten möchten. Derjenige, der am meisten geboten hat, bekommt den Diamanten, es müssen jedoch alle ihr Gebot bezahlen. Damit das Ganze etwas spannender wird und nicht einfach der Reichste alle Diamanten kauft, darf jede Person höchstens eine bestimmte Menge an Goldstücken während einer Auktion bieten.

Maus Stofl wird nächsten Sommer wieder nach Alamaty reisen, um die Schweizer Delegation an der IOI anzufeuern. Er wird dabei auch dieser Diamantenauktion wieder einen Besuch abstatten. Hilf ihm dabei, möglichst viele Diamanten mit der erlaubten Anzahl Goldstücken zu ergattern!

Das Spiel

Es finden insgesamt A Auktionen statt, bei jeder werden D Diamanten versteigert. (So kann dein Programm versuchen, die Strategien der anderen Programme herauszufinden und eine passende Strategie dagegen zu entwickeln). In jeder Auktion hast du G Goldstücke zur Verfügung.

Eine Auktion besteht aus D Bietrunden. In jeder dieser Runden bietet jeder Spieler verdeckt (d.h. die anderen wissen nicht, was Du bietest) einen Betrag B. Der Spieler, der am meisten geboten hat, bekommt einen Diamanten. Haben mehrere Spieler denselben Höchstbetrag geboten, wird der Diamant zersägt, und gerecht unter den Höchstbietenden aufgeteilt. Es müssen immer alle Spieler den gebotenen Betrag bezahlen, unabhängig davon, ob sie gewonnen haben. Anschliessend erfahren alle, wie viel jeder Spieler geboten hat. Die Summe aller Gebote eines Spielers während einer Auktion darf nicht grösser als G sein.

Eingabe und Ausgabe

Dein Programm wird von einem Spiel-Server gestartet. Es muss von stdin lesen und muss seine Züge nach stdout ausgeben.

Wenn das Spiel beginnt, erhältst du auf einer Zeile vier durch Leerzeichen getrennte ganze Zahlen: N, die Anzahl der Spieler (inklusive deinem Program); A, die Anzahl der Auktionen; D, die Anzahl Bietrunden pro Auktion (was der Anzahl der zu versteigernden Diamanten entspricht); sowie G, die Anzahl Goldstücke pro Auktion, die du ausgeben darfst.

Anschliessend werden A Auktionen gespielt. In jeder werden D Bietrunden gespielt. Eine Bietrunde läuft folgendermassen ab:

  • Du gibst eine ganze Zahl B aus, den Betrag den du auf den aktuellen Diamanten bieten möchtest.
  • Du bekommst eine Zeile mit N-1 Leerzeichen-getrennten ganzen Zahlen, die Gebote der anderen Spieler für den aktuellen Diamanten. Die Reihenfolge der Spieler bleibt während des ganzen Spiels dieselbe.

Sobald alle A Auktionen gespielt sind, soll sich dein Programm beenden.

Beispiel

> 3 1 3 1000
< 100
> 20 80
< 50
> 70 80
< 25
> 120 80

Erklärung: Es spielen insgesamt 3 Spieler. In der ersten Runde bietest Du 100 Goldstücke, die beiden anderen 20 bzw. 80 Goldstücke. Du erhältst den Diamanten. Nach den drei hier dargestellten Runden besitzt jeder Spieler einen Diamanten.

Limits

  • 2≤N≤10
  • 1≤A≤1000
  • 1≤D≤1000
  • 1≤G≤109

Bewertung

Die Bewertung der Kreativaufgabe ist anders als bei anderen Aufgaben. Du bekommst

  • 30% der Punkte für ein Programm, welches das Spiel korrekt spielt, d.h. es respektiert alle Spielregeln und spielt mindestens so gut wie die Beispiel-Bots. Wichtig: Es ist nicht erlaubt, einfach den Code eines Beispiel-Bots einzuschicken. Es ist allerdings erlaubt und wird dir nahegelegt, sie als Beispiel zu verwenden, wie Eingabe und Ausgabe in deiner Programmiersprache korrekt durchgeführt wird.
  • Die restlichen 70% der Punkte werden entsprechend den Resultaten des Turniers am SOI-Tag verteilt.

Optimiert eure Programm also nicht nur darauf, dass sie gegen die Sample-Bots gewinnen, denn wir werden sie auch gegen die Einsendungen der anderen Teilnehmer testen.

Dieses Jahr darfst du mehrere Programme (höchstens 3 pro Teilnehmer) einsenden, dein bestes Programm wird für die Bewertung verwendet. Packe diese Programme alle in ein ZIP-Archiv und sende dieses ein. Die letzte Einsendung zählt für diese Aufgabe! Wir wollen dich so dazu ermutigen, auch risikofreudigere Strategien zu implementieren oder auch einfach, mehrere verschiedene Strategien auszuprobieren.

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;
  • 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-Program, das du benutzen kannst, um dein eigenes Programm gegen deines und andere Programme antreten zu lassen.
  • Eine Visualisierung, die simulierte Spiele darstellt.

Du kannst diese hier herunterladen.

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)congress (100)wordchain (100)audio (100)yurt (100)river (100)bazaar (100)
loading ...