Anna et Bruno sont archéologues. Ils étudient des ruines en Iran.

Leurs tâches sont les suivantes : Anna visite les ruines et découvre des objets anciens, tandis que Bruno analyse les résultats au camp de base.

Leur étude est prévue sur $Q\ (=1\,000)$ jours. Chaque jour, Anna transmet les résultats à Bruno à l'aide d'un appareil de communication. Les résultats d'une journée sont représentés par un entier $X$.

Anna ne peut utiliser l'appareil de communication qu'une fois par jour. Celui-ci peut envoyer une suite de longueur $N\ (=150)$ composée de $0$ et de $1$.

Cependant, l'appareil est en panne. Plusieurs positions de la suite de longueur $N$ sont défectueuses. À une position défectueuse, il transmet toujours la valeur $0$, quelle que soit la valeur définie. Lorsqu'Anna envoie une suite, elle peut voir les positions défectueuses. Bruno, en revanche, ne les connaît pas. Les positions défectueuses et leur nombre peuvent changer chaque jour.

Leur étude risque de prendre du retard. Comme vous êtes candidat à la participation à un concours international de programmation en Iran, Anna et Bruno vous demandent d'écrire un programme pour transmettre les résultats de leur étude.

Tâche

Écrivez deux programmes permettant à Anna et Bruno de communiquer.

• Étant donnés la longueur $N$ de la suite, l'entier $X$ à transmettre, le nombre $K$ de positions défectueuses et leurs positions $P$, le premier programme définit la suite $S$ envoyée par Anna.
• Étant donnée la suite $A$ reçue par Bruno, le second programme retrouve l'entier $X$.

À une position où l'appareil fonctionne, les suites $S$ et $A$ ont la même valeur. À une position défectueuse, la suite $A$ vaut toujours $0$, quelle que soit la valeur de la suite $S$.

Détails d'implémentation

Vous devez soumettre deux fichiers écrits dans le même langage de programmation.

Le premier fichier est Anna.c ou Anna.cpp. Il définit la suite envoyée par Anna et implémente la fonction suivante. Le programme doit inclure Annalib.h.

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

Pour chaque cas de test, cette fonction est appelée $Q=1\,000$ fois.

• Le paramètre N est la longueur de la suite à transmettre.
• Le paramètre X est l'entier à transmettre.
• Le paramètre K est le nombre de positions défectueuses.
• Le paramètre P[] est une suite de longueur $K$ décrivant les positions défectueuses.

Dans la fonction Anna, la fonction suivante doit être appelée.

• void Set( int pos, int bit )

Cette fonction définit un bit de la suite $S$ qui sera envoyée par l'appareil de communication.

• Le paramètre pos est la position à définir. pos doit être un entier compris entre $0$ et $N-1$, bornes incluses. Remarquez que les positions sont numérotées à partir de $0$. Si cette fonction est appelée avec un paramètre hors de cet intervalle, votre programme est considéré comme donnant une réponse incorrecte (Wrong Answer[1]). Il est interdit d'appeler cette fonction plusieurs fois avec la même valeur du paramètre pos. Si cela se produit, votre programme est considéré comme donnant une réponse incorrecte (Wrong Answer[2]).
• Le paramètre bit est la valeur affectée à la position pos de la suite. La valeur de bit doit être $0$ ou $1$. Si la fonction est appelée avec une autre valeur, votre programme est considéré comme donnant une réponse incorrecte (Wrong Answer[3]).

La fonction Set doit être appelée exactement $N$ fois dans la fonction Anna. Si, lorsque la fonction Anna se termine, le nombre d'appels à Set est différent de $N$, votre programme est considéré comme donnant une réponse incorrecte (Wrong Answer[4]).

Votre programme est arrêté si un appel effectué par Anna est considéré comme invalide.

Le second fichier est Bruno.c ou Bruno.cpp. Il retrouve l'entier représentant les résultats de l'étude et implémente la fonction suivante. Le programme doit inclure Brunolib.h.

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

Pour chaque cas de test, cette fonction est appelée $Q=1\,000$ fois.

• Le paramètre N est la longueur de la suite reçue par Bruno.
• Le paramètre A est une suite d'entiers de longueur $N$. Il s'agit de la suite reçue par Bruno.
• La fonction Bruno doit retrouver la valeur de $X$ et la renvoyer.

Procédure d'évaluation

L'évaluation se déroule comme suit. Si votre programme est considéré comme donnant une réponse incorrecte, il est immédiatement arrêté.

1. Définir $\mathrm{cnt}=0$.
2. Appeler une fois la fonction Anna.
3. Soit $S$ la suite définie par la fonction Anna. Dans $S$, affecter la valeur $0$ aux positions de $P$ pour obtenir la suite $A$. Appeler une fois la fonction Bruno avec le paramètre $A$.
4. Définir $\mathrm{cnt}=\mathrm{cnt}+1$. Si $\mathrm{cnt}<Q$, retourner à l'étape (2). Si $\mathrm{cnt}=Q$, passer à l'étape (5).
5. Votre programme reçoit un score.

