Takina et Chisato sont à une convention de fruits. Après une journée passée à prendre des photos avec leurs cosplayers de fruits préférés, elles tombent sur un stand de jeu.
Les règles du jeu sont les suivantes : Il y a $n$ fruits, chacun avec une étiquette distincte de $1$ à $n$. Exactement l'un des fruits est un citron, mais ni Takina ni Chisato ne savent encore lequel c'est. * Takina recevra tous les $n$ fruits un par un. Son but est de communiquer l'étiquette du citron à Chisato (qui a les yeux bandés pendant ce processus).
Avant de recevoir les fruits, Takina reçoit un tableau $p$, qui représente l'ordre dans lequel les étiquettes des fruits apparaîtront. $p[1]$ sera l'étiquette du premier fruit, $p[2]$ sera l'étiquette du second fruit, et ainsi de suite. Ensuite, Takina écrira une chaîne binaire $b$ contenant uniquement des $0$ et des $1$. La chaîne ne doit pas dépasser $5000$ caractères, mais elle peut être vide. Soit $x$ la longueur de $b$.
Ensuite, les fruits sont donnés à Takina un par un dans l'ordre susmentionné. À la réception de chaque fruit, Takina est informée s'il s'agit du citron. Si le fruit n'est pas le citron, Takina peut choisir de le manger ou non. Cette décision doit être prise avant de recevoir le fruit suivant et ne peut être modifiée. Si le fruit est le citron, Takina ne doit pas le manger.
Soit $y$ le nombre total de fruits mangés par Takina.
Enfin, Chisato reçoit la chaîne $b$ et la liste triée des étiquettes des fruits qui n'ont pas été mangés. En utilisant ces informations, Chisato doit déterminer l'étiquette du fruit qui est le citron.
Takina et Chisato ont décidé de jouer à ce jeu $t$ fois. Concevez une stratégie pour qu'elles identifient correctement le citron tout en minimisant à la fois $x$ et $y$.
Détails d'implémentation
Ceci est une tâche de communication. Ne lisez pas depuis l'entrée standard et n'écrivez pas sur la sortie standard.
Vous devez implémenter trois procédures.
Pour Takina, vous devez implémenter :
std::string init(int subtask, int n, std::vector<int> p)subtask: l'indice de la sous-tâche à laquelle appartient le cas de test.n: le nombre de fruits.p: un tableau de longueur $n + 1$ où :- $p[0] = 0$, et
- pour chaque $1 \le i \le n$, $p[i]$ est l'étiquette du $i$-ème fruit qui sera donné à Takina.
- Cette procédure est appelée $t$ fois par cas de test, une fois au début de chaque partie.
Cette procédure doit retourner la chaîne $b$, d'une longueur comprise entre $0$ et $5000$ inclus, composée uniquement de $0$ et de $1$. Si une chaîne de longueur ou de format invalide est retournée, vous recevrez un verdict de Wrong Answer.
bool receive_fruit(int id, bool is_lemon)id: l'étiquette du fruit donné à Takina.is_lemon:truesi le fruit donné est le citron,falsesinon.- Cette procédure est appelée $n$ fois pour chacune des $t$ parties, une fois pour chaque fruit.
Cette procédure doit retourner true si le fruit doit être mangé, et false sinon. Si true est retourné alors que is_lemon est true, vous recevrez un verdict de Wrong Answer.
Pour Chisato, vous devez implémenter :
int answer(int subtask, int n, std::string b, std::vector<int> uneaten)subtask: l'indice de la sous-tâche à laquelle appartient le cas de test.n: le nombre de fruits.b: la chaîne retournée parinit.uneaten: le vecteur trié de longueur $n - y + 1$ des étiquettes des fruits non mangés par Takina, où :uneaten[0] = 0, etuneaten[i]est la $i$-ème plus petite étiquette parmi les fruits non mangés.
- Cette procédure est appelée $t$ fois par cas de test, une fois à la fin de chaque partie.
Cette procédure doit retourner un entier, l'étiquette du citron. Si la valeur retournée ne correspond pas à l'étiquette correcte, vous recevrez un verdict de Wrong Answer.
Lors de l'évaluation réelle, un programme qui appelle les procédures ci-dessus est exécuté deux fois :
- Lors de la première exécution, les étapes suivantes sont effectuées $t$ fois :
initest appelée une fois.receive_fruitest appelée $n$ fois, en suivant l'ordre des fruits donnés à Takina.- Votre programme peut stocker et conserver des informations entre les appels successifs.
- Lors de la seconde exécution, l'ordre des parties peut être différent de la première exécution. Pour chacune des $t$ parties :
answerest appelée une fois. En dehors des paramètres passés àanswer, votre programme ne peut pas accéder aux informations de la première exécution.
Remarque
Comme la procédure peut être appelée plus d'une fois, vous devez faire attention à l'effet des données restantes de l'appel précédent sur l'appel actuel.
Sous-tâches
Pour tous les cas de test, l'entrée satisfera les bornes suivantes : $1 \le t \le 10\,000$ $n = 500$ $1 \le p[i] \le n$ pour tout $1 \le i \le n$ Il y a exactement un citron.
Pour chaque sous-tâche, votre programme sera noté différemment en fonction de la longueur de la chaîne écrite par Takina, $x$, et du nombre de fruits qu'elle mange, $y$. Votre score pour chaque cas de test est calculé en utilisant la valeur maximale de $x$ sur toutes les $t$ parties et la valeur maximale de $y$ sur toutes les $t$ parties.
| Sous-tâche | Score |
|---|---|
| 1 | Si $y > 2$, votre score est 0. Sinon, votre score est $10 \times \min \left( \frac{288}{x}, 1 \right)$. |
| 2 | Si $y > 9$, votre score est 0. Sinon, votre score est $30 \times \min \left( \frac{30}{x}, 1 \right)$. |
| 3 | Votre score est $60 \times \min \left( \frac{20}{x+y}, 1 \right)$. |
Exemples
Entrée 1
1 4 0 3 1 4 2
Sortie 1
4
Remarque
Dans cet exemple, Takina mange les fruits avec les étiquettes 3 et 2, donc les fruits non mangés sont $\{1, 4\}$. Le vecteur uneaten passé à answer est donc [0, 1, 4]. En utilisant b et uneaten, la procédure answer retourne 4, qui est l'étiquette du citron. Cette stratégie a permis d'identifier correctement le citron avec $x = 3$ et $y = 2$.
Testing
Vous pouvez télécharger le correcteur local (grader.cpp), le fichier d'en-tête (lemon.h) et un modèle de solution (lemon.cpp) dans les pièces jointes. Deux fichiers d'entrée sont fournis pour vos tests, sample1.txt et sample2.txt. Vous pouvez utiliser les scripts compile.sh pour compiler et run.sh pour exécuter votre solution pour les tests.
Les tests utilisateurs CMS ne sont pas pris en charge pour ce problème.
Sample Grader
Un correcteur local est fourni pour vous aider à tester votre implémentation localement. Contrairement au correcteur officiel, le correcteur local exécute votre programme une seule fois et ne modifie pas l'ordre des tests pour Takina et Chisato.
Input Format
La première ligne de l'entrée contient un entier subtask.
La deuxième ligne de l'entrée contient un entier t.
Les $t$ lignes suivantes décrivent chacune une partie. Chaque partie est décrite par :
une ligne contenant deux entiers séparés par un espace $n$ et $l$, représentant le nombre de fruits et l'étiquette du citron, et
une ligne contenant $n$ entiers séparés par un espace $p[1], p[2], \dots, p[n]$.
Output Format
Le correcteur local affiche un nombre réel unique représentant la fraction de score calculée à partir des valeurs de $x$ et $y$ sur toutes les parties.
Note
Des messages de diagnostic supplémentaires peuvent être imprimés sur la sortie d'erreur standard. Le correcteur local ne simule pas le comportement du correcteur officiel.