Anna e Bruno sono archeologi. Stanno esplorando delle rovine in Iran.

I loro compiti sono i seguenti: Anna visita le rovine e scopre i reperti, mentre Bruno analizza i risultati nel campo base.

La loro indagine è programmata per $Q(=1\,000)$ giorni. Ogni giorno, Anna invia i risultati a Bruno utilizzando un dispositivo di comunicazione. I risultati di ciascun giorno sono espressi come un intero $X$.

Anna può utilizzare il dispositivo di comunicazione solo una volta al giorno. Esso può inviare una sequenza di lunghezza $N(=150)$ composta da $0$ o $1$.

Tuttavia, il dispositivo si è guastato. Ci sono diverse posizioni guaste nella sequenza di lunghezza $N$. In una posizione guasta, il dispositivo invia sempre il valore $0$ indipendentemente dal valore effettivamente impostato. Quando Anna invia una sequenza, può vedere le posizioni dei punti guasti. Ma Bruno non le conosce. Le posizioni dei punti guasti e il loro numero possono cambiare ogni giorno.

C'è il pericolo che la loro indagine subisca ritardi. Poiché sei un candidato a partecipare a una gara internazionale di programmazione in Iran, Anna e Bruno ti chiedono di scrivere un programma che invii i risultati della loro indagine.

Compito

Scrivi due programmi che realizzino la comunicazione tra Anna e Bruno.

• Data la lunghezza della sequenza $N$, l'intero da inviare $X$, il numero di posizioni guaste $K$ e le posizioni dei punti guasti $P$, il primo programma imposta la sequenza $S$ inviata da Anna.
• Data la sequenza $A$ ricevuta da Bruno, il secondo programma ricostruisce l'intero $X$.

In una posizione in cui il dispositivo di comunicazione funziona, la sequenza $S$ e la sequenza $A$ hanno lo stesso valore. In una posizione guasta, la sequenza $A$ ha sempre il valore $0$ indipendentemente dai valori della sequenza $S$.

Dettagli di implementazione

Devi inviare due file scritti nello stesso linguaggio di programmazione.

Il primo file è Anna.c oppure Anna.cpp. Questo file imposta una sequenza inviata da Anna e implementa la seguente funzione. Il programma deve includere Annalib.h.

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

  Per ogni caso di test, questa funzione viene chiamata $Q=1\,000$ volte.

  • Il parametro N è la lunghezza della sequenza da inviare.
  • Il parametro X è l'intero da inviare.
  • Il parametro K è il numero di posizioni guaste.
  • Il parametro P[] è una sequenza di lunghezza $K$, che descrive le posizioni dei punti guasti.

  Nella funzione Anna, deve essere chiamata la seguente funzione.

  • void Set( int pos, int bit )

    Questa funzione imposta un bit nella sequenza $S$ che verrà inviata dal dispositivo di comunicazione.

    • Il parametro pos è l'indice della posizione da impostare. pos deve essere un intero compreso tra $0$ e $N-1$, inclusi. Nota che le posizioni sono numerate a partire da $0$. Se viene chiamata con un parametro fuori da questo intervallo, il tuo programma viene considerato Wrong Answer[1]. Non è consentito chiamare questa funzione più di una volta con lo stesso parametro pos. Se viene chiamata più di una volta con lo stesso parametro, il tuo programma viene considerato Wrong Answer[2].
    • Il parametro bit è il valore impostato nella posizione pos-esima della sequenza. Il valore di bit deve essere $0$ oppure $1$. Se viene chiamata con altri parametri, il tuo programma viene considerato Wrong Answer[3].

  La funzione Set deve essere chiamata esattamente $N$ volte nella funzione Anna. Quando la funzione Anna termina, se il numero di volte in cui è stata chiamata la funzione Set è diverso da $N$, il tuo programma viene considerato Wrong Answer[4].

  Il tuo programma viene terminato se la chiamata di funzione da parte di Anna è considerata non valida.

Il secondo file è Bruno.c oppure Bruno.cpp. Questo file ricostruisce l'intero che esprime i risultati dell'indagine e implementa la seguente funzione. Il programma deve includere Brunolib.h.

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

  Per ogni caso di test, questa funzione viene chiamata $Q=1\,000$ volte.

  • Il parametro N è la lunghezza della sequenza ricevuta da Bruno.
  • Il parametro A è una sequenza di interi di lunghezza $N$. È la sequenza ricevuta da Bruno.
  • La funzione Bruno deve ricostruire il valore di $X$ e restituirlo.

Procedura di valutazione

La valutazione viene effettuata nel modo seguente. Se il tuo programma viene considerato Wrong Answer, viene terminato immediatamente.

