Detta är ett run-twice-problem (två körningar); båda körningarna är interaktiva.
Runt en bred ek står fyra vise män. Varje vis man bär en röd, grön eller blå hatt på huvudet. Varje vis man kan se färgen på hattarna hos båda sina grannar, men kan inte se sin egen hattfärg (hatten hänger inte ner över ögonen) eller färgen på hatten hos den vise mannen mittemot (som skyms av den breda eken). Varje vis man måste, utan att kommunicera med de andra, skriva ner färgen på sin hatt på ett papper. Utveckla ett protokoll sådant att minst en av de fyra vise männen garanterat kommer att gissa rätt på färgen på sin hatt.
Interaktionsprotokoll
Den första raden innehåller två heltal $t$ och $s$, som anger antalet testfall och numret på körningen av lösningen ($1 \le t \le 100$; $s \in \{1, 2\}$). Därefter följer beskrivningar av $t$ testfall, vart och ett på en separat rad.
Om $s = 1$ består testfallet av fyra ord, $c_1$, $c_2$, $c_3$ och $c_4$, som anger färgerna på deltagarnas hattar ($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$). Som svar ska du skriva ut en rad med ett enda heltal $m$ ($1 \le m \le 4$), som anger numret på den vise man som enligt ditt protokoll kommer att gissa färgen på sin hatt (om det finns flera, skriv ut vilken som helst).
Om $s = 2$ består testfallet av ett heltal $m$ och två ord, $\ell$ och $r$, som anger numret på den vise man som måste gissa färgen på sin hatt, samt färgerna på hans vänstra och högra grannes hattar ($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}$). Som svar ska du skriva ut en rad med ett ord $g$ som är färgen på den $m$-te vise mannens hatt. Svaret accepteras om $g = c_m$. Interaktorn gör ingen skillnad på versaler och gemener, så du kan skriva ut varje bokstav som antingen stor eller liten bokstav.
För att förhindra att information skickas mellan testfall har juryn vidtagit följande åtgärder:
- Båda körningarna är interaktiva. Du kommer alltså inte att få nästa testfall förrän du har skrivit ut svaret på alla föregående. Glöm inte att tömma utmatningsströmmen efter varje utskriven rad (till exempel genom att använda
fflush(stdout)ellercout.flush()i C++,sys.stdout.flush()i Python ellerSystem.out.flush()i Java eller Kotlin). Annars kommer du sannolikt att få felet Idleness Limit Exceeded. - Under den andra körningen kan juryn ordna om de $t$ testfallen i vilken ordning som helst, vilken inte behöver stämma överens med ordningen de dök upp i under den första körningen.
- Under den andra körningen kan juryn också lägga till falska testfall som inte motsvarar något testfall från den första körningen. För dessa fall kommer vilket svar som helst av "
red", "green" eller "blue" att betraktas som korrekt; de behövs bara för att ditt program inte enkelt ska kunna skilja ett äkta testfall från ett falskt och skicka information mellan fallen. Således kan $t$ i den andra körningen överstiga $t$ i den första körningen. Det totala antalet äkta och falska fall kan inte överstiga $100$.
Exempel
Indata 1
1 1 green red blue red
Utdata 1
2
Indata 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
Utdata 2
blue BLUE blUE Blue