Phi-Bonacci – Épreuve régionale 2023

Niveau 3

Enoncé

Avec les informations tout juste récupérées, Valérian commence à se poser des questions sur l'encodage des nombres qu'Oscar lui indiquait, avant de se rendre compte qu'Oscar lisait le manuel d'instructions de sa machine à laver ! (Qui bien sûr ne suit pas le même système d'encodage pour la température que notre machine pour l'année...). Personne ne se souvenant du système d'encodage exact, les jeunes vont désespérément tenter de retourner au présent pour récupérer le manuel d'instructions... Même sans connaître l'encodage, ils savent que grâce au mode relatif, ils ne peuvent qu'avancer dans le temps. Alors Valérian décide de faire une combinaison aléatoire pour voir où ça les mène.

Les jeunes sortent alors de leur machine à voyager dans le temps et tombent nez à nez avec ce qui semble être un mathématicien Italien des années 1000. Curieux de l'étrange machine par laquelle nos aventurier viennent de s'extirper, le mathématicien leur offre sa dernière invention, en échange de pouvoir étudier quelques temps leur impressionnante machine.

Cependant, le cadeau du mathématicien, une petite machine sous la forme d'une grande liste X d'entiers, est tout de même trop grand pour pouvoir rentrer dans la machine temporelle !

Heureusement pour nos explorateurs, le mathématicien connaît une opération permettant de modifier la machine sans pour autant la casser :

  1. Choisir un indice $i$
  2. Décrementer $X_{i+2}$
  3. Incrémenter $X_{i+1}$
  4. Incrémenter $X_i$

Pour réduire la taille de la machine, le mathématicien vous indique qu'il est possible d'effectuer cette opération sur la machine autant de fois que souhaité, et qu'il est également toujours possible de supprimer le dernier élément de la liste s'il s'agit d'un 0.

Aidez les jeunes à trouver la forme la plus compacte possible de la machine sans la casser !

Les valeurs présentes dans cette forme pouvant être grandes, il est demandé de les afficher modulo $1\,000\,000\,007$.

Par exemple, la liste $[1\,000\,000\,009, 42]$ sera affichée $[2, 42]$ car $1\,000\,000\,009$ mod $1\,000\,000\,007 = 2$ et $42$ mod $1\,000\,000\,007 = 42$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, la taille initiale de la machine.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : X, la machine à compacter.

Sortie

Vous devez afficher la version la plus courte de la machine sans la casser : un certain nombre d'entiers, sur une ligne, séparés par un espace. Pour rappel, les valeurs sont à afficher modulo $1\,000\,000\,007$.

Contraintes

  • $1 \le N \le 6$
  • $0 \le X_i \le 100$ pour tout $i$
  • $X_i > 0$ pour au moins un $i$

Contraintes de performance

  • $1 \le N \le 100\,000$
  • $0 \le X_i \le 1\,000\,000\,000$ pour tout $i$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
3 1 2
Exemple de sortie
5 3
Commentaire

$[3, 1, 2]$ se simplifie en $[5, 3]$ avec ces opérations :

  • $[4, 2, 1]$ : Première opération avec $i = 0$, les valeurs 3 et 1 sont incrémentées et la valeur 2 décrémentée.
  • $[5, 3, 0]$ : La même opération est réalisée une deuxième fois.
  • $[5, 3]$ : Le 0 en fin de liste est enlevé.
Exemple d'entrée
1
42
Exemple de sortie
42
Commentaire

Cette liste est déjà la plus simplifiée.

Exemple d'entrée
4
1 1 2 3
Exemple de sortie
6 9
Commentaire

$[1, 1, 2, 3]$ se simplifie en $[6, 9]$ après ces étapes :

  1. $[1, 1, 2, 3]$
  2. $[1, 2, 3, 2]$
  3. $[1, 3, 4, 1]$
  4. $[1, 4, 5, 0]$
  5. $[2, 5, 4, 0]$
  6. $[3, 6, 3, 0]$
  7. $[4, 7, 2, 0]$
  8. $[5, 8, 1, 0]$
  9. $[6, 9, 0, 0]$
  10. $[6, 9]$
Exemple d'entrée
3
1 1000000000 9
Exemple de sortie
10 2
Commentaire

Attention : Ce test ne sera jugé que dans les tests de performance.

Il est nécessaire d'afficher les valeurs en utilisant la notation modulo.

$[1, 1\,000\,000\,000, 9]$ se simplifie avec ces opérations :

  1. $[2, 1\,000\,000\,001, 8]$
  2. $[3, 1\,000\,000\,002, 7]$
  3. ...
  4. $[10, 1\,000\,000\,009, 0]$
  5. $[10, 1\,000\,000\,009]$

Nous avons $1\,000\,000\,009$ mod $1\,000\,000\,007 = 2$ donc la liste à afficher est $[10, 2]$.