Divination – Regional event 2010

Level 3

ÉNONCÉ

A partir d'une suite de nombres donnée en entrée, on se propose de deviner le nombre qui suit. Pour simplifier le problème, on suppose que l'on passe d'un terme au suivant en appliquant à chaque fois une même opération de base : ajouter une constante ou multiplier par une constante entière. Dans certains cas plus complexes, deux opérations sont alternées : par exemple, ajouter un, puis multiplier par deux, puis ajouter un, etc.

Tous les nombres de la suite sont des entiers. Les suites sont toujours valides et possèdent au moins 5 nombres.

Par exemple, pour passer de 6 à 3, il existe deux possibilités : soit on a divisé par 2, soit on a retranché 3. En revanche, pour passer de 7 à 3, il n'y a qu'une seule solution, il a fallu soustraire 4, car la division n'est pas possible.

ENTRÉE

  • N, la longueur, suivi des n premiers nombres de la suite.

LIMITES

  • 4 < N <= 100.
  • Tous les nombres en entrée ou en sortie seront compris entre -1000 et 1000.

SORTIE

  • Le terme suivant de la suite, le (n+1)ième.

Runtime constraints

Maximum memory usage
30 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
5
1 2 3 4 5
Sample output
6
Sample input
6
2 4 3 6 5 10
Sample output
9
Sample input
5
1 -2 4 -8 16
Sample output
-32

Submit your solution

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