Anna y Bruno son arqueólogos. Están investigando unas ruinas en Irán.

Sus tareas son las siguientes: Anna visita las ruinas y descubre objetos antiguos, y Bruno analiza los resultados en el campamento base.

Su investigación está programada para $Q\,(=1\,000)$ días. Cada día, Anna envía los resultados a Bruno mediante un dispositivo de comunicación. Los resultados de cada día se expresan como un entero $X$.

Anna solo puede utilizar el dispositivo una vez al día. Este puede enviar una secuencia de longitud $N\,(=150)$ formada por $0$ y $1$.

Sin embargo, el dispositivo está averiado. Hay varias posiciones averiadas en la secuencia de longitud $N$. En una posición averiada, siempre envía el valor $0$, independientemente del valor que se haya establecido. Cuando Anna envía una secuencia, puede ver las posiciones averiadas, pero Bruno no las conoce. Tanto las posiciones averiadas como su número pueden cambiar cada día.

Existe el peligro de que su investigación se retrase. Como eres candidato a participar en un concurso internacional de programación en Irán, Anna y Bruno te piden que escribas un programa que transmita los resultados de su investigación.

Tarea

Escribe dos programas que permitan la comunicación entre Anna y Bruno.

• Dadas la longitud de la secuencia $N$, el entero que se enviará $X$, el número de posiciones averiadas $K$ y sus posiciones $P$, el primer programa establece la secuencia $S$ que envía Anna.
• Dada la secuencia $A$ que recibe Bruno, el segundo programa recupera el entero $X$.

En una posición donde el dispositivo funciona, las secuencias $S$ y $A$ tienen el mismo valor. En una posición averiada, la secuencia $A$ siempre tiene el valor $0$, independientemente del valor de la secuencia $S$.

Detalles de implementación

Debes entregar dos archivos escritos en el mismo lenguaje de programación.

El primer archivo es Anna.c o Anna.cpp. Este archivo establece la secuencia que envía Anna e implementa la siguiente función. El programa debe incluir Annalib.h.

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

  En cada caso de prueba, esta función se llama $Q=1\,000$ veces.

  • El parámetro N es la longitud de la secuencia que se enviará.
  • El parámetro X es el entero que se enviará.
  • El parámetro K es el número de posiciones averiadas.
  • El parámetro P[] es una secuencia de longitud $K$ que describe las posiciones averiadas.

En la función Anna, se debe llamar a la siguiente función.

• void Set( int pos, int bit )

  Esta función establece un bit de la secuencia $S$ que enviará el dispositivo de comunicación.

  • El parámetro pos es la posición que se establecerá. pos debe ser un entero entre $0$ y $N-1$, ambos incluidos. Ten en cuenta que las posiciones se numeran desde $0$. Si se llama con un parámetro fuera de este intervalo, tu programa se considera Wrong Answer[1]. No se permite llamar a esta función más de una vez con el mismo parámetro pos. Si se llama más de una vez con el mismo parámetro, tu programa se considera Wrong Answer[2].
  • El parámetro bit es el valor que se establece en la posición pos de la secuencia. El valor de bit debe ser $0$ o $1$. Si se llama con otro valor, tu programa se considera Wrong Answer[3].

La función Set debe llamarse exactamente $N$ veces dentro de la función Anna. Cuando termina Anna, si el número de llamadas a Set es distinto de $N$, tu programa se considera Wrong Answer[4].

Tu programa termina si una llamada realizada por Anna se considera inválida.

El segundo archivo es Bruno.c o Bruno.cpp. Este archivo recupera el entero que expresa los resultados de la investigación e implementa la siguiente función. El programa debe incluir Brunolib.h.

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

  En cada caso de prueba, esta función se llama $Q=1\,000$ veces.

  • El parámetro N es la longitud de la secuencia recibida por Bruno.
  • El parámetro A es una secuencia de enteros de longitud $N$. Es la secuencia recibida por Bruno.
  • La función Bruno debe recuperar el valor de $X$ y devolverlo.

Procedimiento de evaluación

La evaluación se realiza de la siguiente manera. Si tu programa se considera una respuesta incorrecta, termina inmediatamente.

1. Establecer cnt = 0.
2. Llamar una vez a la función Anna.
3. Sea $S$ la secuencia establecida por Anna. En la secuencia $S$, poner el valor $0$ en las posiciones de $P$ para obtener la secuencia $A$. Llamar una vez a Bruno con el parámetro $A$.
4. Establecer cnt = cnt +1. Si $\mathrm{cnt}<Q$, volver a (2). Si $\mathrm{cnt}=Q$, ir a (5).
5. Se asigna la puntuación a tu programa.

