Anna y Bruno son maestros del juego. Jugarán con D-taro, que es el crupier.
En este juego, Anna y Bruno están en habitaciones distintas. Solo pueden comunicarse mediante un dispositivo averiado. D-taro entrega un entero a Anna. El objetivo de Anna y Bruno es transmitir ese entero de Anna a Bruno usando el dispositivo.
Al comenzar el juego, Anna declara primero un entero $m$ entre $1$ y $2\,000$, ambos incluidos. Después juegan $Q$ rondas. La ronda $i$ ($1\le i\le Q$) se desarrolla así:
- D-taro entrega un entero $A_i$ a Anna.
- Anna introduce los arreglos $s_i,t_i$ en el dispositivo. Cada elemento de $s_i,t_i$ debe ser $0$ o $1$. Los arreglos deben tener la misma longitud, comprendida entre $1$ y $m$, ambos incluidos.
- Sea $u_i$ un arreglo obtenido de $s_i$ y $t_i$ mediante una mezcla por intercalado (véase más abajo). El dispositivo envía $u_i$ a Bruno.
- Bruno envía un entero a D-taro. Si es igual al entero $A_i$ que D-taro entregó a Anna, Anna y Bruno ganan esa ronda.
Escribe programas que implementen las estrategias de Anna y Bruno para que ganen las $Q$ rondas.
Mezcla por intercalado
Decimos que un arreglo $Z$ se obtiene de los arreglos $X$ e $Y$ mediante una mezcla por intercalado si podemos dividir los elementos de $Z$ en dos grupos que satisfagan las dos condiciones siguientes.
- El arreglo formado por los elementos del primer grupo, conservando su orden, es igual a $X$.
- El arreglo formado por los elementos del segundo grupo, conservando su orden, es igual a $Y$.
Por ejemplo, el arreglo $Z=[1,1,1,0,0,0]$ se obtiene de $X=[1,1,0]$ e $Y=[1,0,0]$ mediante una mezcla por intercalado, porque el arreglo formado por el primer, segundo y cuarto elementos de $Z$, en ese orden, es $[1,1,0]$, y el formado por el tercer, quinto y sexto elementos de $Z$, en ese orden, es $[1,0,0]$.
En cambio, si $X=[1,1,0]$, $Y=[1,0,0]$ y $Z=[0,0,0,1,1,1]$, el arreglo $Z$ no se obtiene de $X$ e $Y$ mediante una mezcla por intercalado.
Detalles de implementación
Debes entregar dos archivos.
El primero es Anna.cpp. Debe implementar la estrategia de Anna y las funciones siguientes. El programa debe incluir Anna.h mediante la directiva de preprocesamiento #include.
int Declare()Esta función se llama una vez al principio.
- El valor devuelto es el entero $m$ declarado por Anna.
- El entero $m$ debe estar entre $1$ y $2\,000$, ambos incluidos. Si no se cumple esta condición, el programa recibe el veredicto Wrong Answer [1].
std::pair<std::vector<int>, std::vector<int> > Anna(long long A)Después de llamar a
Declare, esta función se llama $Q$ veces. Su llamada $i$ ($1\le i\le Q$) corresponde a los pasos 1 y 2 de la ronda $i$.- El parámetro
Aes el entero $A_i$ entregado por D-taro a Anna. - El valor devuelto es el par de arreglos $s_i,t_i$ que Anna introduce en el dispositivo.
- Cada elemento de $s_i,t_i$ debe ser $0$ o $1$. Si no se cumple esta condición, el programa recibe el veredicto Wrong Answer [2].
- Las longitudes de ambos arreglos $s_i,t_i$ deben estar entre $1$ y $m$, ambos incluidos. Si no se cumple esta condición, el programa recibe el veredicto Wrong Answer [3].
- Los arreglos $s_i,t_i$ deben tener la misma longitud. Si no se cumple esta condición, el programa recibe el veredicto Wrong Answer [4].
- El parámetro
El segundo archivo es Bruno.cpp. Debe implementar la estrategia de Bruno y la función siguiente. El programa debe incluir Bruno.h mediante la directiva de preprocesamiento #include.
long long Bruno(std::vector<int> u)Después de que Anna introduce los arreglos en el dispositivo, esta función se llama una vez. En total, se llama $Q$ veces. Su llamada $i$ ($1\le i\le Q$) corresponde a los pasos 3 y 4 de la ronda $i$.
- El parámetro
ues el arreglo $u_i$ enviado por el dispositivo a Bruno en la ronda $i$. - El valor devuelto es el entero que Bruno envía a D-taro.
- El valor devuelto debe ser igual al entero $A_i$ que D-taro entregó a Anna. Si no se cumple esta condición, el programa recibe el veredicto Wrong Answer [5].
- El parámetro
Avisos importantes
- El programa puede implementar otras funciones para uso interno o utilizar variables globales. Los archivos entregados se compilarán junto con el evaluador para formar un único ejecutable. Todas las variables globales y funciones internas deben declararse en un espacio de nombres anónimo para evitar conflictos con otros archivos. Durante la evaluación se ejecutarán dos procesos: el de Anna y el de Bruno. Estos procesos no pueden compartir variables globales.
- El programa no debe utilizar la entrada ni la salida estándar. No debe comunicarse con otros archivos por ningún medio. Sin embargo, puede escribir información de depuración en la salida de error estándar.
Compilación y ejecución de pruebas
Puedes descargar de la página del concurso un archivo comprimido que contiene el evaluador de ejemplo para probar tu programa. También contiene un archivo de código fuente de ejemplo para tu programa.
El evaluador de ejemplo es el archivo grader.cpp. Para probar tu programa, coloca grader.cpp, Anna.cpp, Bruno.cpp, Anna.h y Bruno.h en el mismo directorio y ejecuta el siguiente comando para compilar los programas.
g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp
Si la compilación termina correctamente, se genera el ejecutable grader.
Ten en cuenta que el evaluador real es distinto del 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 para el evaluador de ejemplo
El evaluador de ejemplo lee los siguientes datos de la entrada estándar.
$$ \begin{array}{l} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{array} $$
Salida del evaluador de ejemplo
El evaluador de ejemplo escribe la siguiente información en la salida estándar (las comillas son para mayor claridad).
- Si el programa se considera correcto, escribe el valor $m$ devuelto por
Declarecon el formatoAccepted: 2000. - Si el programa recibe algún veredicto Wrong Answer, el evaluador de ejemplo escribe su tipo como
Wrong Answer [1].
Si el programa satisface las condiciones de varios tipos de Wrong Answer, el evaluador de ejemplo informa solo de uno.
Al ejecutar el evaluador de ejemplo, la mezcla por intercalado de cada ronda se calcula mediante números seudoaleatorios. Los resultados no cambian entre ejecuciones. Para cambiar la semilla de los números seudoaleatorios, ejecuta el evaluador de ejemplo así:
./grader 2022
El primer argumento debe ser un entero.
Restricciones
- $1\le Q\le 1\,000$.
- $1\le A_i\le 1\,000\,000\,000\,000\,000\,000$ ($=10^{18}$) ($1\le i\le Q$).
Subtareas
- (5 puntos) $A_i\le 2\,000$ ($1\le i\le Q$).
- (5 puntos) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
- (3 puntos) $A_i\le 10\,000\,000$ ($=10^7$) ($1\le i\le Q$).
- (12 puntos) $A_i\le 100\,000\,000$ ($=10^8$) ($1\le i\le Q$).
- (15 puntos) $A_i\le 100\,000\,000\,000$ ($=10^{11}$) ($1\le i\le Q$).
(60 puntos) Sin restricciones adicionales. En esta subtarea, tu puntuación se calcula de la siguiente manera.
- Sea $m^*$ el máximo de los enteros $m$ declarados por Anna entre todos los casos de prueba de esta subtarea.
- Tu puntuación es la siguiente.
| Valor de $m^*$ | Puntuación |
|---|---|
| $201\le m^*\le 2\,000$ | $40-25\times\log_{10}\left(\frac{m^*}{200}\right)$ puntos (redondeado hacia abajo al entero más próximo) |
| $161\le m^*\le 200$ | 40 puntos |
| $156\le m^*\le 160$ | 44 puntos |
| $151\le m^*\le 155$ | 48 puntos |
| $146\le m^*\le 150$ | 52 puntos |
| $141\le m^*\le 145$ | 56 puntos |
| $m^*\le 140$ | 60 puntos |
Ejemplo de comunicación
A continuación se muestra una entrada de ejemplo para el evaluador de ejemplo y las llamadas a funciones correspondientes.
Entrada 1
2 42 2000
Llamadas a funciones de ejemplo
| Llamada | Valor devuelto |
|---|---|
Declare() |
4 |
Anna(42) |
([0, 0, 1, 0], [1, 1, 0, 1]) |
Bruno([1, 0, 0, 1, 0, 1, 0, 1]) |
42 |
Anna(2000) |
([0, 1], [0, 0]) |
Bruno([0, 0, 1, 0]) |
2000 |
En esta entrada de ejemplo hay $Q$ ($=2$) rondas. En la ronda $1$, D-taro entrega a Anna el entero $A_1$ ($=42$). En la ronda $2$, D-taro entrega a Anna el entero $A_2$ ($=2000$).
Esta entrada de ejemplo satisface las restricciones de todas las subtareas.