Anna och Bruno är arkeologer. De undersöker ruiner i Iran.

Deras uppgifter är följande: Anna besöker ruiner och upptäcker artefakter, och Bruno analyserar resultaten i baslägret.

Deras undersökning är planerad att pågå i $Q(=1\,000)$ dagar. Varje dag skickar Anna resultaten till Bruno med hjälp av en kommunikationsapparat. Resultatet för varje dag uttrycks som ett heltal $X$.

Anna kan bara använda kommunikationsapparaten en gång om dagen. Den kan skicka en sekvens av längd $N(=150)$ som består av $0$ eller $1$.

Den var dock trasig. Det finns flera trasiga platser i sekvensen av längd $N$. På en trasig plats skickar den alltid värdet $0$ oavsett det faktiskt inställda värdet. När Anna skickar en sekvens kan hon se positionerna för de trasiga platserna. Men Bruno känner inte till dem. Positionerna för de trasiga platserna och antalet trasiga platser kan ändras varje dag.

Det finns en risk att deras undersökning blir försenad. Eftersom du är en kandidat till att delta i en internationell programmeringstävling i Iran ber Anna och Bruno dig att skriva ett program som skickar resultaten av deras undersökning.

Uppgift

Skriv två program som åstadkommer kommunikationen mellan Anna och Bruno.

• Givet sekvensens längd $N$, heltalet som ska skickas $X$, antalet trasiga platser $K$ och positionerna för de trasiga platserna $P$, ställer det första programmet in sekvensen $S$ som skickas av Anna.
• Givet sekvensen $A$ som tas emot av Bruno, återskapar det andra programmet heltalet $X$.

På en plats där kommunikationsapparaten fungerar har sekvensen $S$ och sekvensen $A$ samma värde. På en trasig plats har sekvensen $A$ alltid värdet $0$ oavsett värdena i sekvensen $S$.

Implementeringsdetaljer

Du måste skicka in två filer skrivna i samma programmeringsspråk.

Den första filen är antingen Anna.c eller Anna.cpp. Denna fil ställer in en sekvens som skickas av Anna och implementerar följande funktion. Programmet ska inkludera Annalib.h.

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

  För varje testfall anropas denna funktion $Q=1\,000$ gånger.

  • Parametern N är längden på sekvensen som ska skickas.
  • Parametern X är heltalet som ska skickas.
  • Parametern K är antalet trasiga platser.
  • Parametern P[] är en sekvens av längd $K$ som beskriver positionerna för de trasiga platserna.

  I funktionen Anna måste följande funktion anropas.

  • void Set( int pos, int bit )

    Denna funktion ställer in en bit i sekvensen $S$ som ska skickas av kommunikationsapparaten.

    • Parametern pos är positionen för platsen som ska ställas in. pos måste vara ett heltal mellan $0$ och $N-1$, inklusive. Observera att positionerna räknas från $0$. Om den anropas med en parameter utanför detta intervall betraktas ditt program som Wrong Answer[1]. Det är inte tillåtet att anropa denna funktion mer än en gång med samma parameter pos. Om den anropas mer än en gång med samma parameter betraktas ditt program som Wrong Answer[2].
    • Parametern bit är värdet som ställs in på den pos-te positionen i sekvensen. Värdet på bit måste vara antingen $0$ eller $1$. Om den anropas med andra parametrar betraktas ditt program som Wrong Answer[3].

  Funktionen Set måste anropas exakt $N$ gånger i funktionen Anna. När funktionen Anna avslutas, om antalet gånger funktionen Set anropats skiljer sig från $N$, betraktas ditt program som Wrong Answer[4].

  Ditt program avslutas om funktionsanropet av Anna betraktas som ogiltigt.

Den andra filen är antingen Bruno.c eller Bruno.cpp. Denna fil återskapar heltalet som uttrycker undersökningsresultatet och implementerar följande funktion. Programmet ska inkludera Brunolib.h.

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

  För varje testfall anropas denna funktion $Q=1\,000$ gånger.

  • Parametern N är längden på sekvensen som tas emot av Bruno.
  • Parametern A är en heltalssekvens av längd $N$. Det är sekvensen som tas emot av Bruno.
  • Funktionen Bruno måste återskapa värdet på $X$ och returnera det.

Bedömningsprocedur

Bedömningen görs på följande sätt. Om ditt program betraktas som Wrong Answer avslutas det omedelbart.

