Anna und Bruno sind Archäologen. Sie untersuchen Ruinen im Iran.

Ihre Aufgaben sind folgendermaßen verteilt: Anna besucht die Ruinen und entdeckt Artefakte, während Bruno die Ergebnisse im Basislager analysiert.

Ihre Untersuchung ist für $Q\,(=1\,000)$ Tage geplant. Jeden Tag übermittelt Anna die Ergebnisse mit einem Kommunikationsgerät an Bruno. Das Ergebnis eines Tages wird durch eine ganze Zahl $X$ ausgedrückt.

Anna kann das Kommunikationsgerät nur einmal pro Tag benutzen. Es kann eine Folge der Länge $N\,(=150)$ aus Nullen und Einsen senden.

Das Gerät ist jedoch defekt. In der Folge der Länge $N$ gibt es mehrere defekte Positionen. An einer defekten Position wird unabhängig vom tatsächlich eingestellten Wert immer der Wert $0$ gesendet. Wenn Anna eine Folge sendet, kann sie die defekten Positionen sehen. Bruno kennt sie jedoch nicht. Die defekten Positionen und ihre Anzahl können sich täglich ändern.

Es besteht die Gefahr, dass sich die Untersuchung verzögert. Da du ein Kandidat für die Teilnahme an einem internationalen Programmierwettbewerb im Iran bist, bitten Anna und Bruno dich, ein Programm zur Übermittlung ihrer Untersuchungsergebnisse zu schreiben.

Aufgabe

Schreibe zwei Programme, die die Kommunikation zwischen Anna und Bruno ermöglichen.

• Das erste Programm erhält die Folgenlänge $N$, die zu sendende ganze Zahl $X$, die Anzahl defekter Positionen $K$ und deren Positionen $P$ und legt die von Anna gesendete Folge $S$ fest.
• Das zweite Programm erhält die von Bruno empfangene Folge $A$ und stellt die ganze Zahl $X$ wieder her.

An einer funktionierenden Position des Kommunikationsgeräts haben $S$ und $A$ denselben Wert. An einer defekten Position hat $A$ unabhängig vom Wert in $S$ immer den Wert $0$.

Implementierungsdetails

Du musst zwei Dateien in derselben Programmiersprache einreichen.

Die erste Datei heißt entweder Anna.c oder Anna.cpp. Sie legt die von Anna gesendete Folge fest und implementiert die folgende Funktion. Das Programm muss Annalib.h einbinden.

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

Für jeden Testfall wird diese Funktion $Q=1\,000$ Mal aufgerufen.

• Der Parameter N ist die Länge der zu sendenden Folge.
• Der Parameter X ist die zu sendende ganze Zahl.
• Der Parameter K ist die Anzahl defekter Positionen.
• Der Parameter P[] ist eine Folge der Länge $K$, die die defekten Positionen beschreibt.

In der Funktion Anna muss die folgende Funktion aufgerufen werden.

• void Set( int pos, int bit )

Diese Funktion setzt ein Bit in der vom Kommunikationsgerät zu sendenden Folge $S$.

• Der Parameter pos ist die zu setzende Position. pos muss eine ganze Zahl zwischen $0$ und $N-1$ einschließlich sein. Beachte, dass die Positionen ab $0$ gezählt werden. Bei einem Aufruf mit einem Parameter außerhalb dieses Bereichs wird dein Programm als Wrong Answer[1] bewertet. Diese Funktion darf nicht mehrmals mit demselben Parameter pos aufgerufen werden. Andernfalls wird dein Programm als Wrong Answer[2] bewertet.
• Der Parameter bit ist der Wert, der an Position pos der Folge gesetzt wird. Der Wert von bit muss entweder $0$ oder $1$ sein. Bei anderen Werten wird dein Programm als Wrong Answer[3] bewertet.

Die Funktion Set muss innerhalb der Funktion Anna genau $N$ Mal aufgerufen werden. Ist beim Ende von Anna die Anzahl der Aufrufe von Set ungleich $N$, wird dein Programm als Wrong Answer[4] bewertet.

Dein Programm wird beendet, wenn ein Funktionsaufruf durch Anna als ungültig bewertet wird.

Die zweite Datei heißt entweder Bruno.c oder Bruno.cpp. Sie stellt die ganze Zahl wieder her, die die Untersuchungsergebnisse ausdrückt, und implementiert die folgende Funktion. Das Programm muss Brunolib.h einbinden.

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

Für jeden Testfall wird diese Funktion $Q=1\,000$ Mal aufgerufen.

• Der Parameter N ist die Länge der von Bruno empfangenen Folge.
• Der Parameter A ist eine ganzzahlige Folge der Länge $N$. Dies ist die von Bruno empfangene Folge.
• Die Funktion Bruno muss den Wert von $X$ wiederherstellen und zurückgeben.

Bewertungsablauf

Die Bewertung erfolgt folgendermaßen. Wird dein Programm als falsche Antwort bewertet, wird es sofort beendet.

1. Setze $\mathrm{cnt}=0$.
2. Rufe die Funktion Anna einmal auf.
3. Sei $S$ die von Anna festgelegte Folge. Setze in $S$ die Werte an den Positionen aus $P$ auf $0$, um die Folge $A$ zu erhalten. Rufe die Funktion Bruno einmal mit dem Parameter $A$ auf.
4. Setze $\mathrm{cnt}=\mathrm{cnt}+1$. Falls $\mathrm{cnt}<Q$, fahre mit (2) fort. Falls $\mathrm{cnt}=Q$, fahre mit (5) fort.
5. Dein Programm erhält seine Punktzahl.

