Dîner mondain – Épreuve régionale 2011

É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 C₁, ..., C_N 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 <= C_i <= 100