Dîner mondain – Regional event 2011

Level 7

Énoncé

S'il y a quelque chose que Joseph Marchand déteste, ce sont bien les dîners mondains. Pour s'occuper, il se livre donc à un petit jeu avec ses amis. Tous les participants se retrouvent alors autour d'une table, chacun ayant son verre en face de lui. À chaque moment, un joueur peut prendre 2 verres non vides équidistants du sien (c'est-à-dire, n - k et n + k s'il s'agit du joueur n) et verser 1 cL de l'un, et 1 cL de l'autre dans son verre ; inversement, si un joueur a un verre d'au moins 2 cL, il peut choisir 2 verres équidistants du sien et verser 1 cL de son verre dans chacun d'eux.

Au bout d'un certain temps, il se trouve que seul un verre est rempli : celui du gagnant. Là, le vainqueur peut choisir de continuer la partie ou de l'arrêter.

On vous donne le nombre de joueurs N et les capacités en cL des N verres, le premier verre appartenant à Joseph. Écrivez une fonction qui retourne 1 si c'est forcément Joseph qui gagne, 2 si ça peut être Joseph comme quelqu'un d'autre et 0 si Joseph ne peut pas gagner.

Entrée

  • Sur la première ligne, l'entier N correspondant au nombre de joueurs.
  • Sur la deuxième ligne, N entiers représentant les capacités C1, ..., CN des verres, en cL. Le premier verre est celui de Joseph.

Sortie

Vous devez retourner :

  • 1 si Joseph est le seul à pouvoir gagner.
  • 2 si Joseph peut gagner mais que c'est aussi le cas d'autres joueurs.
  • 0 si Joseph ne peut pas gagner.

Contraintes

  • 1 <= N <= 1 000 000
  • 0 <= Ci <= 100

Runtime constraints

Maximum memory usage
40960 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Submit your solution

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