Universal Cup Judging System

Universal Cup

时间限制: 2.0 s 内存限制: 1024 MB 总分: 100 可 Hack ✓
统计

On vous donne un tableau de $n$ entiers compris entre $1$ et $n+1$. Il est possible que certains entiers apparaissent plusieurs fois dans le tableau. Néanmoins, il est clair qu'au moins un des entiers de $1$ à $n+1$ est absent du tableau. Votre tâche consiste à trouver l'un quelconque de ces entiers manquants. Normalement, ce serait facile, mais il y a un problème fâcheux : votre ordinateur ne dispose pas d'assez de mémoire pour représenter le tableau entier.

Il vous est donc demandé de produire à la place un algorithme de flux (streaming algorithm). De manière informelle, les éléments du tableau vous sont donnés un par un sans aucun moyen d'y accéder aléatoirement. Il y a toutefois une consolation : après avoir reçu le dernier élément du tableau, vous pouvez recommencer sa lecture depuis le début. Idéalement, vous aimeriez éviter une telle situation et résoudre l'ensemble du problème en une seule passe. Cependant, parfois (y compris dans ce problème même), plusieurs passes sur l'entrée peuvent s'avérer nécessaires pour éviter d'utiliser trop de mémoire. Vous devez équilibrer ces deux contraintes et simultanément ne pas utiliser trop de mémoire et ne pas effectuer trop de passes sur le tableau (le problème est trivial si vous êtes autorisé à stocker $n$ bits de mémoire ou à utiliser $n$ passes).

Il reste cependant une subtilité. Pour des raisons techniques, vous devez produire un automate fini déterministe (DFA) sur l'alphabet $\{0, 1, \dots, n + 1\}$ implémentant la logique de votre algorithme. Les caractères de l'alphabet correspondent aux informations que vous recevez lors de la lecture du flux : les nombres de $1$ à $n+1$ représentent la lecture de l'entier correspondant dans le tableau, tandis que le nombre $0$ représente le fait que vous avez atteint la fin du tableau. Après les 7 premières fois où vous avez atteint la fin du tableau, celui-ci vous sera redonné dans le même ordre qu'auparavant, en se terminant toujours par un caractère $0$ représentant la fin du tableau. Ainsi, votre DFA recevra la chaîne $a_1, a_2, \dots, a_n, 0$ un total de 8 fois (ici, $a_1, a_2, \dots, a_n$ est le tableau caché). Enfin, à tout moment de l'exécution, votre automate peut « déclarer » qu'il connaît déjà une réponse correcte au problème ; dans ce cas, l'exécution s'arrête. Si votre DFA ne l'a pas fait au moment où il a lu l'intégralité du flux (y compris le caractère $0$ à la fin) 8 fois, il n'est pas accepté comme solution. De même, s'il s'arrête mais avec une réponse incorrecte, il n'est pas accepté non plus.

Énonçons le problème formellement. Il existe un tableau caché $a_1, a_2, \dots, a_n$ de $n$ entiers compris entre $1$ et $n+1$. Dans l'exemple, $n = 4$, et dans tous les autres tests, $n = 250$. Vous devez spécifier une machine à états finis comportant au plus 4000 états, numérotés de $0$ à $q - 1$, où $q \le 4000$ est le nombre d'états. Pour l'état $i$ ($0 \le i \le q - 1$), vous devez spécifier $n + 2$ nombres $\delta(i, 0), \delta(i, 1), \dots, \delta(i, n + 1)$. Le nombre $\delta(i, j)$ représente le comportement de votre DFA lorsqu'il se trouve dans l'état $i$ et lit le nombre $j$ depuis l'entrée. Ce doit être un entier compris entre $-(n + 1)$ et $q - 1$ inclus. Les entiers négatifs correspondent au fait que l'exécution s'arrête et qu'une réponse est donnée ; plus précisément, $-s$ correspond au fait que votre DFA affirme que $+s$ est une réponse correcte au problème. Les entiers naturels (positifs ou nuls) correspondent au fait que l'exécution se poursuit et que l'état de l'automate passe de $i$ à $\delta(i, j)$. L'exécution de l'automate commence dans l'état $0$.

Votre DFA est considéré comme fonctionnant correctement sur le tableau $a_1, a_2, \dots, a_n$ s'il s'arrête avec une réponse correcte à un certain moment de la lecture de la chaîne $a_1, a_2, \dots, a_n, 0, a_1, a_2, \dots, a_n, 0, \dots, a_1, a_2, \dots, a_n, 0$, où le tableau est répété 8 fois. Votre DFA est considéré comme fonctionnant correctement en général s'il fonctionne correctement sur tous les tableaux possibles $a_1, a_2, \dots, a_n$ d'entiers de $1$ à $n+1$ (par conséquent, les solutions probabilistes sont déconseillées).

Pour $n = 4$, nous vérifierons votre DFA sur tous les tableaux possibles. Pour $n = 250$, nous n'avons pas les moyens de le vérifier sur tous les tableaux, nous le vérifierons donc sur moins de 5000 tableaux spécialement sélectionnés. Il y a deux tests dans ce problème ; les deux tests vérifient concrètement que votre approche fonctionne correctement sur de nombreux tableaux simultanément.

Entrée

Un entier $n$, qui est égal soit à $4$, soit à $250$.

Sortie

Sur la première ligne, affichez un seul entier $q$ ($1 \le q \le 4000$) désignant le nombre d'états de votre DFA.

Sur la $i$-ème des $q$ lignes suivantes, affichez $n + 2$ entiers $\delta(i - 1, 0), \delta(i - 1, 1), \dots, \delta(i - 1, n + 1)$. Ils doivent tous être compris entre $-(n + 1)$ et $q - 1$ inclus et correspondre aux transitions de l'automate. Notez que tous les nombres doivent appartenir à cet intervalle : même si une certaine combinaison de l'état $i$ et du nombre d'entrée $j$ ne peut jamais être atteinte sur aucune entrée valide, la valeur de $\delta(i, j)$ que vous spécifiez doit tout de même se situer dans l'intervalle $[-(n + 1), q - 1]$.

Exemple

Entrée 1

4

Sortie 1

8
-3 0 0 1 0 0
2 1 1 1 1 1
-1 3 2 2 2 2
4 3 3 3 3 3
-5 4 4 4 4 5
6 5 5 5 5 5
-2 6 7 6 6 6
-4 7 7 7 7 7

Note

La réponse pour l'exemple est un automate très ennuyeux qui utilise quatre passes pour vérifier si le tableau contient les nombres 3, 1, 5 et 2 (dans cet ordre). Chacune des passes n'utilise concrètement que deux états qui correspondent au fait d'avoir déjà trouvé ou non le nombre recherché au cours de la passe actuelle. S'il atteint la fin du tableau (le caractère 0) sans avoir trouvé le nombre nécessaire, il s'arrête immédiatement en déclarant que ce nombre est effectivement manquant. Sinon, il passe à la passe suivante pour chercher le nombre suivant. Enfin, s'il a trouvé les quatre entiers nécessaires, alors le nombre 4 est forcément manquant. Il n'effectue donc pas de cinquième passe pour chercher le nombre 4 (mais il aurait pu le faire sans enfreindre les restrictions sur le nombre d'états de l'automate et le nombre de passes utilisées).

Bien entendu, cette approche naïve n'a aucune chance de fonctionner pour $n = 250$, et il faut trouver bien mieux. La raison principale de l'existence de cet exemple est d'illustrer le format de sortie.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1213EditorialOpen题解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.