Tämä on kahdesti ajettava (run-twice) tehtävä; molemmat ajokerrat ovat vuorovaikutteisia.
Leveän tammen ympärillä seisoo neljä tietäjää. Jokaisella tietäjällä on päässään punainen, vihreä tai sininen hattu. Jokainen tietäjä näkee molempien naapuriensa hattujen värit, mutta ei näe oman hattunsa väriä (hattu ei roiku silmien edessä) eikä vastapäätä seisovan tietäjän hatun väriä (joka jää leveän tammen taakse). Jokaisen tietäjän täytyy, kommunikoimatta muiden kanssa, kirjoittaa oman hattunsa väri paperille. Kehitä protokolla, jonka avulla vähintään yksi neljästä tietäjästä arvaa varmasti oman hattunsa värin.
Vuorovaikutusprotokolla
Ensimmäinen rivi sisältää kaksi kokonaislukua $t$ ja $s$, jotka ilmaisevat testitapausten lukumäärän ja ratkaisun ajokerran numeron ($1 \le t \le 100$; $s \in \{1, 2\}$). Tämän jälkeen seuraa $t$ testitapauksen kuvaukset, kukin omalla rivillään.
Jos $s = 1$, testitapaus koostuu neljästä sanasta, $c_1$, $c_2$, $c_3$ ja $c_4$, jotka ilmaisevat osallistujien hattujen värit ($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$). Tulosta vastauksena rivi, jolla on yksi kokonaisluku $m$ ($1 \le m \le 4$), joka ilmaisee sen tietäjän numeron, joka protokollasi mukaan arvaa hattunsa värin (jos heitä on useita, tulosta mikä tahansa).
Jos $s = 2$, testitapaus koostuu kokonaisluvusta $m$ sekä kahdesta sanasta $\ell$ ja $r$, jotka ilmaisevat sen tietäjän numeron, jonka täytyy arvata hattunsa väri, sekä hänen vasemman ja oikean naapurinsa hattujen värit ($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}$). Tulosta vastauksena rivi, jolla on sana $g$, joka on $m$-nnen tietäjän hatun väri. Vastaus hyväksytään, jos $g = c_m$. Tarkastin ei erottele isoja ja pieniä kirjaimia, joten voit tulostaa jokaisen kirjaimen missä tahansa kirjainkoossa (isona tai pienenä).
Estääkseen tiedon välittämisen testitapausten välillä tuomaristo on ryhtynyt seuraaviin toimiin:
- Molemmat ajokerrat ovat vuorovaikutteisia. Et siis saa seuraavaa testitapausta ennen kuin olet tulostanut vastauksen kaikkiin edellisiin. Jokaisen rivin tulostamisen jälkeen muista tyhjentää tulostuspuskuri (esimerkiksi käyttämällä
fflush(stdout)taicout.flush()C++:ssa,sys.stdout.flush()Pythonissa taiSystem.out.flush()Javassa tai Kotlinissa). Muutoin saat todennäköisesti Idleness Limit Exceeded -virheen. - Toisen ajokerran aikana tuomaristo voi järjestää $t$ testitapausta uudelleen mihin tahansa järjestykseen, joka ei välttämättä vastaa ensimmäisen ajokerran järjestystä.
- Toisen ajokerran aikana tuomaristo voi myös lisätä valetestitapauksia, jotka eivät vastaa mitään ensimmäisen ajokerran testitapausta. Näissä tapauksissa mikä tahansa vastauksista "
red", "green" tai "blue" katsotaan oikeaksi; niitä tarvitaan vain siksi, ettei ohjelmasi pystyisi helposti erottamaan oikeaa testitapausta valetapauksesta ja välittämään tietoa tapausten välillä. Näin ollen toisen ajokerran $t$ voi olla suurempi kuin ensimmäisen ajokerran $t$. Oikeiden ja valetapausten kokonaismäärä on enintään $100$.
Esimerkit
Syöte 1
1 1 green red blue red
Tuloste 1
2
Syöte 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
Tuloste 2
blue BLUE blUE Blue