Anna og Bruno er arkeologer. De undersøker ruiner i Iran.

Oppgavene deres er som følger: Anna besøker ruiner og oppdager gjenstander, og Bruno analyserer resultatene i hovedleiren.

Undersøkelsen deres er planlagt å vare i $Q(=1\,000)$ dager. Hver dag sender Anna resultatene til Bruno ved hjelp av en kommunikasjonsenhet. Resultatene for hver dag uttrykkes som et heltall $X$.

Anna kan bare bruke kommunikasjonsenheten én gang om dagen. Den kan sende en sekvens med lengde $N(=150)$ som består av $0$ eller $1$.

Men den var ødelagt. Det er flere ødelagte plasser i sekvensen med lengde $N$. På en ødelagt plass sender den alltid verdien $0$ uavhengig av den faktisk innstilte verdien. Når Anna sender en sekvens, kan hun se posisjonene til de ødelagte plassene. Men Bruno kjenner dem ikke. Posisjonene til de ødelagte plassene og antallet ødelagte plasser kan endre seg hver dag.

Det er fare for at undersøkelsen deres blir forsinket. Fordi du er en kandidat til å delta i en internasjonal programmeringskonkurranse i Iran, ber Anna og Bruno deg om å skrive et program som sender resultatene av undersøkelsen deres.

Oppgave

Skriv to programmer som gjennomfører kommunikasjonen mellom Anna og Bruno.

• Gitt lengden på sekvensen $N$, heltallet som skal sendes $X$, antallet ødelagte plasser $K$ og posisjonene til de ødelagte plassene $P$, setter det første programmet sekvensen $S$ som sendes av Anna.
• Gitt sekvensen $A$ som mottas av Bruno, gjenoppretter det andre programmet heltallet $X$.

På en plass der kommunikasjonsenheten fungerer, har sekvensen $S$ og sekvensen $A$ samme verdi. På en ødelagt plass har sekvensen $A$ alltid verdien $0$ uavhengig av verdiene i sekvensen $S$.

Implementeringsdetaljer

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

Den første filen er enten Anna.c eller Anna.cpp. Denne filen setter en sekvens som sendes av Anna, og implementerer følgende funksjon. Programmet skal inkludere Annalib.h.

• void Anna( int N, long long X, int K, int P[] )

  For hvert testtilfelle kalles denne funksjonen $Q=1\,000$ ganger.

  • Parameteren N er lengden på sekvensen som skal sendes.
  • Parameteren X er heltallet som skal sendes.
  • Parameteren K er antallet ødelagte plasser.
  • Parameteren P[] er en sekvens med lengde $K$, som beskriver posisjonene til de ødelagte plassene.

  I funksjonen Anna må følgende funksjon kalles.

  • void Set( int pos, int bit )

    Denne funksjonen setter en bit i sekvensen $S$ som skal sendes av kommunikasjonsenheten.

    • Parameteren pos er posisjonen til plassen som skal settes. pos må være et heltall mellom $0$ og $N-1$, inkludert. Merk at posisjonene telles fra $0$. Hvis den kalles med en parameter utenfor dette området, regnes programmet ditt som Wrong Answer[1]. Det er ikke tillatt å kalle denne funksjonen mer enn én gang med samme parameter pos. Hvis den kalles mer enn én gang med samme parameter, regnes programmet ditt som Wrong Answer[2].
    • Parameteren bit er verdien som settes på den pos-te posisjonen i sekvensen. Verdien til bit må være enten $0$ eller $1$. Hvis den kalles med andre parametere, regnes programmet ditt som Wrong Answer[3].

  Funksjonen Set må kalles nøyaktig $N$ ganger i funksjonen Anna. Når funksjonen Anna avsluttes, hvis antallet ganger funksjonen Set er kalt er forskjellig fra $N$, regnes programmet ditt som Wrong Answer[4].

  Programmet ditt avsluttes hvis funksjonskallet fra Anna regnes som ugyldig.

Den andre filen er enten Bruno.c eller Bruno.cpp. Denne filen gjenoppretter heltallet som uttrykker resultatene av undersøkelsen, og implementerer følgende funksjon. Programmet skal inkludere Brunolib.h.

• long long Bruno( int N, int A[] )

  For hvert testtilfelle kalles denne funksjonen $Q=1\,000$ ganger.

  • Parameteren N er lengden på sekvensen som mottas av Bruno.
  • Parameteren A er en heltallssekvens med lengde $N$. Det er sekvensen som mottas av Bruno.
  • Funksjonen Bruno må gjenopprette verdien av $X$ og returnere den.

Evalueringsprosedyre

Evalueringen gjøres på følgende måte. Hvis programmet ditt regnes som Wrong Answer, avsluttes det umiddelbart.

