Le jury a choisi un entier $x$ dans l'intervalle $[1, n]$. Votre tâche est de le deviner. Afin de ne pas avoir à le faire complètement à l'aveugle, vous pouvez poser des questions. Dans chaque question, vous pouvez fournir un entier $y$ dans l'intervalle $[0, c]$, et nous vous révélerons en réponse le nombre de diviseurs de $x + y$.

Pour rendre la tâche un peu plus difficile, vous devrez résoudre $t$ cas de test lors d'une seule exécution du programme. Le nombre total de questions que vous pouvez poser est limité par $q$.

Interaction

Il s'agit d'un problème interactif. Vous devez écrire un programme qui communique avec le jury en utilisant la bibliothèque fournie. Pour utiliser la bibliothèque, vous devez inclure dans votre programme :

• C++ : #include "dzilib.h"
• Python : from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer

La bibliothèque fournit les fonctions suivantes :

• GetT() – Renvoie le paramètre $t$ – le nombre de cas de test à résoudre.
• GetN() – Renvoie le paramètre $n$ – la limite sur les valeurs cachées $x$.
• GetQ() – Renvoie le paramètre $q$ – la limite sur le nombre total de questions que vous pouvez poser pour l'ensemble des $t$ cas de test.
• GetC() – Renvoie le paramètre $c$ – la limite sur les valeurs $y$ que vous pouvez fournir.
• Ask(y) – Renvoie le nombre de diviseurs positifs de la valeur cachée $x$ augmentée de $y$. La condition $0 \le y \le c$ doit être respectée.
• Answer(z) – Informe la bibliothèque que, selon vous, la valeur cachée $x$ est égale à $z$. Cette fonction ne renvoie rien (en C++, le type de retour est void).

En Python, tous les paramètres des fonctions de la bibliothèque ainsi que les valeurs renvoyées sont des entiers. En C++, les types acceptés et renvoyés par les fonctions sont identiques à ceux de la bibliothèque fournie en exemple, dont il est question dans la section Eksperymenty.

À tout moment de l'exécution du programme (sauf à la toute fin), un seul cas de test sera actif. Le premier cas de test est activé immédiatement après le démarrage du programme. Lorsqu'un cas de test est actif, vous pouvez poser des questions en utilisant la fonction Ask. Lorsque vous pensez connaître la valeur cachée $x$, vous pouvez la soumettre via la fonction Answer, et la bibliothèque la vérifiera. Si la valeur fournie est incorrecte, la bibliothèque terminera l'exécution du programme avec le verdict « réponse incorrecte ». Si la valeur est correcte, la fonction se terminera ; si le cas de test résolu n'était pas le dernier, le suivant sera immédiatement activé. Après avoir répondu au dernier cas de test, vous devez terminer l'exécution de votre programme. Si vous ne le faites pas et que vous tentez d'utiliser les fonctions Ask ou Answer, vous recevrez le verdict « réponse incorrecte ».

Les fonctions GetT, GetN, GetQ et GetC peuvent être utilisées à tout moment de l'exécution du programme et les valeurs qu'elles renvoient ne changeront pas. Ces fonctions ne sont pas comptabilisées dans la limite de questions, mais consomment du temps processeur. La valeur $q$ limite uniquement le nombre d'appels à la fonction Ask. Au moment où vous dépassez le nombre total de questions autorisées, la bibliothèque terminera l'exécution du programme et vous recevrez le verdict « réponse incorrecte ».

Vous ne devez lire aucune donnée depuis l'entrée standard ni écrire quoi que ce soit sur la sortie standard. Les tentatives délibérées d'influencer le fonctionnement interne de la bibliothèque d'évaluation sont interdites.

Bibliothèques

Les valeurs cachées $x$ dans tous les tests ainsi que leur ordre sont déterminés à l'avance. Cela signifie que la bibliothèque avec laquelle votre programme communique ne sera pas malveillante et n'adaptera pas son comportement aux actions de votre programme.

Les limites indiquées dans l'énoncé concernent uniquement le temps et la mémoire consommés par votre programme. Le temps d'exécution de la bibliothèque et la mémoire qu'elle utilise peuvent cependant dépendre du test et du comportement exact de votre programme. Pour cette raison, les limites de temps et de mémoire sur SIO2 sont légèrement supérieures à celles indiquées dans l'énoncé.

Exemples

Entrée 1

2
1000000
10000
1000000000000000
1000
1

Sortie 1

GetT() -> 2
GetN() -> 1000000
GetQ() -> 10000
GetC() -> 1000000000000000
Ask(1) -> 8
Ask(24) -> 11
Answer(1000)
GetT() -> 2
Answer(1)

Remarque

Dans l'exemple ci-dessus, $t = 2$, $n = 10^6$, $q = 10^4$, $c = 10^{15}$, les valeurs cachées sont successivement $1000$ et $1$. Deux questions Ask ont été posées, ce qui est bien en dessous de la limite de $10\,000$ questions. N'oubliez pas que c'est le nombre total de questions pour tous les cas de test d'un même test qui est comptabilisé.

Sous-tâches

Au sein d'un groupe de tests, tous les tests ont les mêmes valeurs $t$, $n$, $q$ et $c$, présentées dans le tableau suivant :

Le test d'exemple n'appartient à aucun groupe. Vous pouvez le résoudre, mais notez qu'il est possible d'obtenir le score complet sans le résoudre.

Eksperymenty

Des exemples de solutions incorrectes et des bibliothèques exemples en C++ et Python se trouvent dans les archives de la section Pliki sur SIO2. Ces solutions et bibliothèques illustrent les types renvoyés et acceptés par toutes les fonctions. Les bibliothèques exemples peuvent différer dans leur comportement de celle qui sera utilisée pour l'évaluation des solutions et peuvent ne pas respecter toutes les hypothèses du problème. Elles ne servent qu'à montrer le mode d'interaction avec le programme.

La solution dzi.cpp en C++ peut être compilée comme suit :

g++ -O3 -static -o dzi dzi.cpp dzilib.cpp -std=c++20

Vous devez vous assurer que les fichiers dzilib.h et dzilib.cpp se trouvent dans le même dossier que votre solution.

La solution dzi.py peut être exécutée avec la commande :

python dzi.py

Vous devez vous assurer que le fichier dzilib.py se trouve dans le même dossier que votre solution.

Après le lancement, au tout début de l'exécution du programme, la bibliothèque lit sur l'entrée standard les valeurs $t$, $n$, $q$ et $c$, puis les valeurs cachées successives $x$. Le fichier d'entrée correspondant au test d'exemple se trouve dans les deux archives sous le nom dzi0.in.