Prologin
2024
Énoncé¶
$N$ dieux veulent se répartir le contrôle des villes parmi $V$ villes
existantes.
Les dieux sont numérotés de $0$ à $N-1$, et les villes de $0$ à $V-1$.
Chaque dieu possède une certaine affection pour chaque ville, indiquée dans
un tableau $\mathtt{villes}$.
Pour chaque dieu, il vous est donné une chaîne binaire de taille $V$: le
caractère en position $i$ vaut 1 si le dieu veut contrôler la ville $i$,
et 0 sinon.
Lorsque certaines villes parmi les $V$ villes sont abandonnées, alors deux dieux vont tenter de se répartir équitablement leur contrôle. Cependant, il peut y avoir des villes dites contestées dont les deux dieux veulent le contrôle. Si le nombre de villes contestées est pair, alors pas de problème, les dieux peuvent se les répartir équitablement. Mais si ce nombre est impair, ils se battront inévitablement.
Alors, pour un certain sous-ensemble de villes abandonnées, on dit que deux dieux sont compatibles si le nombre de villes contestées par les deux dieux dans ce sous-ensemble est pair.
Étant donné un sous-ensemble $S$ de villes dites abandonnées, et un entier $\Delta$, on appelle alors $R(S, \Delta)$ le nombre de $X$ tels que les dieux $X$ et $X \oplus \Delta$ sont compatibles, où $\oplus$ représente l'opération "ou exclusif" au niveau du bit.
Afin d'évaluer l'animosité générale chez les dieux, Jøsëf Marchand doit alors
répondre à $R$ requêtes.
Chaque requête prend la forme d'un sous-ensemble de villes $S$, auquel Jøsëf
Marchand devra répondre en appelant la fonction Hashe avec, consécutivement,
toutes les valeurs de $R(S, \Delta)$ pour toutes les valeurs possibles de
$\Delta$ entre 1 et $N-1$.
La fonction Hashe est donnée en pseudo-code ci-dessous :
1 2 3 4 5 | Hashe(valeur) {
X = (X * valeur + Z + 37) % 1000 000 007;
Y = (X * 13 + 36 * Y + 257) % 1000 000 009;
Z = (Y * valeur + 4 * valeur + X * X + 7) % 998 244 353;
}
|
Faites attention aux dépassements entier !
En C++ par exemple, il faut utiliser un type d'entier 64 bits, tel que
long long.
Les valeurs de X, Y et Z sont initialisées à 0 au début de l'exercice
et ne sont jamais réinitialisées.
Après chaque requête, Jøsëf Marchand doit afficher les nouvelles valeurs
de X, Y et Z.
Aidez Jøsëf Marchand à répondre à toutes ces requêtes.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : V, le nombre de villes.
- Sur la ligne suivante, un entier : N, le nombre de dieux.
- Sur les lignes suivantes, une liste de N éléments : villes, pour
chaque dieu, une chaîne de caractère binaire. Si le dieu veut le contrôle de
la ville $i$, un
1est présent dans la chaîne de caractère à la position $i$, un0sinon.- Une ligne par élément de la liste : une liste de V caractères juxtaposés.
- Sur la ligne suivante, un entier : R, le nombre de requêtes.
- Sur les lignes suivantes, une liste de R éléments : requetes, pour
chaque requête, une chaîne de caractère binaire représentant un sous-ensemble
de villes. Si la ville $i$ est présente dans le sous-ensemble, alors un
1est présent dans la chaîne de caractère à la position $i$, un0sinon.- Une ligne par élément de la liste : une liste de V caractères juxtaposés.
Sortie¶
Initialisez X, Y et Z à 0.
Pour chaque requête $S$ : appelez la fonction Hashe avec toutes les valeurs
de $R(S, \Delta)$, pour toutes les valeurs de $\Delta$ entre $1$ et $N - 1$,
puis affichez, sur une ligne et séparés par un espace, les nouvelles valeurs
de X, Y et Z.
Contraintes¶
- $1 \le V \le 5$
- $2 \le N \le 16$
- $1 \le R \le 16$
- $N$ est toujours une puissance de deux
Contraintes de performance¶
- $1 \le V \le 13$
- $2 \le N \le 8\,192$
- $1 \le R \le 8\,192$
- $N$ est toujours une puissance de deux