Wichtige Hinweise

• Laufzeit und Speicherverbrauch werden für die Schritte (1), (2), (3) und (4) des Bewertungsablaufs berechnet.
• Dein Programm darf weder beim Aufruf von Anna in (2) noch beim Aufruf von Bruno in (3) als falsche Antwort bewertet werden. Es muss ohne Laufzeitfehler ausgeführt werden.
• Dein Programm kann weitere Funktionen für den internen Gebrauch implementieren oder globale Variablen verwenden. Die eingereichten Programme werden zusammen mit dem Bewertungsprogramm kompiliert und bilden eine einzige ausführbare Datei. Alle globalen Variablen und internen Funktionen sollten als static deklariert werden, um Konflikte mit anderen Dateien zu vermeiden. Da die Programme von Anna und Bruno bei der Bewertung als zwei getrennte Prozesse ausgeführt werden, können sie keine globalen Variablen gemeinsam nutzen.
• Im Prozess wird jede der Funktionen Anna und Bruno $Q=1\,000$ Mal aufgerufen. Die von deinen Programmen verwendeten Variablen sollten angemessen initialisiert werden.
• Dein Programm darf weder die Standardeingabe noch die Standardausgabe verwenden. Es darf auf keine Weise mit anderen Dateien kommunizieren.

Kompilieren und Testen

Du kannst von der Wettbewerbswebseite ein Archiv herunterladen, das ein Beispielbewertungsprogramm zum Testen deines Programms enthält. Das Archiv enthält auch eine Beispielquelldatei für dein Programm.

Das Beispielbewertungsprogramm besteht aus einer Quelldatei namens grader.c oder grader.cpp. Sind deine Programme beispielsweise Anna.c und Bruno.c beziehungsweise Anna.cpp und Bruno.cpp, kompilierst du sie mit den folgenden Befehlen.

• 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

Bei erfolgreicher Kompilierung wird die ausführbare Datei grader erzeugt.

Beachte, dass das tatsächliche Bewertungsprogramm vom Beispielbewertungsprogramm abweicht. Das Beispielbewertungsprogramm wird als einzelner Prozess ausgeführt, liest Eingabedaten von der Standardeingabe und schreibt die Ergebnisse auf die Standardausgabe.

Eingabe für das Beispielbewertungsprogramm

Das Beispielbewertungsprogramm liest die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält eine ganze Zahl $Q$.
• Danach folgen Informationen zu $Q$ Anfragen.
• Die Informationen zu jeder Anfrage bestehen aus den folgenden zwei Zeilen.

Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N,X,K$. Die Länge der zu sendenden Folge ist $N$, die von Anna zu sendende ganze Zahl ist $X$, und es gibt $K$ defekte Positionen.

Die zweite Zeile enthält $K$ durch Leerzeichen getrennte ganze Zahlen $P_0,P_1,\ldots,P_{K-1}$. Für jedes $i$ ($0 \le i \le K-1$) ist die Position $P_i$ der Folge defekt.

Ausgabe des Beispielbewertungsprogramms

Wenn das Programm erfolgreich endet, schreibt das Beispielbewertungsprogramm die folgenden Informationen auf die Standardausgabe. (Die Anführungszeichen werden tatsächlich nicht ausgegeben.)

• Wird dein Programm als falsche Antwort bewertet, gibt das Beispielbewertungsprogramm den Fehlertyp in der Form „Wrong Answer [1]“ aus, und dein Programm wird beendet.
• Wird kein Aufruf von Anna als falsche Antwort bewertet, gibt das Beispielbewertungsprogramm „Accepted“ und den Wert von $L^*$ aus. Siehe den Abschnitt „Teilaufgaben“ für den Wert von $L^*$.

Wird dein Programm mehreren Arten falscher Antworten zugeordnet, meldet das Beispielbewertungsprogramm nur eine davon.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

• Sei $L^*$ das Minimum des folgenden Wertes über alle Testfälle dieser Aufgabe:

Die größte ganze Zahl $L \le 40$, sodass Bruno für jede Anfrage mit $K \le L$ den richtigen Wert von $X$ zurückgibt.

• Die Punktzahl dieser Aufgabe wird folgendermaßen berechnet:

Falls $L^*=0$, beträgt die Punktzahl $0$.

Falls $1 \le L^* \le 14$, beträgt die Punktzahl $8$.

Falls $15 \le L^* \le 37$, beträgt die Punktzahl $(L^*-15)\times 2+41$.

Falls $38 \le L^* \le 40$, beträgt die Punktzahl $(L^*-38)\times 5+90$.

Beispiele

Hier folgen eine Beispieleingabe für das Bewertungsprogramm und die entsprechenden Funktionsaufrufe. Beachte, dass dieses Beispiel die Beschränkungen der Aufgabe nicht erfüllt, da $Q=2$ und $N=3$ gelten.

Eingabe 1

2
3 14 1
2
3 9 2
0 1

Beispielaufrufe

Hier sind die Parameter für Anna(...), Bruno(...), Anna(...), Bruno(...) wie folgt.