Anna og Bruno er gamblermestere. De skal spille et spill med D-taro, som er kortgiveren i spillet.

I dette spillet oppholder Anna og Bruno seg i forskjellige rom. De kan kun kommunisere med hverandre ved hjelp av en ødelagt enhet. D-taro gir et heltall til Anna. For Anna og Bruno er hensikten med dette spillet å sende det oppgitte heltallet fra Anna til Bruno ved hjelp av enheten.

Når spillet starter, erklærer Anna helt i begynnelsen et heltall $m$ mellom $1$ og $2\,000$, inkludert. Deretter spiller de $Q$ runder. Runde $i$ ($1\le i\le Q$) gjennomføres som følger.

1. D-taro gir et heltall $A_i$ til Anna.
2. Anna legger inn tabellene $s_i,t_i$ i enheten. Hvert element i tabellene $s_i,t_i$ skal være enten $0$ eller $1$. Tabellene $s_i,t_i$ skal ha samme lengde, og lengden er mellom $1$ og $m$, inkludert.
3. La $u_i$ være en tabell oppnådd fra tabellene $s_i$ og $t_i$ ved riffle-stokk (riffle shuffle, se nedenfor). Deretter sender enheten $u_i$ til Bruno.
4. Bruno sender et heltall til D-taro. Hvis dette heltallet er det samme som heltallet $A_i$ gitt av D-taro til Anna, vinner Anna og Bruno denne runden.

Skriv programmer som implementerer strategiene til Anna og Bruno slik at de vinner alle de $Q$ rundene.

Riffle-stokk

Vi sier at en tabell $Z$ er oppnådd fra tabellene $X$ og $Y$ ved riffle-stokk hvis vi kan dele elementene i tabellen $Z$ inn i to grupper slik at følgende to betingelser er oppfylt.

• Tabellen som består av elementene i den første gruppen i samme rekkefølge, er lik tabellen $X$.
• Tabellen som består av elementene i den andre gruppen i samme rekkefølge, er lik tabellen $Y$.

For eksempel er tabellen $Z=[1,1,1,0,0,0]$ oppnådd fra $X=[1,1,0]$ og $Y=[1,0,0]$ ved riffle-stokk fordi tabellen som består av det første, andre og fjerde elementet i $Z$ i samme rekkefølge er tabellen $[1,1,0]$, og tabellen som består av det tredje, femte og sjette elementet i $Z$ i samme rekkefølge er tabellen $[1,0,0]$.

På den annen side, hvis $X=[1,1,0]$, $Y=[1,0,0]$ og $Z=[0,0,0,1,1,1]$, er ikke tabellen $Z$ oppnådd fra $X$ og $Y$ ved riffle-stokk.

Implementeringsdetaljer

Du må sende inn to filer.

Den første filen er Anna.cpp. Den skal implementere Annas strategi. Den skal implementere følgende funksjoner. Programmet skal inkludere Anna.h ved hjelp av preprosessordirektivet #include.

• int Declare()

  Denne funksjonen kalles én gang i begynnelsen.

  • Returverdien er heltallet $m$ erklært av Anna.
  • Heltallet $m$ skal være mellom $1$ og $2\,000$, inkludert. Hvis denne betingelsen ikke er oppfylt, bedømmes programmet ditt som Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Etter at funksjonen Declare er kalt, kalles denne funksjonen $Q$ ganger. Det $i$-te kallet ($1\le i\le Q$) til denne funksjonen tilsvarer Steg 1 og Steg 2 for runde $i$.

  • Parameteren A er heltallet $A_i$ gitt av D-taro til Anna.
  • Returverdien er paret av de to tabellene $s_i,t_i$ lagt inn av Anna i enheten.
  • Hvert element i tabellene $s_i,t_i$ skal være enten $0$ eller $1$. Hvis denne betingelsen ikke er oppfylt, bedømmes programmet ditt som Wrong Answer [2].
  • Begge lengdene til tabellene $s_i,t_i$ skal være mellom $1$ og $m$, inkludert. Hvis denne betingelsen ikke er oppfylt, bedømmes programmet ditt som Wrong Answer [3].
  • Tabellene $s_i,t_i$ skal ha samme lengde. Hvis denne betingelsen ikke er oppfylt, bedømmes programmet ditt som Wrong Answer [4].