1. Imposta cnt = 0.
2. Chiama la funzione Anna una volta.
3. Sia $S$ la sequenza impostata dalla funzione Anna. Nella sequenza $S$, imposta il valore $0$ nelle posizioni contenute in $P$ e ottieni la sequenza $A$. Chiama la funzione Bruno una volta con il parametro $A$.
4. Imposta cnt = cnt +1. Se $\mathrm{cnt}<Q$, vai al punto (2). Se $\mathrm{cnt}=Q$, vai al punto (5).
5. Il tuo programma verrà valutato e riceverà un punteggio.

Avvisi importanti

• Il tempo di esecuzione e l'utilizzo della memoria vengono calcolati per i passi (1), (2), (3), (4) della Procedura di valutazione.
• Il tuo programma non deve essere considerato Wrong Answer nella chiamata alla funzione Anna in (2) o Bruno in (3). Il tuo programma deve essere eseguito senza errori di runtime.
• Il tuo programma può implementare altre funzioni per uso interno o utilizzare variabili globali. I programmi inviati verranno compilati insieme al grader e diventeranno un singolo file eseguibile. Tutte le variabili globali e le funzioni interne devono essere dichiarate static per evitare conflitti con altri file. Poiché i programmi di Anna e Bruno verranno eseguiti come 2 processi distinti durante la valutazione, non possono condividere variabili globali.
• Nel processo, ciascuna delle funzioni Anna e Bruno viene chiamata $Q=1\,000$ volte. Le variabili utilizzate dai tuoi programmi devono essere inizializzate appropriatamente.
• Il tuo programma non deve utilizzare lo standard input e lo standard output. Il tuo programma non deve comunicare con altri file con alcun metodo.

Compilazione ed esecuzione di prova

Puoi scaricare dalla pagina web della gara un file archivio che contiene un grader di esempio per testare il tuo programma. Il file archivio contiene anche un file sorgente di esempio del tuo programma.

Un grader di esempio consiste in un file sorgente che è grader.c oppure grader.cpp. Ad esempio, se i tuoi programmi sono Anna.c e Bruno.c, oppure Anna.cpp e Bruno.cpp, esegui i seguenti comandi per compilare i tuoi programmi.

• 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

Quando la compilazione ha successo, viene generato il file eseguibile grader.

Nota che il grader effettivo è diverso dal grader di esempio. Il grader di esempio verrà eseguito come un singolo processo, che leggerà i dati di input dallo standard input e scriverà i risultati sullo standard output.

Input per il grader di esempio

Il grader di esempio legge i seguenti dati dallo standard input.

• La prima riga contiene un intero $Q$.
• Successivamente vengono fornite le informazioni su $Q$ query.

• Le informazioni di ciascuna query consistono in due righe come segue.

  • La prima riga contiene tre interi separati da spazi $N$, $X$, $K$. Ciò significa che la lunghezza della sequenza da inviare è $N$, l'intero da inviare da parte di Anna è $X$ e ci sono $K$ posizioni guaste.
  • La seconda riga contiene $K$ interi separati da spazi $P_0,P_1,\cdots,P_{K-1}$. Ciò significa che, per ogni $i$ ($0\le i\le K-1$), la $P_i$-esima posizione nella sequenza è guasta.

Output del grader di esempio

Quando il programma termina correttamente, il grader di esempio scrive le seguenti informazioni sullo standard output. (Le virgolette non vengono scritte effettivamente.)

• Se il tuo programma viene considerato Wrong Answer, il grader di esempio ne scrive il tipo nella forma seguente “Wrong Answer [1],” e il tuo programma viene terminato.
• Se nessuna chiamata di funzione ad Anna viene considerata Wrong Answer, il grader di esempio scrive “Accepted” e il valore di $L^*$. Per il valore di $L^*$, vedi Subtask.

Se il tuo programma incorre in più tipi di Wrong Answer, il grader di esempio ne segnala solo uno.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

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

Subtask

• Sia $L^*$ il minimo del seguente valore su tutti i casi di test di questo problema.

  • Il massimo intero $L\le40$ tale che, per ogni query con $K\le L$, Bruno risponde con il valore corretto di $X$.

• Il punteggio di questo problema viene calcolato nel modo seguente:

  • Se $L^*=0$, il punteggio è 0 punti.
  • Se $1\le L^*\le14$, il punteggio è 8 punti.
  • Se $15\le L^*\le37$, il punteggio è $(L^*-15)\times2+41$ punti.
  • Se $38\le L^*\le40$, il punteggio è $(L^*-38)\times5+90$ punti.

Esempi

Ecco un input di esempio per il grader e le corrispondenti chiamate di funzione. Nota che l'esempio seguente non soddisfa i vincoli di questo problema perché $Q=2$, $N=3$.

Input 1

2
3 14 1
2
3 9 2
0 1

Chiamate di esempio

Qui i parametri per Anna(...), Bruno(...), Anna(...), Bruno(...) sono i seguenti.