Бұл — интерактивті есеп. Әрбір шығарудан кейін шығыс буферін тазартуды (flush) ұмытпаңыз. Шығысты тазарту үшін келесіні пайдалана аласыз:

• C/C++ тілдерінде fflush(stdout) немесе cout.flush();
• Java және Kotlin тілдерінде System.out.flush();
• Python тілінде sys.stdout.flush().

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$ сандары берілген, бұл шешіміңіз қабылдануы үшін $n$ ойынның кемінде $w$ ойынында жеңіске жетуіңіз керек екенін білдіреді. Барлығы тек үш тест бар:

• Мысал тест: $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

Шығыс деректер