A og B, som har blitt valgt ut som Japans representanter til Den internasjonale informatikkolympiaden, har bestemt seg for å spille «Budbringerspillet» med direktør K i Den japanske komiteen for Den internasjonale informatikkolympiaden for å forbedre ferdighetene sine i informasjonsbehandling. Reglene for dette spillet er forklart nedenfor.

A og B er isolert i hvert sitt rom som vist på figuren. Selv om det er interntelefoner i rommene til A, B og direktør K, er det bare direktør K som kan starte en samtale. Andre kommunikasjonsmidler er kuttet, og A og B kan ikke forlate rommene sine med mindre de får beskjed om det.

Rommet til A | Lang korridor | Rommet til direktør K | Lang korridor | Rommet til B

Ved starten av spillet forteller direktør K et positivt heltall $X$ til A over telefonen. Målet med spillet er at A skal formidle verdien av $X$ korrekt til B uten direkte kommunikasjon mellom dem.

Rommet til direktør K har et $4 \times 4$-rutenett. La $(i, j)$ representere ruten i den $i$-te raden og den $j$-te kolonnen ($1 \le i \le 4, 1 \le j \le 4$). Rute $(1, 1)$ er øvre venstre hjørne, $(1, 4)$ er øvre høyre hjørne, $(4, 1)$ er nedre venstre hjørne og $(4, 4)$ er nedre høyre hjørne. Ved starten av spillet plasseres en brikke i én av rutene. Deretter vil ikke direktør K endre hvilken rute brikken står i.

Fra dette tidspunktet ringer direktør K gjentatte ganger enten A eller B inn til rommet per telefon. Hver gang A eller B kommer til rommet til direktør K, må vedkommende flytte brikken til en naborute (opp, ned, til venstre eller til høyre). Etter å ha flyttet brikken går A eller B tilbake til sitt eget rom. Hvis B vet verdien av $X$ når B kommer til rommet til direktør K, kan B svare denne verdien til direktør K i stedet for å flytte brikken. Hvis riktig verdi av $X$ blir svart, er det et riktig svar; ellers er det et feil svar.

Tidspunktene når direktør K kaller A eller B inn til rommet er uregelmessige, og A og B vet ikke i hvilken rekkefølge direktør K kaller de to inn til rommet. Direktør K bestemmer imidlertid rekkefølgen de to skal kalles inn i ved starten av spillet, og det er garantert at direktør K ikke vil kalle inn verken A eller B mer enn 100 ganger på rad. Hvis B ikke har svart verdien av $X$ etter at A eller B har gått tilbake til rommet sitt etter at direktør K har kalt inn A og B totalt 10,000 ganger, avsluttes spillet med feil svar.

Oppgave

Implementer strategiene for A og B, og lag et program som kan svare riktig i «Budbringerspillet» beskrevet ovenfor.

Implementeringsdetaljer

Du må sende inn to filer i samme programmeringsspråk.

Den første filen heter playerA.c eller playerA.cpp. Denne filen implementerer strategien til A og må implementere følgende rutiner:

• void InitA(int T, int X) Denne rutinen kalles nøyaktig én gang på begynnelsen. Argumentet T er deloppgavenummeret. Argumentet X er det positive heltallet som A må formidle til B.

• int GameA(int I, int J) Denne rutinen kalles når A kommer til rommet til direktør K. Argumentene I og J er heltallene som representerer ruten $(I, J)$ der brikken befinner seg når A ankommer rommet til direktør K, og de oppfyller $1 \le I \le 4$ og $1 \le J \le 4$. Denne rutinen må returnere ett av heltallene $-1, -2, -3, -4$. Hvis en hvilken som helst annen verdi returneres, bedømmes det som Wrong Answer [1] og programkjøringen avsluttes. Disse representerer følgende handlinger fra A:

  • $-1$: Flytt brikken til ruten over $(I - 1, J)$.
  • $-2$: Flytt brikken til ruten under $(I + 1, J)$.
  • $-3$: Flytt brikken til ruten til venstre $(I, J - 1)$.
  • $-4$: Flytt brikken til ruten til høyre $(I, J + 1)$. Hvis det angis et trekk som fører brikken utenfor brettet, bedømmes det som Wrong Answer [2] og programkjøringen avsluttes.

Den andre filen heter playerB.c eller playerB.cpp. Denne filen implementerer strategien til B og må implementere følgende rutiner:

• void InitB(int T) Denne rutinen kalles nøyaktig én gang på begynnelsen. Argumentet T er deloppgavenummeret.

