זוהי בעיה אינטראקטיבית. זכרו לרוקן את חוצץ הפלט (flush) לאחר כל הדפסה. כדי לרוקן את הפלט, תוכלו להשתמש ב:

• fflush(stdout) או cout.flush() ב-C/C++;
• System.out.flush() ב-Java וב-Kotlin;
• sys.stdout.flush() ב-Python.

רעיון המשחק, מאויר על ידי Nano Banana Pro.

אתם משתתפים במשחק אסטרטגיה מבוסס-תורות הידוע בשם Revolver Roulette ("רולטת אקדח תופי").

המשחק מתחיל עם אקדח תופי הטעון ב-$6$ כדורים בדיוק. כל כדור הוא חי (live) או סרק (blank), באופן בלתי תלוי ובהסתברות שווה. שני השחקנים תמיד יודעים את המספר הנוכחי של כדורים חיים וכדורי סרק שנותרו בתוף, אך הסדר המדויק שלהם אינו ידוע.

כל שחקן מתחיל עם $5$ נקודות חיים (HP) ו-$2$ פריטים. אם ה-HP של שחקן יורד ל-$0$ או פחות, הוא מודח והשחקן השני מנצח. השחקנים מבצעים פעולות בתורות.

מהלך התור

במהלך תורו, השחקן הפעיל רשאי לבצע מספר כלשהו של הפעולות הבאות:

• להשתמש בכל פריט שהוא.
• לבצע כל פעולת ירי שהיא.

התור מסתיים רק כאשר פעולת ירי גורמת לתור לעבור לשחקן השני, או כאשר אחד השחקנים מודח.

פעולות ירי

השחקן הפעיל חייב לבחור אחת מפעולות הירי הבאות:

• Fire at Opponent: השחקן הפעיל יורה את הכדור הבא לעבר השחקן השני. אם הכדור חי, השחקן השני מאבד $1$ HP. ללא קשר לסוג הכדור, התור עובר לשחקן השני.
• Fire at Self: השחקן הפעיל יורה את הכדור הבא לעבר עצמו. אם הכדור חי, השחקן הפעיל מאבד $1$ HP, והתור עובר לשחקן השני. אחרת, אם מדובר בכדור סרק, השחקן הפעיל שומר על תורו וממשיך לבצע פעולות.

פריטים

כאשר נעשה שימוש בפריט, הוא מתכלה והשחקן הפעיל שומר על תורו, ללא קשר לסוג הפריט. הפריטים גלויים לשני השחקנים. כאשר שחקן מקבל פריט חדש (כולל כל אחד מהפריטים ההתחלתיים), הפריט נבחר באקראי בהתפלגות אחידה מתוך ארבעת הסוגים הבאים:

• Dummy: ירי הכדור הבא לעבר בובת אימונים. פעולה זו מכלה את הכדור ואינה נחשבת לפעולת ירי.
• Magnifier: הצצה בכדור הבא כדי לחשוף האם הכדור הבא חי או סרק. שני השחקנים לומדים מהי התוצאה.
• Converter: היפוך הסוג של הכדור הבא (חי $\leftrightarrow$ סרק). שני השחקנים רואים את הכמויות המעודכנות של כדורים חיים וכדורי סרק.

• Cage: קבלת אפקט חד-פעמי המונע מהתור להסתיים בפעולת הירי הבאה שבדרך כלל הייתה מסיימת אותו. ליתר דיוק:

  • אם השחקן מבצע לאחר מכן Fire at Opponent (בין אם הכדור חי ובין אם הוא סרק), האפקט פועל והתור אינו מסתיים.
  • אם השחקן מבצע לאחר מכן Fire at Self והכדור חי, האפקט פועל והתור אינו מסתיים (השחקן עדיין מאבד $1$ HP, אך שומר על התור).

  האפקט מתכלה מיד לאחר שהוא מופעל פעם אחת. ניתן להשתמש לכל היותר בפריט Cage אחד בכל תור.

טעינה מחדש (Reloading)

כאשר התוף מתרוקן, נטענים מיד $6$ כדורים חדשים (כל אחד מהם חי או סרק באופן בלתי תלוי ובהסתברות שווה). שני השחקנים מקבלים הודעה על הכמויות החדשות של כדורים חיים וכדורי סרק. בנוסף, כל שחקן מקבל השלמת פריטים עד ל-$2$ פריטים (שחקן עם $k$ פריטים מקבל $(2 - k)$ פריטים חדשים, שכל אחד מהם נבחר באופן בלתי תלוי ובאקראי בהתפלגות אחידה מתוך ארבעת הסוגים שלעיל).

מטרה

אתם השחקן שמשחק את התור הראשון, ומטרתכם היא לנצח במשחק על ידי הדחת היריב.

קלט

השורה הראשונה מכילה שני מספרים שלמים $n$ ו-$w$, המציינים שעליכם לנצח לפחות ב-$w$ מתוך $n$ משחקים כדי שהפתרון יתקבל. ישנם שלושה מבחנים בלבד:

• מבחן דוגמה: $n = 1$ ו-$w = 0$. ($0\%$)
• מבחן סודי 1: $n = 2\,000$ ו-$w = 1\,000$. ($50\%$)
• מבחן סודי 2: $n = 20\,000$ ו-$w = 11\,000$. ($55\%$)

ניתן להראות שכאשר שני השחקנים משחקים באופן אופטימלי, השחקן שמשחק את התור הראשון מנצח בכ-$56.89\%$ מהמשחקים.

פרוטוקול אינטראקציה

תחילת משחק

הפתרון שלכם מתפקד כשחקן שמשחק את התור הראשון מול האינטראקטור. בתחילת כל משחק, האינטראקטור מדפיס מספר שלם $g$:

