Este es un problema interactivo.
Contexto
Tras medio año, I 君 ya no puede mantener abierta su tienda. Decide traspasarla y convertirse en explorador para descubrir el vasto mundo desconocido.
Siguiendo un libro antiguo, encuentra en el corazón de un gran desierto un palacio subterráneo creado por una civilización desconocida. El palacio consta de $N$ grandes cuevas y $M$ pasadizos bidireccionales que las conectan. El libro permite a I 君 identificar la cueva en la que se encuentra, pero no describe cómo se conectan los $M$ pasadizos, por lo que le resulta difícil buscar los tesoros inagotables que, según la leyenda, esconde el palacio.
Ahora ha descubierto un mecanismo misterioso que proporciona información sobre el palacio. Decide utilizarlo para averiguar su estructura de conexiones. Ayúdalo.
Descripción
El palacio subterráneo se puede representar como un grafo simple no dirigido de $N$ vértices y $M$ aristas. En un grafo simple hay como máximo una arista directamente entre cada pareja de vértices. Las cuevas están numeradas de $0$ a $n-1$. Actualmente desconoces cuáles son las aristas.
Cada cueva tiene una fuente de luz que puede estar encendida o apagada. Una cueva solo está iluminada cuando su fuente está encendida. Inicialmente todas están apagadas, y sus estados solo pueden cambiarse mediante el mecanismo misterioso descubierto por I 君. Concretamente, permite realizar estas cuatro operaciones:
- Se proporciona un número $x$ y el mecanismo invierte el estado de la luz de la cueva $x$ y de todas las cuevas conectadas directamente con ella por un pasadizo: las luces encendidas se apagan y las apagadas se encienden.
- Se proporciona un número $x$ y el mecanismo muestra el estado actual de la luz de la cueva $x$.
- Se proporcionan dos números $x,y$ para indicar que has determinado que existe un pasadizo entre esas cuevas y hacer que el mecanismo lo registre.
- Se proporciona un número $x$ y el mecanismo comprueba si ya se han registrado todos los pasadizos conectados con la cueva $x$.
Solo se puede realizar una operación después de que haya terminado la anterior. El mecanismo no puede utilizarse libremente: los límites de uso de las cuatro operaciones son, respectivamente, $L_m,L_q,M,L_c$. Debes escribir un programa que ayude a I 君 a utilizarlo adecuadamente para encontrar correctamente los $M$ pasadizos.
Detalles de implementación
No necesitas ni debes implementar la función principal. Solo debes implementar explore(N, M), donde $N,M$ son el número de cuevas y de pasadizos. Puedes interactuar con la biblioteca mediante estas cuatro funciones:
1. modify(x)
- Ejecuta la operación 1 del mecanismo con el número $x$.
- Debes garantizar $0\le x<N$. La función no devuelve ningún valor.
2. query(x)
- Ejecuta la operación 2 del mecanismo con el número $x$.
- Debes garantizar $0\le x<N$. Devuelve $0$ o $1$, indicando que la luz de la cueva $x$ está apagada ($0$) o encendida ($1$), respectivamente.
3. report(x, y)
- Ejecuta la operación 3 del mecanismo con los números $x,y$.
- Debes garantizar $0\le x,y<N$ y $x\ne y$. No devuelve ningún valor.
4. check(x)
- Ejecuta la operación 4 del mecanismo con el número $x$.
- Debes garantizar $0\le x<N$. Devuelve $0$ o $1$, y devuelve $1$ si y solo si todos los pasadizos conectados con la cueva $x$ se han registrado mediante la operación 3.
Durante la evaluación, la biblioteca llama a explore exactamente una vez.
Se garantiza que el grafo utilizado está completamente determinado antes de comenzar la interacción y no se construye dinámicamente según la interacción con tu programa. Por tanto, todas las operaciones son deterministas y no necesitas conocer los detalles de su implementación en la biblioteca.
Se garantiza que, respetando los límites de llamadas, el tiempo de ejecución de la biblioteca no supera 1 segundo. Su consumo de memoria es fijo y no supera 128 MB.
Método de implementación
En el directorio de trabajo del concursante se proporciona template_explore.cpp/c/pas. Cópialo, renombra la copia como explore.cpp/c/pas y desarrolla tu solución a partir de ella.
Para participantes que utilicen C++ o C
- Asegúrate de incluir
#include "explore.h"al principio de tu programa. - La interfaz de la función
exploreque debes implementar es:
void explore(int N, int M);- Las interfaces de las funciones de interacción disponibles son:
void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);Para participantes que utilicen Pascal
- Atención: la sintaxis de implementación de la interfaz en Pascal es relativamente compleja. Trabaja directamente sobre el archivo proporcionado
template_explore.pas, en lugar de escribir el código desde cero. - La interfaz de la función que debes implementar es:
procedure _explore(N, M : longint);- Atención: su nombre es
_explore, noexplore. Utilizarexplorehará que falle la compilación. - Las interfaces de las funciones de interacción disponibles son:
procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;Cómo probar el programa
Los archivos grader.cpp/c y graderhelperlib.pas del directorio del problema son implementaciones de referencia de la biblioteca de interacción. La implementación utilizada en la evaluación final difiere de ellas, por lo que tu solución no debe depender de cómo esté implementada la biblioteca.
Para participantes que utilicen C/C++
Debes compilar el ejecutable en el directorio del problema mediante estos comandos:
Para C:
gcc grader.c explore.c -o explore -O2 -lmPara C++:
g++ grader.cpp explore.cpp -o explore -O2 -lmPara participantes que utilicen Pascal
Debes compilar el ejecutable en el directorio del problema mediante el siguiente comando:
fpc grader.pas -o"explore" -O2Para el ejecutable obtenido
El ejecutable lee de la entrada estándar los datos con el siguiente formato:
La primera línea contiene tres enteros $L_m,L_q,L_c$ y la segunda dos enteros $N,M$, con los significados de la descripción.
Cada una de las siguientes $M$ líneas contiene dos enteros $x,y$, que describen un pasadizo entre las cuevas $x$ e $y$.
Después de leer los datos, la biblioteca llama a explore exactamente una vez para probar tu función con ellos. Cuando tu función retorna correctamente, la biblioteca comprueba si tu cálculo es correcto. Si lo es, imprime Correct e información sobre el número de llamadas a las funciones de interacción; de lo contrario, imprime el mensaje de error correspondiente.
Ejemplo de interacción
Supongamos que el ejecutable lee los siguientes datos:
100 200 300 3 2 0 1 1 2
Los tres enteros de la primera línea indican los límites de llamadas de tres operaciones: modify(x) no puede llamarse más de 100 veces, query(x) más de 200 veces y check(x) más de 300 veces.
Los dos enteros de la segunda línea indican el número de cuevas y el de pasadizos: $N=3$, $M=2$.
El número de llamadas a report(x, y) no puede superar $M$, que en este ejemplo es 2.
El siguiente proceso de interacción es correcto:
| Programa del concursante | Biblioteca de interacción | Nota |
|---|---|---|
Llama a explore(3, 2) |
Comienza la prueba | |
Llama a modify(0) |
Aplica la operación 1 a la cueva $0$ | |
Llama a query(2) |
Devuelve $0$ | La luz de la cueva $2$ está apagada |
Llama a report(0, 1) |
Descubre y registra el pasadizo $(0,1)$ | |
Llama a check(0) |
Devuelve $1$ | Todos los pasadizos de la cueva $0$ están registrados |
Llama a report(2, 1) |
Descubre y registra el pasadizo $(2,1)$ | |
| Termina y retorna | Imprime Correct en pantalla |
La interacción termina con un resultado correcto |
Archivos proporcionados
En el directorio del problema:
grader.cpp/cygraderhelperlib.passon las implementaciones de referencia de la biblioteca de interacción.explore.hygrader.passon archivos de cabecera; no necesitas conocer su contenido concreto.template_explore.cpp/c/pascontiene el código fuente de ejemplo proporcionado para resolver el problema.explore1.in,explore2.in,explore3.inson entradas de ejemplo que puedes utilizar para probar tu programa.
Haz copias de seguridad de todos los archivos proporcionados. El evaluador solo recoge explore.c/cpp/pas del directorio del problema; los cambios en los demás archivos no tienen efecto.
Subtareas
La evaluación final solo recoge explore.cpp/c/pas. Modificar los demás archivos del directorio del concursante no tiene efecto sobre ella.
Se aplican primero las mismas restricciones que en un problema tradicional. Por ejemplo, un error de compilación hace que todo el problema obtenga 0 puntos, y un error de ejecución o superar los límites de tiempo o memoria hace que el caso de prueba correspondiente obtenga 0 puntos. Solo puedes acceder a las variables definidas por ti y a las proporcionadas por la biblioteca, y a sus espacios de memoria correspondientes. Intentar acceder a otros espacios puede causar errores de compilación o ejecución.
Bajo esas condiciones, obtienes la puntuación completa de un caso de prueba si y solo si:
- Todas tus llamadas son válidas, y los números de llamadas a
modify,query,checkno superan $L_m,L_q,L_c$, respectivamente. - Como el límite de llamadas a
reportes $M$, cada llamada debe registrar una arista nueva que exista. Es decir, al llamar areport(x, y)debe existir un pasadizo entre $x$ e $y$, y no se debe haber llamado antes areport(x, y)ni areport(y, x). - La función
exploreque has implementado retorna normalmente. - Cuando
exploreretorna, ya has registrado los $M$ pasadizos mediante llamadas areport.
Restricciones
Hay 25 casos de prueba, cada uno de 4 puntos. Los tamaños y límites correspondientes son:
| Caso de prueba | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Propiedad especial |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | Ninguna |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | Ninguna |
| $3$ | $200$ | $10N$ | $200$ | $4\times 10^4$ | $2M$ | Ninguna |
| $4$ | $300$ | $10N$ | $299$ | $9\times 10^4$ | $2M$ | Ninguna |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times 10^5$ | $2M$ | Ninguna |
| $6$ | $59998$ | $N/2$ | $17N$ | $17N$ | $0$ | A |
| $7$ | $99998$ | $N/2$ | $18N$ | $18N$ | $0$ | A |
| $8$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $9$ | $199998$ | $N/2$ | $19N$ | $19N$ | $0$ | A |
| $10$ | $99997$ | $N-1$ | $18N$ | $18N$ | $0$ | B |
| $11$ | $199997$ | $N-1$ | $19N$ | $19N$ | $0$ | B |
| $12$ | $99996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $13$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $14$ | $199996$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | C |
| $15$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $16$ | $99995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $17$ | $199995$ | $N-1$ | $10^7$ | $10^7$ | $2M$ | D |
| $18$ | $1004$ | $2000$ | $10^7$ | $5\times 10^4$ | $2M$ | Ninguna |
| $19$ | $1004$ | $3000$ | $10^7$ | $5\times 10^4$ | $2M$ | Ninguna |
| $20$ | $1004$ | $3000$ | $10^7$ | $5\times 10^4$ | $2M$ | Ninguna |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Ninguna |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Ninguna |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | Ninguna |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | Ninguna |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | Ninguna |
Recordamos que el grafo de la prueba queda completamente determinado antes de comenzar la interacción y no se construye dinámicamente según la interacción con tu programa.
Los símbolos de la columna de propiedades especiales significan lo siguiente:
A: se garantiza que el grado de cada vértice es exactamente $1$.
B: para cada $x>0$, existe exactamente un $y<x$ tal que las cuevas $x$ e $y$ están conectadas directamente por un pasadizo.
C: existe una permutación $p_0,p_1,\ldots,p_{N-1}$ de $0$ a $N-1$ tal que, para todo $1\le i<N$, hay un pasadizo entre las cuevas $p_{i-1}$ y $p_i$.
D: se garantiza que el grafo está conectado.
- Nota: tu programa puede distinguir los distintos tipos de datos anteriores mediante el dígito de las unidades del valor $N$ recibido.