Dette er et interaktivt problem. Husk å tømme utdatabufferen (flush) etter hver utskrift. For å tømme utdataen din kan du bruke:

• fflush(stdout) eller cout.flush() i C/C++;
• System.out.flush() i Java og Kotlin;
• sys.stdout.flush() i Python.

Konseptet i spillet, illustrert av Nano Banana Pro.

Du deltar i et strategisk turbasert spill kjent som Revolver Roulette.

Spillet starter med en revolver ladet med nøyaktig $6$ patroner. Hver patron er uavhengig og med lik sannsynlighet enten skarp (live) eller løs (blank). Begge spillerne vet alltid det nåværende antallet skarpe og løse patroner som er igjen i tønnen, men den nøyaktige rekkefølgen er ukjent.

Hver spiller starter med $5$ helsepoeng (HP) og $2$ gjenstander. Hvis en spillers HP faller til $0$ eller lavere, blir spilleren eliminert og den andre spilleren vinner. Spillerne bytter på å utføre handlinger.

Turprosedyre

I løpet av sin tur kan den aktive spilleren utføre et hvilket som helst antall av følgende handlinger:

• Bruke en hvilken som helst gjenstand.
• Utføre en hvilken som helst skytehandling.

Turen avsluttes bare når en skytehandling fører til at turen går over til den andre spilleren, eller når en spiller blir eliminert.

Skytehandlinger

Den aktive spilleren må velge én av følgende skytehandlinger:

• Fire at Opponent: Den aktive spilleren skyter neste patron mot den andre spilleren. Hvis den er skarp, mister den andre spilleren $1$ HP. Uavhengig av patrontype går turen over til den andre spilleren.
• Fire at Self: Den aktive spilleren skyter neste patron mot seg selv. Hvis den er skarp, mister den aktive spilleren $1$ HP, og turen går over til den andre spilleren. Ellers, hvis det er en løspatron, beholder den aktive spilleren turen og fortsetter å utføre handlinger.

Gjenstander

Når en gjenstand brukes, blir den brukt opp, og den aktive spilleren beholder turen uavhengig av gjenstandstype. Gjenstandene er synlige for begge spillerne. Når en spiller får en ny gjenstand (inkludert hver av startgjenstandene), velges den uniformt tilfeldig blant følgende fire typer:

• Dummy: Skyt neste patron mot en treningsdukke. Dette bruker opp patronen og regnes ikke som en skytehandling.
• Magnifier: Kikk på neste patron for å avsløre om neste patron er skarp eller løs. Begge spillerne får vite resultatet.
• Converter: Snu typen til neste patron (skarp $\leftrightarrow$ løs). Begge spillerne observerer det oppdaterte antallet skarpe og løse patroner.

• Cage: Få en engangseffekt som hindrer at turen avsluttes ved neste skytehandling som normalt ville avsluttet den. Mer spesifikt:

  • Hvis spilleren senere utfører Fire at Opponent (uavhengig av om patronen er skarp eller løs), trer effekten i kraft og turen avsluttes ikke.
  • Hvis spilleren senere utfører Fire at Self og patronen er skarp, trer effekten i kraft og turen avsluttes ikke (spilleren mister fortsatt $1$ HP, men beholder turen).

  Effekten brukes opp umiddelbart etter at den har virket én gang. Høyst én Cage-gjenstand kan brukes per tur.

Omlading (Reloading)

Når tønnen er tom, lades det umiddelbart $6$ nye patroner (hver uavhengig skarp eller løs med lik sannsynlighet). Begge spillerne blir informert om det nye antallet skarpe og løse patroner. I tillegg får hver spiller fylt opp gjenstandene sine til opptil $2$ gjenstander (en spiller med $k$ gjenstander mottar $(2 - k)$ nye gjenstander, hver uavhengig valgt uniformt tilfeldig blant de fire typene ovenfor).

Mål

Du er spilleren som tar den første turen, og målet ditt er å vinne spillet ved å eliminere motstanderen din.

Inndata

Den første linjen inneholder to heltall $n$ og $w$, som angir at du må vinne minst $w$ av $n$ spill for å bli godkjent. Det er bare tre tester:

• Eksempeltest: $n = 1$ og $w = 0$. ($0\%$)
• Hemmelig test 1: $n = 2\,000$ og $w = 1\,000$. ($50\%$)
• Hemmelig test 2: $n = 20\,000$ og $w = 11\,000$. ($55\%$)