• int GameB(int I, int J) Denne rutinen kalles når B kommer til rommet til direktør K. Argumentene I og J er heltallene som representerer ruten $(I, J)$ der brikken befinner seg når B ankommer rommet til direktør K, og de oppfyller $1 \le I \le 4$ og $1 \le J \le 4$. Denne rutinen må returnere ett av heltallene $-1, -2, -3, -4$, eller et positivt heltall $Y$. Hvis en hvilken som helst annen verdi returneres, bedømmes det som Wrong Answer [3] og programkjøringen avsluttes. Disse representerer følgende handlinger fra B:

  • $-1$: Flytt brikken til ruten over $(I - 1, J)$.
  • $-2$: Flytt brikken til ruten under $(I + 1, J)$.
  • $-3$: Flytt brikken til ruten til venstre $(I, J - 1)$.
  • $-4$: Flytt brikken til ruten til høyre $(I, J + 1)$. Hvis det angis et trekk som fører brikken utenfor brettet, bedømmes det som Wrong Answer [4] og programkjøringen avsluttes.
  • Positivt heltall $Y$: Svar til direktør K at verdien av $X$ er $Y$. Hvis $X = Y$, er det et riktig svar; ellers bedømmes det som Wrong Answer [5] og programkjøringen avsluttes.

Rutinene GameA og GameB vil ikke bli kalt mer enn 100 ganger på rad for noen av dem. Videre, hvis GameB ikke har returnert et positivt heltall innen GameA og GameB har blitt kalt totalt 10,000 ganger, bedømmes det som Wrong Answer [6] og programkjøringen avsluttes.

Du står fritt til å implementere andre rutiner eller deklarere globale variabler til internt bruk. Men siden de to innsendte programmene lenkes sammen med bedømmerprogrammet til én enkelt kjørbar fil, må du deklarere alle globale variabler og interne rutiner i hver fil som static for å unngå forstyrrelser med andre filer. Under bedømming kjøres dette programmet som to separate prosesser, én for A og én for B, så globale variabler kan ikke deles mellom A-siden og B-siden. Innsendingen din må ikke interagere med standard inndata/utdata eller andre filer på noen måte.

Inndata

Eksempelbedømmeren leser følgende inndata fra standard inndata:

• Den første linjen inneholder heltallene $T, X, I_0, J_0$ atskilt med mellomrom, som representerer deloppgavenummeret $T$, heltallet $X$ som A må formidle til B, og startposisjonen $(I_0, J_0)$ til brikken ved starten av spillet.
• Den andre linjen inneholder en streng med lengde nøyaktig 10,000 som består av to typer tegn, 'A' og 'B'. Hvis det $k$-te tegnet ($1 \le k \le 10,000$) er 'A' eller 'B', betyr det at den $k$-te rutinen som kalles etter at InitA og InitB er kalt, er henholdsvis GameA eller GameB.

Utdata

Hvis programmet avsluttes normalt, skriver eksempelbedømmeren ut følgende informasjon til standard utdata på én linje:

• Hvis det er riktig, skrives "Accepted" ut (anførselstegn skrives ikke faktisk ut; det samme gjelder nedenfor).
• Hvis det er feil, skrives typen feil svar ut som "Wrong Answer [1]" basert på tallene som står i delen "Implementeringsdetaljer". Videre, for Wrong Answer [5], skrives den riktige verdien av $X$ og det positive heltallet $Y$ returnert av rutinen GameB ut som Wrong Answer [5] : X = 2, Y = 3.

Begrensninger

Alle inndata oppfyller følgende betingelser:

• $1 \le X \le 1,000,000,000$.

Deloppgaver

Deloppgave 1 [20 poeng]

• Oppfyller $T = 1$.
• A kalles inn til rommet til direktør K først, og A og B kalles inn til rommet til direktør K annenhver gang. Det vil si at etter at InitA og InitB er kalt, kalles rutinene i rekkefølgen GameA, GameB, GameA, GameB, ...

Deloppgave 2 [20 poeng]

• Oppfyller $T = 2$.
• Posisjonen til brikken ved starten av spillet er $(I_0, J_0) = (1, 1)$. Det vil si at etter at InitA og InitB er kalt, kalles først rutinen GameA eller GameB med $I = 1, J = 1$ som argumenter.

Deloppgave 3 [60 poeng]

• Oppfyller $T = 3$.

Merk

Et eksempel på inndata lest av eksempelbedømmeren og et eksempel på de tilhørende rutinekallene er vist nedenfor.

Merk at dette eksempelet ikke nødvendigvis beskriver en meningsfull interaksjon.