Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Interactif
Statistiques

Description

On considère un graphe orienté à $n$ sommets numérotés de $1$ à $n$. Pour chaque sommet $1 \le i \le n$, le demi-degré extérieur du sommet $i$ vaut au plus un ; on peut donc décrire le graphe à l'aide d'un tableau $p_i$, où $p_i = 0$ si le demi-degré extérieur du sommet $i$ est nul, et sinon $1 \le p_i \le n$, $p_i \ne i$, et il existe un arc orienté de $i$ vers $p_i$. Il n'y a aucun cycle orienté dans le graphe, de sorte qu'en partant de n'importe quel sommet $i$, le chemin formé en se déplaçant de manière répétée vers le sommet suivant le long des arcs orientés finira toujours par s'arrêter sur un sommet de demi-degré extérieur nul.

Initialement, un pion en bois est posé sur l'un des sommets. Lorsque vous frappez dans vos mains, si le pion se trouve sur un sommet $i$ tel que $p_i$ est non nul, il se déplace vers le sommet $p_i$ ; sinon, il ne bouge pas. Cependant, vous ne pouvez pas du tout voir où se trouve le pion — la seule opération que vous pouvez effectuer consiste à choisir un sous-ensemble de sommets, placer le pion sur l'un des sommets choisis, frapper dans vos mains un certain nombre de fois, et observer si le pion finit sur l'un des sommets que vous avez choisis. Même la position initiale du pion et le nombre de fois où vous frappez dans vos mains sont choisis par un interacteur : vous pouvez seulement choisir le sous-ensemble de sommets et observer le nombre maximal de fois où vous pouvez frapper dans vos mains de sorte que le pion puisse partir de l'un de vos sommets choisis et arriver sur l'un de vos sommets choisis.

Vous souhaitez ajouter un unique arc allant de $x$ à $y$ ($1 \le x, y \le n$, $x \ne y$ et $p_x = 0$, c'est-à-dire que vous pouvez poser $p_x = y$), afin de pouvoir frapper dans vos mains encore plus de fois sur le graphe entier qu'auparavant. Toutefois, l'ajout de cet arc ne doit créer aucun cycle orienté dans le graphe.

Trouvez un tel arc à ajouter en interrogeant le nombre maximal de battements de mains sur au plus $n$ sous-ensembles de sommets, ou déterminez qu'il est impossible d'ajouter un tel arc.

Entrée

La première ligne de l'entrée contient un seul entier $n$ ($1 \le n \le 1000$).

Interaction

Pour effectuer une requête, affichez une seule ligne de la forme $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, où $1 \le k \le n$, et $1 \le u_i \le n$ sont des sommets deux à deux distincts dans le sous-ensemble choisi. Lisez ensuite une seule ligne contenant un unique entier : le nombre maximal de fois où vous pouvez frapper dans vos mains de sorte que le pion puisse partir de l'un des sommets choisis et terminer sur l'un des sommets choisis. Vous pouvez effectuer au plus $n$ requêtes.

Une fois que vous avez déterminé l'arc que vous souhaitez ajouter, affichez une seule ligne de la forme $\texttt{! } x \text{ } y$, où $1 \le x, y \le n$ sont les extrémités de l'arc orienté que vous souhaitez ajouter. S'il existe plusieurs solutions, vous pouvez afficher n'importe laquelle d'entre elles.

S'il est impossible d'ajouter un tel arc, affichez $-1 \text{ -1}$ à la place des extrémités de l'arc.

Votre programme doit se terminer immédiatement après avoir affiché la réponse.

Videz le tampon de sortie (flush) après chaque requête effectuée.

L'interacteur n'est pas adaptatif ; le graphe est fixé à l'avance.

Exemple

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Note

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.