Det kan vises at når begge spillerne spiller optimalt, vinner spilleren som tar den første turen omtrent $56.89\%$ av spillene.

Interaksjonsprotokoll

Spillstart

Løsningen din opptrer som spilleren som tar den første turen mot interaktoren. Ved starten av hvert spill skriver interaktoren ut et heltall $g$:

• Hvis $g = 0$, er alle spillene i den nåværende kjøringen fullført. Løsningen din må avslutte umiddelbart.
• Ellers er $g$ den nåværende spillindeksen ($1 \le g \le n$).

På grunn av tekniske årsaker kjøres løsningen din to ganger på hver test:

• Interaktoren kan når som helst bestemme seg for å starte løsningen din på nytt ved å gi $g = 0$.

Du vil motta de samme $n$ og $w$ for hver kjøring i en test. Derfor er $n$ ikke alltid lik antallet spill i den nåværende kjøringen. Det garanteres at hvert spill $1, \dots, n$ spilles nøyaktig én gang i løpet av de to kjøringene. Bortsett fra dette kan løsningen din trygt ignorere betingelsen om to kjøringer.

Spilltilstand

Deretter skriver interaktoren ut spilltilstandslinjen som inneholder $13$ ikke-negative heltall:

$$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\}$: turstatus.
• $l, b$ ($1 \le l + b \le 6$): det nåværende antallet skarpe og løse patroner som er igjen i tønnen.
• $h_1$ ($0 \le h_1 \le 5$): dine nåværende HP.
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): antallet Dummy-, Magnifier-, Converter- og Cage-gjenstander du har for øyeblikket.
• $h_2$ ($0 \le h_2 \le 5$): motstanderens nåværende HP.
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): antallet Dummy-, Magnifier-, Converter- og Cage-gjenstander motstanderen din har.

Tilfelle $t = 0$ (Spillet er over)

Det nåværende spillet er avsluttet. Interaktoren går videre til neste spill (ved å skrive ut den nye $g$).

Tilfelle $t = 1$ (Din tur)

Du må skrive ut et heltall for å velge en handling:

1. Fire at Opponent.
2. Fire at Self.
3. Bruk en Dummy-gjenstand.
4. Bruk en Magnifier-gjenstand.
5. Bruk en Converter-gjenstand.
6. Bruk en Cage-gjenstand.

Hvis handlingen er ugyldig (f.eks. å bruke en gjenstand du ikke har, eller å bruke en Cage-gjenstand mer enn én gang i samme tur), forblir spilltilstanden uendret, og interaktoren skriver ut $0$ og den samme tilstandslinjen ($13$ heltall) på nytt. Selv om det fortsatt er din tur, må du utføre en annen gyldig handling for å fortsette spillet.

Ellers er handlingen gyldig, og interaktoren skriver ut etangitt resultatheltall:

• For handlingene $1$–$5$: Returnerer $1$ hvis neste patron før handlingen er skarp, $2$ hvis den er løs.
• For handling $6$: Returnerer $1$ (ingen patroninformasjon avsløres).

Interaktoren skriver deretter ut den oppdaterte spilltilstandslinjen.

Tilfelle $t = 2$ (Motstanderens tur)

Interaktoren simulerer motstanderens handling og skriver ut to linjer:

• Handlings-ID $a \in \{1, \dots, 6\}$.
• Resultatheltallet ($1$ eller $2$ som beskrevet ovenfor).

Motstanderen din utfører aldri en ulovlig handling. Umiddelbart etterpå skriver interaktoren ut neste spilltilstandslinje ($13$ heltall).

For hver runde av spillet bruker spillsimulatoren en pseudotilfeldig tallgenerator med et fast tilfeldig frø (seed). I tillegg bruker motstanderen i interaktoren en deterministisk strategi. Beslutningen om å starte løsningen din på nytt er uavhengig av interaksjonsprosedyren. Derfor fører den samme sekvensen av handlinger alltid til den samme spilltilstanden.

Et testverktøy er tilgjengelig for å hjelpe deg med å utvikle og teste løsningen din.

Eksempel

Eksempel 1, Omgang 1

Inndata

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

Utdata

6


1


6


2


1








1








4


1

Eksempel 1, Omgang 2

Inndata

1 0
0

Utdata