Dette er et run-twice-problem (to kjøringer); begge kjøringene er interaktive.
Rundt et bredt eiketre står fire vismenn. Hver vismann har en rød, grønn eller blå hatt på hodet. Hver vismann kan se fargene på hattene til begge naboene sine, men kan ikke se sin egen hattefarge (hatten henger ikke ned over øynene deres) eller fargen på hatten til vismannen rett overfor dem (som er blokkert av det brede eiketreet). Hver vismann må, uten å kommunisere med de andre, skrive ned fargen på hatten sin på et papirark. Utvikle en protokoll slik at minst én av de fire vismennene helt sikkert vil gjette riktig farge på hatten sin.
Interaksjonsprotokoll
Den første linjen inneholder to heltall $t$ og $s$, som angir antallet testtilfeller og kjøringsnummeret for løsningen ($1 \le t \le 100$; $s \in \{1, 2\}$). Deretter følger beskrivelser av $t$ testtilfeller, hvert på en egen linje.
Hvis $s = 1$, består testtilfellet av fire ord, $c_1$, $c_2$, $c_3$ og $c_4$, som angir fargene på deltakernes hatter ($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$). Som svar skal du skrive ut en linje med et enkelt heltall $m$ ($1 \le m \le 4$), som angir nummeret på vismannen som ifølge protokollen din vil gjette fargen på hatten sin (hvis det er flere, kan du skrive ut hvem som helst av dem).
Hvis $s = 2$, består testtilfellet av et heltall $m$ og to ord, $\ell$ og $r$, som angir nummeret på vismannen som må gjette fargen på hatten sin, samt fargene på hattene til hans venstre og høyre nabo ($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 skal du skrive ut en linje med et ord $g$ som er fargen på hatten til den $m$-te vismannen. Svaret blir godkjent hvis $g = c_m$. Interaktoren skiller ikke mellom store og små bokstaver, så du kan skrive ut hver bokstav som enten stor eller liten bokstav.
For å forhindre at informasjon overføres mellom testtilfeller, har juryen iverksatt følgende tiltak:
- Begge kjøringene er interaktive. Dermed vil du ikke motta det neste testtilfellet før du har skrevet ut svaret på alle de foregående. Etter å ha skrevet ut hver linje, må du ikke glemme å tømme utstrømmen (for eksempel ved å bruke
fflush(stdout)ellercout.flush()i C++,sys.stdout.flush()i Python, ellerSystem.out.flush()i Java eller Kotlin). Ellers vil du sannsynligvis få en Idleness Limit Exceeded-feil. - Under den andre kjøringen kan juryenstokke om på de $t$ testtilfellene i hvilken som helst rekkefølge, som ikke nødvendigvis samsvarer med rekkefølgen de dukket opp i under den første kjøringen.
- Under den andre kjøringen kan juryen også legge til falske testtilfeller som ikke tilsvarer noe testtilfelle fra den første kjøringen. For disse tilfellene vil ethvert svar blant «
red», «green» eller «blue» bli regnet som riktig; de er kun nødvendige for at programmet ditt ikke lett skal kunne skille et ekte testtilfelle fra et falskt og sende informasjon mellom tilfellene. Dermed kan $t$ i den andre kjøringen overstige $t$ i den første kjøringen. Det totale antallet ekte og falske tilfeller kan ikke overstige $100$.
Eksempler
Inndata 1
1 1 green red blue red
Utdata 1
2
Inndata 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
Utdata 2
blue BLUE blUE Blue