Ceci est un problème interactif.

Une permutation $p$ de longueur $n=30000$ est cachée par le juge. Votre tâche est de trouver l’indice de la valeur minimale de cette permutation.

Le juge est non adaptatif : la permutation est choisie avant le début de l’interaction et ne change jamais.

Contrairement aux requêtes de comparaison ordinaires, le juge compare uniquement votre requête actuelle avec votre requête précédente. Plus précisément, si votre précédent indice interrogé était $i$ et que vous interrogez maintenant l’indice $j$, le juge vous donne la comparaison entre $p_i$ et $p_j$.

Vous pouvez effectuer au plus $q_{\max}=42000$ requêtes.

Les données de test officielles sont constituées de 100 fichiers de test séparés. Votre programme est exécuté indépendamment sur chaque fichier.

Interaction

Au début de l’interaction, votre programme doit lire deux entiers $$ n \quad q_{\max}. $$ Pour les tests officiels, $n=30000$ et $q_{\max}=42000$.

Pour faire une requête, affichez une ligne au format suivant : $$ \text{? j} $$ où $1 \le j \le n$.

Le juge répond par un seul caractère :

• < si $p_i < p_j$ où $i$ désigne la requête précédente (si applicable) ;
• = s’il s’agit de la première requête, ou si $p_i = p_j$ ;
• > si $p_i > p_j$ où $i$ désigne la requête précédente (si applicable).

Comme $p$ est une permutation, la réponse = après la première requête ne peut se produire que si vous interrogez le même indice que la requête précédente. Si le juge répond par -1, votre programme doit se terminer immédiatement. Cela signifie que votre programme a violé le protocole d’interaction et recevra une mauvaise réponse (Wrong Answer).

Pour donner votre réponse finale, affichez une ligne au format suivant : $$ \text{! a} $$ où $a$ est l’indice que vous affirmez contenir la valeur minimale. Après avoir affiché la réponse, votre programme doit se terminer. La réponse finale n’est pas comptée comme une requête.

Si votre programme effectue plus de $q_{\max}$ requêtes, interroge un indice invalide, affiche une commande invalide ou donne une réponse finale incorrecte, il reçoit une mauvaise réponse (Wrong Answer).

Après chaque requête ou réponse affichée, videz le tampon de sortie. Par exemple, en C++ vous pouvez utiliser endl ou cout.flush().

Remarque

Cet exemple n’est qu’une interaction d’exemple et n’apparaîtra pas dans les vraies données de test. Les lignes de la forme (receiving ... output) sont des placeholders utilisés uniquement pour aligner les requêtes et les réponses du juge dans l’exemple. Dans un vrai cas de test, le jury n’affichera pas ces lignes placeholders, et le participant ne doit ni les lire ni les afficher.

Dans cet exemple d’interaction, la permutation cachée est $p=(3,1,4,2)$. Les puces ci-dessous décrivent l’interaction montrée dans l’exemple.

• Le juge envoie d’abord $n=4$ et la limite de requêtes $5$.
• La première requête ? 1 reçoit = car il n’y a pas d’indice précédent interrogé.
• La requête ? 2 compare $p_1=3$ avec $p_2=1$, donc le juge répond >.
• La requête ? 4 compare $p_2=1$ avec $p_4=2$, donc le juge répond <. Le minimum est à l’indice $2$, donc ! 2 est correct.

Outil d’interaction local : Le fichier attachments/local_interactive.py joint peut reproduire ce cadre local avec --perm 3,1,4,2 --limit 5, mais le réussir ne garantit pas de réussir les données de test officielles.