Phi-Bonacci – Regional event 2023

Level 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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
3 1 2
Sample output
5 3
Note

$[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é.
Sample input
1
42
Sample output
42
Note

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

Sample input
4
1 1 2 3
Sample output
6 9
Note

$[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]$
Sample input
3
1 1000000000 9
Sample output
10 2
Note

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]$.

Submit your solution

You have to register or log in to be able to submit your solution.