• אם $g = 0$, כל המשחקים בהרצה הנוכחית הושלמו. על הפתרון שלכם להסתיים מיד.
• אחרת, $g$ הוא אינדקס המשחק הנוכחי ($1 \le g \le n$).

בשל אילוצים טכניים, הפתרון שלכם מורץ פעמיים בכל מבחן:

• האינטראקטור יכול להחליט האם להפעיל מחדש את הפתרון שלכם על ידי מתן $g = 0$ בכל עת.

תקבלו את אותם ערכי $n$ ו-$w$ בכל הרצה במבחן. לכן, $n$ אינו בהכרח שווה למספר המשחקים בהרצה הנוכחית. מובטח שכל משחק $1, \dots, n$ משוחק בדיוק פעם אחת על פני שתי ההרצות יחד. מלבד זאת, הפתרון שלכם יכול להתעלם בבטחה מתנאי ההרצה הכפולה.

מצב המשחק

לאחר מכן, האינטראקטור מדפיס את שורת מצב המשחק המכילה $13$ מספרים שלמים אי-שליליים:

$$t \quad l \quad b \quad h_1 \quad d_1 \quad m_1 \quad c_1 \quad k_1 \quad h_2 \quad d_2 \quad m_2 \quad c_2 \quad k_2$$

• $t \in \{0, 1, 2\}$: מצב התור.
• $l, b$ ($1 \le l + b \le 6$): הכמויות הנוכחיות של כדורים חיים וכדורי סרק שנותרו בתוף.
• $h_1$ ($0 \le h_1 \le 5$): ה-HP הנוכחי שלכם.
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): מספר הפריטים מסוג Dummy, Magnifier, Converter ו-Cage שאתם מחזיקים כעת.
• $h_2$ ($0 \le h_2 \le 5$): ה-HP הנוכחי של היריב שלכם.
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): מספר הפריטים מסוג Dummy, Magnifier, Converter ו-Cage שהיריב שלכם מחזיק.

מקרה $t = 0$ (המשחק הסתיים)

המשחק הנוכחי הסתיים. האינטראקטור ממשיך למשחק הבא (מדפיס את ה-$g$ החדש).

מקרה $t = 1$ (התור שלכם)

עליכם להדפיס מספר שלם כדי לבחור פעולה:

1. Fire at Opponent.
2. Fire at Self.
3. שימוש בפריט Dummy.
4. שימוש בפריט Magnifier.
5. שימוש בפריט Converter.
6. שימוש בפריט Cage.

אם הפעולה אינה חוקית (למשל, שימוש בפריט שאין לכם, או שימוש בפריט Cage יותר מפעם אחת באותו תור), מצב המשחק נשאר ללא שינוי, והאינטראקטור מדפיס $0$ ואת אותה שורת מצב ($13$ מספרים שלמים) שוב. למרות שעדיין תורכם, עליכם לבצע פעולה חוקית אחרת כדי להמשיך במשחק.

אחרת, הפעולה תקפה והאינטראקטור מדפיס מספר שלם המייצג את התוצאה:

• עבור פעולות $1$–$5$: מחזיר $1$ אם הכדור הבא לפני הפעולה הוא חי, ו-$2$ אם הוא סרק.
• עבור פעולה $6$: מחזיר $1$ (לא נחשף מידע על הכדור).

לאחר מכן האינטראקטור מדפיס את שורת מצב המשחק המעודכנת.

מקרה $t = 2$ (תור היריב)

האינטראקטור מדמה את פעולת היריב שלכם ומדפיס שתי שורות:

• מזהה הפעולה $a \in \{1, \dots, 6\}$.
• מספר התוצאה השלם ($1$ או $2$ כפי שתואר לעיל).

היריב שלכם לעולם אינו מבצע פעולה לא חוקית. מיד לאחר מכן, האינטראקטור מדפיס את שורת מצב המשחק הבאה ($13$ מספרים שלמים).

עבור כל סיבוב במשחק, סימולטור המשחק משתמש במחולל מספרים פסאודו-אקראיים עם גרעין אקראי (seed) קבוע. כמו כן, היריב באינטראקטור נוקט אסטרטגיה דטרמיניסטית. ההחלטה להפעיל מחדש את הפתרון שלכם אינה תלויה בתהליך האינטראקציה. לכן, אותה סדרת פעולות תמיד מובילה לאותו מצב משחק.

כלי בדיקה מסופק כדי לסייע לכם בפיתוח ובבדיקת הפתרון שלכם.

דוגמה

דוגמה 1, מעבר 1

קלט

1 0
1
1 3 3 5 0 0 0 2 5 1 0 1 0

1
1 3 3 5 0 0 0 1 5 1 0 1 0

1
1 2 3 5 0 0 0 1 4 1 0 1 0

0
1 2 3 5 0 0 0 1 4 1 0 1 0

2
1 2 2 5 0 0 0 1 4 1 0 1 0

1
2 1 2 5 0 0 0 1 3 1 0 1 0
5
2
2 2 1 5 0 0 0 1 3 1 0 0 0
1
1
1 1 1 4 0 0 0 1 3 1 0 0 0

1
2 0 1 4 0 0 0 1 2 1 0 0 0
3
2
2 2 4 4 0 1 0 1 2 0 1 0 1
2
1
1 1 4 4 0 1 0 1 1 0 1 0 1

1
1 1 4 4 0 0 0 1 1 0 1 0 1

1
0 0 4 4 0 0 0 1 0 0 1 0 1
0

פלט

6


1


6


2


1








1








4


1

דוגמה 1, מעבר 2

קלט

1 0
0

פלט