Dies ist ein Run-Twice-Problem (zweimalige Ausführung); beide Durchläufe sind interaktiv.
Um eine breite Eiche herum stehen vier Weise. Jeder Weise trägt einen roten, grünen oder blauen Hut auf dem Kopf. Jeder Weise kann die Hutfarben seiner beiden Nachbarn sehen, aber weder seine eigene Hutfarbe (der Hut hängt nicht über seine Augen) noch die Hutfarbe des ihm gegenüberstehenden Weisen (die durch die breite Eiche verdeckt wird). Jeder Weise muss, ohne mit den anderen zu kommunizieren, die Farbe seines Hutes auf ein Blatt Papier schreiben. Entwickle ein Protokoll, sodass mindestens einer der vier Weisen mit Sicherheit die Farbe seines Hutes errät.
Interaktionsprotokoll
Die erste Zeile enthält zwei ganze Zahlen $t$ und $s$, die die Anzahl der Testfälle und die Nummer des Durchlaufs der Lösung angeben ($1 \le t \le 100$; $s \in \{1, 2\}$). Darauf folgen die Beschreibungen von $t$ Testfällen, jeweils in einer eigenen Zeile.
Wenn $s = 1$ ist, besteht der Testfall aus vier Wörtern $c_1$, $c_2$, $c_3$ und $c_4$, die die Hutfarben der Teilnehmer bezeichnen ($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$). Gib als Antwort eine Zeile mit einer einzigen ganzen Zahl $m$ ($1 \le m \le 4$) aus, die die Nummer des Weisen angibt, der gemäß deinem Protokoll die Farbe seines Hutes erraten wird (falls es mehrere gibt, gib einen beliebigen davon aus).
Wenn $s = 2$ ist, besteht der Testfall aus einer ganzen Zahl $m$ und zwei Wörtern $\ell$ und $r$, die die Nummer des Weisen, der die Farbe seines Hutes erraten muss, sowie die Hutfarben seines linken und rechten Nachbarn bezeichnen ($1 \le m \le 4$; $\ell, r \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$; $\ell = c_{(m+2) \bmod 4 + 1}$; $r = c_{m \bmod 4 + 1}$). Gib als Antwort eine Zeile mit einem Wort $g$ aus, das die Hutfarbe des $m$-ten Weisen angibt. Die Antwort wird akzeptiert, wenn $g = c_m$ gilt. Der Interaktor unterscheidet nicht zwischen Groß- und Kleinschreibung, sodass du jeden Buchstaben beliebig (groß oder klein) ausgeben kannst.
Um die Weitergabe von Informationen zwischen Testfällen zu verhindern, hat die Jury folgende Maßnahmen ergriffen:
- Beide Durchläufe sind interaktiv. Du erhältst also den nächsten Testfall erst, nachdem du die Antworten auf alle vorherigen ausgegeben hast. Vergiss nach der Ausgabe jeder Zeile nicht, den Ausgabestream zu leeren (z. B. mit
fflush(stdout)odercout.flush()in C++,sys.stdout.flush()in Python oderSystem.out.flush()in Java oder Kotlin). Andernfalls erhältst du wahrscheinlich einen Fehler vom Typ Idleness Limit Exceeded. - Während des zweiten Durchlaufs kann die Jury die $t$ Testfälle in eine beliebige Reihenfolge bringen, die nicht mit der Reihenfolge im ersten Durchlauf übereinstimmen muss.
- Während des zweiten Durchlaufs kann die Jury außerdem gefälschte Testfälle hinzufügen, die keinem Testfall aus dem ersten Durchlauf entsprechen. Für diese Fälle wird jede der Antworten „
red“, „green“ oder „blue“ als richtig gewertet; sie dienen lediglich dazu, dass dein Programm einen echten Testfall nicht leicht von einem gefälschten unterscheiden und Informationen zwischen Fällen weitergeben kann. Somit kann $t$ im zweiten Durchlauf größer sein als $t$ im ersten Durchlauf. Die Gesamtzahl der echten und gefälschten Fälle überschreitet nicht $100$.
Beispiele
Eingabe 1
1 1 green red blue red
Ausgabe 1
2
Eingabe 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
Ausgabe 2
blue BLUE blUE Blue