Avisos importantes

• El tiempo de ejecución y el uso de memoria se calculan para los pasos (1), (2), (3) y (4) del procedimiento de evaluación.
• Tu programa no debe considerarse una respuesta incorrecta en la llamada a Anna de (2) ni en la llamada a Bruno de (3). Tu programa debe ejecutarse sin errores de ejecución.
• Tu programa puede implementar otras funciones para uso interno o utilizar variables globales. Los programas entregados se compilarán junto con el evaluador para generar un único archivo ejecutable. Todas las variables globales y funciones internas deben declararse static para evitar conflictos con otros archivos. Como los programas de Anna y Bruno se ejecutan en dos procesos distintos durante la evaluación, no pueden compartir variables globales.
• Durante el proceso, cada una de las funciones Anna y Bruno se llama $Q=1\,000$ veces. Las variables utilizadas por tus programas deben inicializarse adecuadamente.
• Tu programa no debe utilizar la entrada ni la salida estándar. Tampoco debe comunicarse con otros archivos por ningún medio.

Compilación y ejecución de prueba

Puedes descargar de la página web del concurso un archivo comprimido que contiene un evaluador de ejemplo para probar tu programa. El archivo también contiene un código fuente de ejemplo para tu programa.

El evaluador de ejemplo consta de un archivo fuente, grader.c o grader.cpp. Por ejemplo, si tus programas son Anna.c y Bruno.c, o Anna.cpp y Bruno.cpp, ejecuta los siguientes comandos para compilarlos.

• 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

Si la compilación tiene éxito, se genera el archivo ejecutable grader.

Ten en cuenta que el evaluador real es distinto del evaluador de ejemplo. El evaluador de ejemplo se ejecuta como un único proceso, que lee datos de la entrada estándar y escribe los resultados en la salida estándar.

Entrada del evaluador de ejemplo

El evaluador de ejemplo lee los siguientes datos de la entrada estándar.

• La primera línea contiene un entero $Q$.
• A continuación se proporciona la información de $Q$ consultas.

• La información de cada consulta consta de las dos líneas siguientes.

  • La primera línea contiene tres enteros $N$, $X$ y $K$ separados por espacios. Esto significa que la longitud de la secuencia que se enviará es $N$, el entero que enviará Anna es $X$ y hay $K$ posiciones averiadas.
  • La segunda línea contiene $K$ enteros $P_0,P_1,\ldots,P_{K-1}$ separados por espacios. Esto significa que, para cada $i$ ($0 \le i \le K-1$), la posición $P_i$ de la secuencia está averiada.

Salida del evaluador de ejemplo

Cuando el programa termina correctamente, el evaluador de ejemplo escribe la siguiente información en la salida estándar. (Las comillas no se escriben realmente).

• Si tu programa se considera una respuesta incorrecta, el evaluador de ejemplo escribe su tipo con el formato Wrong Answer [1] y tu programa termina.
• Si ninguna llamada a Anna se considera una respuesta incorrecta, el evaluador de ejemplo escribe Accepted y el valor de $L^*$. Para conocer el significado de $L^*$, consulta la sección «Subtareas».

Si tu programa se considera una respuesta incorrecta de varios tipos, el evaluador de ejemplo solo informa de uno de ellos.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

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

Subtareas

• Sea $L^*$ el mínimo, entre todos los casos de prueba de esta tarea, del siguiente valor.

  • El mayor entero $L \le 40$ tal que, para toda consulta con $K \le L$, Bruno responde con el valor correcto de $X$.

• La puntuación de esta tarea se calcula de la siguiente manera:

  • Si $L^*=0$, la puntuación es de $0$ puntos.
  • Si $1 \le L^* \le 14$, la puntuación es de $8$ puntos.
  • Si $15 \le L^* \le 37$, la puntuación es de $(L^*-15)\times 2+41$ puntos.
  • Si $38 \le L^* \le 40$, la puntuación es de $(L^*-38)\times 5+90$ puntos.

Ejemplo de comunicación

A continuación se muestra una entrada de ejemplo para el evaluador y las llamadas a funciones correspondientes. Ten en cuenta que este ejemplo no cumple las restricciones de la tarea, ya que $Q=2$ y $N=3$.

Entrada 1

2
3 14 1
2
3 9 2
0 1

Llamadas de ejemplo

Los parámetros de Anna(...), Bruno(...), Anna(...) y Bruno(...), en ese orden, son los siguientes.