Remarques importantes

• Le temps d'exécution et l'utilisation de la mémoire sont calculés pour les étapes (1), (2), (3) et (4) de la procédure d'évaluation.
• Votre programme ne doit pas être considéré comme donnant une réponse incorrecte lors de l'appel à Anna à l'étape (2) ni à Bruno à l'étape (3). Il doit s'exécuter sans erreur d'exécution.
• Votre programme peut implémenter d'autres fonctions à usage interne ou utiliser des variables globales. Les programmes soumis seront compilés avec le programme d'évaluation pour former un seul exécutable. Toutes les variables globales et fonctions internes doivent être déclarées static afin d'éviter les conflits avec les autres fichiers. Comme les programmes d'Anna et de Bruno sont exécutés dans deux processus distincts lors de l'évaluation, ils ne peuvent pas partager de variables globales.
• Au cours de ce processus, chacune des fonctions Anna et Bruno est appelée $Q=1\,000$ fois. Les variables utilisées par vos programmes doivent être initialisées correctement.
• Votre programme ne doit utiliser ni l'entrée standard ni la sortie standard. Il ne doit communiquer avec d'autres fichiers par aucun moyen.

Compilation et exécution de test

Vous pouvez télécharger sur la page web du concours une archive contenant un programme d'évaluation d'exemple pour tester votre programme. Elle contient également un exemple de code source de votre programme.

Le programme d'évaluation d'exemple est constitué d'un fichier source, grader.c ou grader.cpp. Par exemple, si vos programmes sont Anna.c et Bruno.c, ou Anna.cpp et Bruno.cpp, exécutez les commandes suivantes pour les compiler.

• 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

Lorsque la compilation réussit, le fichier exécutable grader est créé.

Remarquez que le programme d'évaluation réel diffère de celui fourni en exemple. Ce dernier s'exécute dans un seul processus, qui lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée du programme d'évaluation d'exemple

Le programme d'évaluation d'exemple lit les données suivantes sur l'entrée standard.

• La première ligne contient un entier $Q$.
• Viennent ensuite les informations de $Q$ requêtes.
• Les informations de chaque requête sont constituées de deux lignes, comme suit.

La première ligne contient trois entiers $N,X,K$ séparés par des espaces. Cela signifie que la longueur de la suite à envoyer est $N$, que l'entier qu'Anna doit transmettre est $X$ et qu'il y a $K$ positions défectueuses.

La seconde ligne contient $K$ entiers $P_0,P_1,\ldots,P_{K-1}$ séparés par des espaces. Cela signifie que, pour chaque $i$ tel que $0 \le i \le K-1$, la position $P_i$ de la suite est défectueuse.

Sortie du programme d'évaluation d'exemple

Lorsque le programme se termine correctement, le programme d'évaluation d'exemple écrit les informations suivantes sur la sortie standard. (Les guillemets ne sont pas réellement écrits.)

• Si votre programme est considéré comme donnant une réponse incorrecte, le programme d'évaluation d'exemple écrit son type sous la forme Wrong Answer [1], puis votre programme est arrêté.
• Si aucun appel à Anna n'est considéré comme donnant une réponse incorrecte, le programme d'évaluation d'exemple écrit Accepted et la valeur de $L^*$. Pour la valeur de $L^*$, consultez la section « Sous-tâches ».

Si votre programme est considéré comme donnant plusieurs types de réponses incorrectes, le programme d'évaluation d'exemple n'en signale qu'un seul.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$ pour $0 \le i \le K-1$.
• $P_i<P_{i+1}$ pour $0 \le i \le K-2$.

Sous-tâches

• Soit $L^*$ le minimum, sur tous les cas de test de cette tâche, de la valeur suivante.

Le plus grand entier $L \le 40$ tel que, pour toute requête où $K \le L$, Bruno renvoie la valeur correcte de $X$.

• Le score de cette tâche est calculé comme suit :

Si $L^*=0$, le score est de $0$ point.

Si $1 \le L^* \le 14$, le score est de $8$ points.

Si $15 \le L^* \le 37$, le score est de $(L^*-15)\times 2+41$ points.

Si $38 \le L^* \le 40$, le score est de $(L^*-38)\times 5+90$ points.

Exemples

Voici un exemple d'entrée du programme d'évaluation et les appels de fonctions correspondants. Remarquez que cet exemple ne satisfait pas les contraintes de la tâche, car $Q=2$ et $N=3$.

Entrée 1

2
3 14 1
2
3 9 2
0 1

Appels d'exemple

Les paramètres de Anna(...), Bruno(...), Anna(...) et Bruno(...) sont les suivants.