Ce problème est interactif.
Contexte
Six mois plus tard, I 君 ne parvient finalement plus à faire fonctionner sa boutique. Il décide de la céder et de devenir explorateur pour découvrir le vaste monde inconnu.
En suivant les indications d'un livre ancien, il découvre, au cœur d'un immense désert, un palais souterrain créé par une civilisation inconnue. Le palais comprend $N$ grandes cavernes et $M$ passages bidirectionnels qui les relient. Grâce au livre, I 君 peut identifier la caverne où il se trouve, mais le livre ne décrit pas les connexions des $M$ passages ; il lui est donc difficile de chercher les trésors inépuisables que la légende situe dans le palais.
Cependant, I 君 vient de découvrir un mécanisme mystérieux qui fournit des informations sur le palais. Il décide de l'utiliser pour connaître les connexions du palais. Aidez-le.
Énoncé
Le palais souterrain peut être représenté par un graphe simple non orienté à $N$ sommets et $M$ arêtes (dans un graphe simple, deux sommets quelconques sont reliés directement par au plus une arête). Les cavernes sont numérotées de $0$ à $n-1$. Vous ne connaissez actuellement pas les arêtes.
Chaque caverne possède une source lumineuse, qui peut être allumée ou éteinte. Une caverne n'est éclairée que lorsque sa source est allumée. Initialement, toutes les sources sont éteintes ; leur état ne peut être modifié qu'avec le mécanisme mystérieux découvert par I 君. Plus précisément, le mécanisme permet les quatre opérations suivantes :
- Donner un numéro $x$ au mécanisme : il inverse l'état de la source de la caverne $x$ et de celles des cavernes directement reliées à $x$ par un passage. Les sources allumées s'éteignent et les sources éteintes s'allument.
- Donner un numéro $x$ au mécanisme : il affiche l'état actuel de la source de la caverne $x$.
- Donner deux numéros $x,y$ au mécanisme : vous affirmez qu'un passage relie les cavernes $x$ et $y$, et demandez au mécanisme de l'enregistrer.
- Donner un numéro $x$ au mécanisme : il détermine si tous les passages reliés à la caverne $x$ ont été enregistrés.
Le mécanisme ne peut effectuer une nouvelle opération qu'après avoir terminé la précédente. Il ne peut pas être utilisé librement : les nombres d'utilisations de ces opérations sont limités respectivement à $L_m,L_q,M,L_c$. Votre tâche consiste à écrire un programme qui aide I 君 à utiliser judicieusement le mécanisme afin de trouver correctement les $M$ passages.
Détails d'implémentation
Vous n'avez pas besoin et ne devez pas implémenter de fonction principale. Vous devez seulement implémenter la fonction explore(N, M), où $N$ et $M$ sont respectivement les nombres de cavernes et de passages. Vous pouvez interagir avec la bibliothèque en appelant les quatre fonctions suivantes :
modify(x)Cette fonction fait exécuter l'opération 1 au mécanisme avec le numéro $x$.
Vous devez garantir $0\le x<N$. Cette fonction ne renvoie aucune valeur.
query(x)Cette fonction fait exécuter l'opération 2 au mécanisme avec le numéro $x$.
Vous devez garantir $0\le x<N$. Elle renvoie $0$ ou $1$, indiquant si la source de la caverne $x$ est actuellement éteinte ($0$) ou allumée ($1$).
report(x, y)Cette fonction fait exécuter l'opération 3 au mécanisme avec les numéros $x,y$.
Vous devez garantir $0\le x,y<N$ et $x\ne y$. Cette fonction ne renvoie aucune valeur.
check(x)Cette fonction fait exécuter l'opération 4 au mécanisme avec le numéro $x$.
- Vous devez garantir $0\le x<N$. Elle renvoie $0$ ou $1$, et renvoie $1$ si et seulement si tous les passages reliés à la caverne $x$ ont été enregistrés par l'opération 3.
Pendant l'évaluation, la bibliothèque appelle explore exactement une fois.
Il est garanti que le graphe utilisé est entièrement fixé avant le début de l'interaction et n'est pas construit dynamiquement en fonction des échanges avec votre programme. Les opérations d'interaction sont donc déterministes et vous n'avez pas à vous préoccuper de leur implémentation dans la bibliothèque.
Il est garanti que, dans les limites du nombre d'appels, le temps d'exécution de la bibliothèque ne dépasse pas 1 seconde ; sa consommation de mémoire est fixe et ne dépasse pas 128 Mo.
Méthode d'implémentation
Le fichier template_explore.cpp/c/pas se trouve dans le répertoire de travail des candidats. Copiez-le, renommez la copie explore.cpp/c/pas et rédigez votre solution à partir de ce fichier.
Pour C++ / C
- Assurez-vous que votre programme commence par
#include "explore.h". - La signature de la fonction
exploreà implémenter est :
void explore(int N, int M);
- Les signatures des fonctions d'interaction disponibles sont :
void modify(int x); int query(int x); void report(int x, int y); int check(int x);
Pour Pascal
- Attention : la syntaxe d'implémentation des interfaces en Pascal est relativement complexe. Travaillez directement à partir du fichier fourni
template_explore.pas, au lieu d'écrire le programme depuis le début. - La signature de la fonction
exploreà implémenter est :
procedure _explore(N, M : longint);
- Attention : le nom de la fonction est ici
_explore, et nonexplore. Utiliserexploreprovoque une erreur de compilation. - Les signatures des fonctions d'interaction disponibles sont :
procedure modify(x : longint); function query(x : longint) : longint; procedure report(x : longint; y : longint); function check(x : longint) : longint;
Comment tester votre programme
Les fichiers grader.cpp/c et graderhelperlib.pas du répertoire du problème constituent l'implémentation de référence de la bibliothèque d'interaction que nous fournissons. L'implémentation utilisée lors de l'évaluation finale est différente de cette référence ; votre solution ne doit donc pas dépendre de l'implémentation de la bibliothèque.
Pour C/C++
- Dans le répertoire du problème, compilez avec la commande suivante pour obtenir l'exécutable :
- Pour C :
gcc grader.c explore.c -o explore -O2 -lm
- Pour C++ :
g++ grader.cpp explore.cpp -o explore -O2 -lm
Pour Pascal
- Dans le répertoire du problème, compilez avec la commande suivante pour obtenir l'exécutable :
fpc grader.pas -o"explore" -O2
Pour l'exécutable obtenu
- L'exécutable lit sur l'entrée standard les données au format suivant :
La première ligne contient trois entiers $L_m,L_q,L_c$ ; la deuxième contient deux entiers $N,M$, dont la signification est celle de l'énoncé.
Les $M$ lignes suivantes contiennent chacune deux entiers $x,y$ décrivant un passage entre les cavernes $x$ et $y$.
- Après la lecture, la bibliothèque appelle la fonction
exploreexactement une fois et teste votre fonction avec les données lues. Quand votre fonction se termine correctement, la bibliothèque vérifie votre résultat. S'il est correct, elle afficheCorrectet des informations sur les nombres d'appels des fonctions d'interaction ; sinon, elle affiche le message d'erreur correspondant.
Interaction
Supposons que l'exécutable lise les données suivantes :
100 200 300 3 2 0 1 1 2
Les trois entiers de la première ligne sont les limites du nombre d'appels des trois opérations : modify(x) peut être appelée au plus $100$ fois, query(x) au plus $200$ fois et check(x) au plus $300$ fois.
Les deux entiers de la deuxième ligne indiquent les nombres de cavernes et de passages : $N=3$, $M=2$.
Le nombre d'appels à report(x, y) ne doit pas dépasser $M$, soit 2 appels dans cet exemple.
Voici un déroulement d'interaction correct :
| Programme du candidat | Bibliothèque d'interaction | Explication |
|---|---|---|
Appelle explore(3, 2) |
Début du test | |
Appelle modify(0) |
Effectue l'opération 1 sur la caverne $0$ | |
Appelle query(2) |
Renvoie $0$ | La source de la caverne $2$ est actuellement éteinte |
Appelle report(0, 1) |
Découvre le passage $(0,1)$ et l'enregistre | |
Appelle check(0) |
Renvoie $1$ | Tous les passages reliés à la caverne $0$ ont été enregistrés |
Appelle report(2, 1) |
Découvre le passage $(2,1)$ et l'enregistre | |
| Termine son exécution et rend la main | Affiche Correct à l'écran |
Fin de l'interaction, résultat correct |
Description des fichiers fournis
Dans le répertoire de ce problème :
grader.cpp/cetgraderhelperlib.passont l'implémentation de référence de la bibliothèque d'interaction que nous fournissons.explore.hetgrader.passont des fichiers d'en-tête ; vous n'avez pas à vous préoccuper de leur contenu.template_explore.cpp/c/pascontient le code source d'exemple fourni pour résoudre le problème.explore1.in,explore2.inetexplore3.insont des exemples d'entrée que vous pouvez utiliser pour vos tests.
Faites des sauvegardes de tous les fichiers fournis. Seul le fichier explore.c/cpp/pas du répertoire de ce problème est recueilli pour l'évaluation ; les modifications des autres fichiers sont sans effet.
Sous-tâches
Lors de l'évaluation finale, seul explore.cpp/c/pas est recueilli. Modifier les autres fichiers du répertoire des candidats n'a aucun effet sur l'évaluation.
Ce problème est d'abord soumis aux mêmes restrictions qu'un problème classique. Par exemple, une erreur de compilation donne zéro point pour l'ensemble du problème ; une erreur d'exécution, un dépassement du temps ou de la mémoire autorisés donne zéro point pour le test correspondant. Vous ne pouvez accéder qu'aux variables que vous définissez et à celles fournies par la bibliothèque, ainsi qu'à leurs zones de mémoire correspondantes. Tenter d'accéder à d'autres zones peut entraîner une erreur de compilation ou d'exécution.
Sous ces conditions, vous obtenez la totalité des points d'un test si et seulement si :
- Tous vos appels de fonctions sont valides et les nombres d'appels à
modify,queryetcheckne dépassent pas respectivement $L_m,L_q,L_c$. - Puisque le nombre d'appels à
reportest limité à $M$, chaque appel doit enregistrer une arête nouvelle et existante. Autrement dit, chaque appelreport(x, y)doit satisfaire les conditions suivantes : un passage relie les cavernes $x$ et $y$, et aucun appelreport(x, y)oureport(y, x)n'a eu lieu auparavant. - La fonction
exploreque vous implémentez se termine normalement. - Au retour de
explore, vous avez enregistré les $M$ passages en appelantreport.
Contraintes
Ce problème comporte 25 tests, valant chacun 4 points. Les tailles des données et les limites correspondantes sont données ci-dessous.
| Numéro du test | $N=$ | $M=$ | $L_m=$ | $L_q=$ | $L_c=$ | Propriété particulière |
|---|---|---|---|---|---|---|
| $1$ | $3$ | $2$ | $100$ | $100$ | $100$ | Aucune |
| $2$ | $100$ | $10N$ | $200$ | $10^4$ | $2M$ | Aucune |
| $3$ | $200$ | $10N$ | $200$ | $4\times10^4$ | $2M$ | Aucune |
| $4$ | $300$ | $10N$ | $299$ | $9\times10^4$ | $2M$ | Aucune |
| $5$ | $500$ | $10N$ | $499$ | $1.5\times10^5$ | $2M$ | Aucune |
| $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\times10^4$ | $2M$ | Aucune |
| $19$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Aucune |
| $20$ | $1004$ | $3000$ | $10^7$ | $5\times10^4$ | $2M$ | Aucune |
| $21$ | $50000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Aucune |
| $22$ | $100000$ | $2N$ | $10^7$ | $10^7$ | $2M$ | Aucune |
| $23$ | $150000$ | $200000$ | $10^7$ | $10^7$ | $2M$ | Aucune |
| $24$ | $200000$ | $250000$ | $10^7$ | $10^7$ | $2M$ | Aucune |
| $25$ | $200000$ | $300000$ | $10^7$ | $10^7$ | $2M$ | Aucune |
Nous rappelons que le graphe utilisé pour les tests est entièrement fixé avant le début de l'interaction et n'est pas construit dynamiquement en fonction des échanges avec votre programme.
Voici la signification des lettres de la colonne des propriétés particulières :
A : chaque sommet a un degré exactement égal à $1$.
B : pour chaque $x>0$, il existe exactement un $y<x$ tel qu'un passage relie directement les cavernes $x$ et $y$.
C : il existe une permutation $p_0,p_1,\ldots,p_{N-1}$ de $0,\ldots,N-1$ telle que, pour tout $1\le i<N$, un passage relie les cavernes de numéros $p_{i-1}$ et $p_i$.
D : le graphe est connexe.
- Indication : votre programme peut distinguer les différents types de données ci-dessus en examinant le chiffre des unités du nombre $N$ reçu en paramètre.