1. Sett cnt = 0.
2. Kall funksjonen Anna én gang.
3. La $S$ være sekvensen satt av funksjonen Anna. I sekvensen $S$, sett verdien $0$ på posisjonene i $P$, og få sekvensen $A$. Kall funksjonen Bruno én gang med parameteren $A$.
4. Sett cnt = cnt +1. Hvis $\mathrm{cnt}<Q$, gå til (2). Hvis $\mathrm{cnt}=Q$, gå til (5).
5. Programmet ditt vil bli gitt poeng.

Viktige merknader

• Kjøretid og minnebruk beregnes for (1), (2), (3), (4) i Evalueringsprosedyren.
• Programmet ditt må ikke bli regnet som Wrong Answer i funksjonskallet til Anna i (2) eller Bruno i (3). Programmet ditt må kjøre uten kjøretidsfeil (runtime error).
• Programmet ditt kan implementere andre funksjoner for intern bruk, eller bruke globale variabler. Innsendte programmer vil bli kompilert sammen med graderen og bli én enkelt kjørbar fil. Alle globale variabler og interne funksjoner bør deklareres static for å unngå konflikter med andre filer. Siden programmene til Anna og Bruno vil bli kjørt som 2 adskilte prosesser når de evalueres, kan de ikke dele globale variabler.
• I prosessen kalles hver av funksjonene Anna og Bruno $Q=1\,000$ ganger. Variablene som brukes av programmene dine bør initialiseres på riktig måte.
• Programmet ditt skal ikke bruke standard inndata og standard utdata. Programmet ditt skal ikke kommunisere med andre filer på noen måte.

Kompilering og testkjøring

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

En eksempelgrader består av én kildefil som enten er grader.c eller grader.cpp. Hvis programmene dine for eksempel er Anna.c og Bruno.c, eller Anna.cpp og Bruno.cpp, kjører du følgende kommandoer for å kompilere programmene dine.

• C

  gcc -std=c11 -O2 -o grader grader.c Anna.c Bruno.c -lm

• C++

  g++ -std=c++14 -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 én enkelt prosess, som leser inndata fra standard inndata og skriver resultatene til standard utdata.

Inndata for eksempelgraderen

Eksempelgraderen leser følgende data fra standard inndata.

• Den første linjen inneholder et heltall $Q$.
• Deretter gis informasjon om $Q$ spørringer.

• Informasjonen om hver spørring består av to linjer som følger.

  • Den første linjen inneholder tre mellomromseparerte heltall $N$, $X$, $K$. Dette betyr at lengden på sekvensen som skal sendes er $N$, heltallet som skal sendes av Anna er $X$, og det er $K$ ødelagte plasser.
  • Den andre linjen inneholder $K$ mellomromseparerte heltall $P_0,P_1,\cdots,P_{K-1}$. Dette betyr at for hver $i$ ($0\le i\le K-1$) er den $P_i$-te plassen i sekvensen ødelagt.

Utdata fra eksempelgraderen

Når programmet avsluttes uten feil, skriver eksempelgraderen følgende informasjon til standard utdata. (Anførselstegnene skrives ikke faktisk.)

• Hvis programmet ditt regnes som Wrong Answer, skriver eksempelgraderen typen på følgende form “Wrong Answer [1],” og programmet ditt avsluttes.
• Hvis ingen funksjonskall til Anna regnes som Wrong Answer, skriver eksempelgraderen “Accepted” og verdien av $L^*$. For verdien av $L^*$, se Deloppgaver.

Hvis programmet ditt regnes som flere typer Wrong Answer, rapporterer eksempelgraderen bare én av dem.

Begrensninger

Alle inndata tilfredsstiller følgende betingelser.

• $Q=1000$.
• $N=150$.
• $0\le X\le 1\,000\,000\,000\,000\,000\,000$.
• $1\le K\le 40$.
• $0\le P_i\le N-1$ ($0\le i\le K-1$).
• $P_i<P_{i+1}$ ($0\le i\le K-2$).

Deloppgaver

• La $L^*$ være minimum av følgende verdi for alle testtilfeller i denne oppgaven.

  • Det største heltallet $L\le40$ slik at Bruno for hver spørring med $K\le L$ svarer med riktig verdi av $X$.

• Poengsummen for denne oppgaven beregnes på følgende måte:

  • Hvis $L^*=0$, er poengsummen 0 poeng.
  • Hvis $1\le L^*\le14$, er poengsummen 8 poeng.
  • Hvis $15\le L^*\le37$, er poengsummen $(L^*-15)\times2+41$ poeng.
  • Hvis $38\le L^*\le40$, er poengsummen $(L^*-38)\times5+90$ poeng.

Eksempler

Her er et eksempel på inndata for graderen og tilhørende funksjonskall. Merk at følgende eksempel ikke tilfredsstiller begrensningene i denne oppgaven fordi $Q=2$, $N=3$.

Inndata 1

2
3 14 1
2
3 9 2
0 1

Eksempelkall

Her er parameterne for Anna(...), Bruno(...), Anna(...), Bruno(...) som følger.