1. Sätt cnt = 0.
2. Anropa funktionen Anna en gång.
3. Låt $S$ vara sekvensen som ställts in av funktionen Anna. I sekvensen $S$, sätt värdet $0$ på positionerna i $P$ och erhåll sekvensen $A$. Anropa funktionen Bruno en gång med parametern $A$.
4. Sätt cnt = cnt +1. Om $\mathrm{cnt}<Q$, gå till (2). Om $\mathrm{cnt}=Q$, gå till (5).
5. Ditt program poängsätts.

Viktiga meddelanden

• Körtid och minnesanvändning beräknas för (1), (2), (3), (4) i Bedömningsproceduren.
• Ditt program får inte betraktas som Wrong Answer i funktionsanropet till Anna i (2) eller Bruno i (3). Ditt program måste köras utan körfel (runtime error).
• Ditt program kan implementera andra funktioner för internt bruk eller använda globala variabler. Inskickade program kommer att kompileras med gradern och bli en enda körbar fil. Alla globala variabler och interna funktioner bör deklareras static för att undvika konflikter med andra filer. Eftersom Annas och Brunos program kommer att köras som 2 separata processer när de bedöms kan de inte dela globala variabler.
• Under processen anropas var och en av funktionerna Anna och Bruno $Q=1\,000$ gånger. Variablerna som används av dina program bör initieras på lämpligt sätt.
• Ditt program får inte använda standard inmatning och standard utmatning. Ditt program får inte kommunicera med andra filer på något sätt.

Kompilering och testkörning

Du kan ladda ner en arkivfil från tävlingens webbsida som innehåller en exempelgrader för att testa ditt program. Arkivfilen innehåller också en exempelkällfil för ditt program.

En exempelgrader består av en källfil som antingen är grader.c eller grader.cpp. Om dina program till exempel är Anna.c och Bruno.c, eller Anna.cpp och Bruno.cpp, kör du följande kommandon för att kompilera dina program.

• 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 lyckas genereras den körbara filen grader.

Observera att den faktiska gradern skiljer sig från exempelgradern. Exempelgradern kommer att köras som en enda process, som läser indata från standard inmatning och skriver resultaten till standard utmatning.

Indata för exempelgradern

Exempelgradern läser följande data från standard inmatning.

• Den första raden innehåller ett heltal $Q$.
• Därefter ges information om $Q$ frågor.

• Informationen för varje fråga består av två rader enligt följande.

  • Den första raden innehåller tre blankstegsseparerade heltal $N$, $X$, $K$. Detta betyder att längden på sekvensen som ska skickas är $N$, heltalet som ska skickas av Anna är $X$, och det finns $K$ trasiga platser.
  • Den andra raden innehåller $K$ blankstegsseparerade heltal $P_0,P_1,\cdots,P_{K-1}$. Detta betyder att för varje $i$ ($0\le i\le K-1$) är den $P_i$-te platsen i sekvensen trasig.

Utdata från exempelgradern

När programmet avslutas framgångsrikt skriver exempelgradern följande information till standard utmatning. (Citattecknen skrivs inte ut i verkligheten.)

• Om ditt program betraktas som Wrong Answer skriver exempelgradern dess typ i följande form “Wrong Answer [1],” och ditt program avslutas.
• Om inget funktionsanrop till Anna betraktas som Wrong Answer skriver exempelgradern “Accepted” och värdet på $L^*$. För värdet på $L^*$, se Deluppgifter.

Om ditt program betraktas som flera typer av Wrong Answer rapporterar exempelgradern bara en av dem.

Begränsningar

All indata uppfyller följande villkor.

• $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$).

Deluppgifter

• Låt $L^*$ vara minimum av följande värde för alla testfall i denna uppgift.

  • Det största heltalet $L\le40$ sådant att Bruno för varje fråga med $K\le L$ svarar med det korrekta värdet på $X$.

• Poängen för denna uppgift beräknas på följande sätt:

  • Om $L^*=0$ är poängen 0 poäng.
  • Om $1\le L^*\le14$ är poängen 8 poäng.
  • Om $15\le L^*\le37$ är poängen $(L^*-15)\times2+41$ poäng.
  • Om $38\le L^*\le40$ är poängen $(L^*-38)\times5+90$ poäng.

Exempel

Här är ett exempel på indata för gradern och motsvarande funktionsanrop. Observera att följande exempel inte uppfyller begränsningarna för denna uppgift eftersom $Q=2$, $N=3$.

Indata 1

2
3 14 1
2
3 9 2
0 1

Exempelanrop

Här är parametrarna för Anna(...), Bruno(...), Anna(...), Bruno(...) följande.