นี่คือโจทย์แบบรันสองครั้ง (run-twice) โดยทั้งสองครั้งเป็นการทำงานแบบโต้ตอบ (interactive)
รอบต้นโอ๊กที่กว้างใหญ่มีนักปราชญ์สี่คนยืนอยู่ นักปราชญ์แต่ละคนสวมหมวกสีแดง สีเขียว หรือสีน้ำเงินอยู่บนศีรษะ นักปราชญ์แต่ละคนสามารถมองเห็นสีหมวกของเพื่อนบ้านทั้งสองข้างของตนได้ แต่ไม่สามารถมองเห็นสีหมวกของตนเอง (หมวกไม่ได้ห้อยลงมาบังตา) หรือสีหมวกของนักปราชญ์ที่อยู่ฝั่งตรงข้าม (ซึ่งถูกต้นโอ๊กที่กว้างใหญ่บังไว้) นักปราชญ์แต่ละคนจะต้องเขียนสีหมวกของตนเองลงบนกระดาษโดยไม่สื่อสารกับคนอื่น จงพัฒนาโปรโตคอลที่ทำให้นักปราชญ์อย่างน้อยหนึ่งคนจากทั้งสี่คนทายสีหมวกของตนเองได้อย่างถูกต้องแน่นอน
โปรโตคอลการโต้ตอบ
บรรทัดแรกประกอบด้วยจำนวนเต็มสองตัวคือ $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$ โปรแกรมตรวจไม่สนใจตัวพิมพ์ใหญ่หรือเล็ก ดังนั้นคุณจึงสามารถพิมพ์แต่ละตัวอักษรเป็นตัวพิมพ์ใหญ่หรือตัวพิมพ์เล็กก็ได้
เพื่อป้องกันการส่งผ่านข้อมูลระหว่างชุดข้อมูลทดสอบ คณะกรรมการจึงได้ใช้มาตรการดังต่อไปนี้:
- การรันทั้งสองครั้งเป็นแบบโต้ตอบ ดังนั้นคุณจะไม่ได้รับชุดข้อมูลทดสอบถัดไปจนกว่าคุณจะแสดงผลคำตอบของชุดข้อมูลทดสอบก่อนหน้าทั้งหมด หลังจากพิมพ์แต่ละบรรทัด อย่าลืมล้างบัฟเฟอร์เอาต์พุต (เช่น ใช้
fflush(stdout)หรือcout.flush()ใน C++,sys.stdout.flush()ใน Python หรือSystem.out.flush()ใน Java หรือ Kotlin) มิฉะนั้น คุณอาจได้รับข้อผิดพลาด 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