Den andre filen er Bruno.cpp. Den skal implementere Brunos strategi. Den skal implementere følgende funksjon. Programmet skal inkludere Bruno.h ved hjelp av preprosessordirektivet #include.

• long long Bruno(std::vector<int> u)

  Etter at Anna legger inn tabellene i enheten, kalles denne funksjonen én gang. Totalt kalles denne funksjonen $Q$ ganger. Det $i$-te kallet ($1\le i\le Q$) til denne funksjonen tilsvarer Steg 3 og Steg 4 for runde $i$.

  • Parameteren u er tabellen $u_i$ sendt av enheten til Bruno for runde $i$.
  • Returverdien er heltallet sendt av Bruno til D-taro.
  • Returverdien skal være den samme som heltallet $A_i$ gitt av D-taro til Anna. Hvis denne betingelsen ikke er oppfylt, bedømmes programmet ditt som Wrong Answer [5].

Viktige merknader

• Programmet ditt kan implementere andre funksjoner for intern bruk, eller bruke globale variabler. Innsendte filer vil bli kompilert med graderen, og bli til én enkelt kjørbar fil. Alle globale variabler og interne funksjoner bør deklareres i et navnløst navnerom (unnamed namespace) for å unngå konflikter med andre filer. Når det bedømmes, vil det bli kjørt som to prosesser for Anna og Bruno. Prosessen til Anna og prosessen til Bruno kan ikke dele globale variabler.
• Programmet ditt må ikke bruke standard inndata eller standard utdata. Programmet ditt må ikke kommunisere med andre filer på noen måte. Programmet ditt kan imidlertid skrive ut feilsøkingsinformasjon til standard feilutdata (standard error).

Kompilering og testkjøring

Du kan laste ned en arkivfil fra konkurransens nettside som inneholder eksempelgraderen for å teste programmet ditt. Arkivfilen inneholder også en eksempelkildefil for programmet ditt.

Eksempelgraderen er filen grader.cpp. For å teste programmet ditt, legg grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h i samme mappe, og kjør følgende kommando for å kompilere programmene dine.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Når kompileringen lykkes, genereres den kjørbare filen grader.

Merk at den faktiske graderen er forskjellig fra eksempelgraderen. Eksempelgraderen vil bli kjørt som en enkelt prosess, som vil lese inndata fra standard inndata og skrive resultatene til standard utdata.

Inndata for eksempelgraderen

Eksempelgraderen leser følgende data fra standard inndata.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Utdata fra eksempelgraderen

Eksempelgraderen skriver ut følgende informasjon til standard utdata (anførselstegn for klarhet).

• Hvis programmet ditt bedømmes som riktig, skriver den returverdien $m$ fra funksjonen Declare som “Accepted: 2000”.
• Hvis programmet ditt bedømmes som en av Wrong Answer, skriver eksempelgraderen typen som “Wrong Answer [1]”.

Hvis programmet ditt oppfyller betingelsene for flere typer Wrong Answer, rapporterer eksempelgraderen bare én av dem.

Når eksempelgraderen kjøres, beregnes riffle-stokken for hver runde ved hjelp av pseudotilfeldige tall. Resultatene deres endres ikke mellom kjøringer. For å endre frøet (seed) til de pseudotilfeldige tallene, kjør eksempelgraderen på følgende måte.

./grader 2022

Det første argumentet skal være et heltall.

Begrensninger

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Deloppgaver

1. (5 poeng) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 poeng) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 poeng) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 poeng) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 poeng) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 poeng) Ingen ytterligere begrensninger. For denne deloppgaven beregnes poengsummen din som følger.

   • La $m^*$ være maksimum av heltallene $m$ erklært av Anna for alle testtilfeller i denne deloppgaven.
   • Poengsummen din er som følger.

Eksempler

Her er et eksempel på inndata for eksempelgraderen og tilhørende funksjonskall.

Inndata 1

2
42
2000

Eksempel på funksjonskall

I disse eksempeldataene er det $Q\ (=2)$ runder. For runde 1 gir D-taro heltallet $A_1\ (=42)$ til Anna. For runde 2 gir D-taro heltallet $A_2\ (=2000)$ til Anna.

Disse eksempeldataene tilfredsstiller begrensningene i alle deloppgavene.