זוהי בעיית הרצה-כפולה (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$. האינטראקטור אינו תלוי-רישיות (case-insensitive), כך שניתן להדפיס כל אות בכל צורה (אותיות גדולות או קטנות).
כדי למנוע העברת מידע בין מקרי בדיקה, חבר השופטים נקט באמצעים הבאים:
- שתי ההרצות הן אינטראקטיביות. לכן, לא תקבל את מקרה הבדיקה הבא עד שתדפיס את התשובה לכל המקרים הקודמים. לאחר הדפסת כל שורה, אל תשכח לרוקן את זרם הפלט (לדוגמה, באמצעות
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