這是一道執行兩次(run-twice)的題目;兩次執行皆為互動式。
在一棵寬闊的橡樹周圍站著四位智者。每位智者的頭上都戴著一頂紅色、綠色或藍色的帽子。每位智者都能看到他左右兩側鄰居的帽子顏色,但看不到自己帽子的顏色(帽子沒有遮住眼睛),也看不到對面智者的帽子顏色(被寬闊的橡樹擋住了)。每位智者必須在不與其他人交流的情況下,在一張紙上寫下自己帽子的顏色。請設計一個協定,使得四位智者中至少有一位必定能猜中自己帽子的顏色。
互動協定
第一行包含兩個整數 $t$ 和 $s$,分別表示測試資料的組數與解答的執行編號($1 \le t \le 100$;$s \in \{1, 2\}$)。接下來是 $t$ 組測試資料的描述,每組各佔一行。
如果 $s = 1$,測試資料包含四個單字 $c_1$、$c_2$、$c_3$ 和 $c_4$,表示參與者的帽子顏色($c_i \in \{\texttt{red}, \texttt{green}, \texttt{blue}\}$)。作為回應,請輸出一行包含一個整數 $m$($1 \le m \le 4$),表示根據你的協定,將會猜中自己帽子顏色的智者編號(若有多位,輸出任意一位即可)。
如果 $s = 2$,測試資料包含一個整數 $m$ 以及兩個單字 $\ell$ 和 $r$,分別表示必須猜測自己帽子顏色的智者編號,以及其左側與右側鄰居的帽子顏色($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}$)。作為回應,請輸出一行包含一個單字 $g$,代表第 $m$ 位智者帽子的顏色。當 $g = c_m$ 時答案將被接受。互動器不區分大小寫,因此你可以用任意大小寫(大寫或小寫)輸出每個字母。
為了防止在測試資料之間傳遞資訊,裁判採取了以下措施:
- 兩次執行皆為互動式。因此,在你輸出前面所有測試資料的答案之前,你不會收到下一組測試資料。在印出每一行之後,請別忘了清空輸出緩衝區(例如在 C++ 中使用
fflush(stdout)或cout.flush(),在 Python 中使用sys.stdout.flush(),或在 Java 或 Kotlin 中使用System.out.flush())。否則,你很可能會收到 Idleness Limit Exceeded 錯誤。 - 在第二次執行期間,裁判可能會以任意順序重新排列這 $t$ 組測試資料,該順序可能與第一次執行時出現的順序不同。
- 在第二次執行期間,裁判也可能加入偽造的測試資料,這些資料不對應第一次執行中的任何測試資料。對於這些資料,回答「
red」、「green」或「blue」中的任何一個都會被視為正確;它們僅是為了讓你的程式無法輕易區分真實測試資料與偽造測試資料,從而無法在測試資料之間傳遞資訊。因此,第二次執行中的 $t$ 可能會大於第一次執行中的 $t$。真實與偽造測試資料的總數不會超過 $100$。
範例
輸入範例 1
1 1 green red blue red
輸出範例 1
2
輸入範例 2
4 2 2 blue green 4 red blue 3 red red 4 red blue
輸出範例 2
blue BLUE blUE Blue