Prologin
2024
Énoncé¶
À l'issue de la finale, nous remplissons la cour de l'EPITA de mousse, de manière à relaxer nos candidats.
Pour cela, nous disposons de N bidons de volumes distincts triés dans l'ordre décroissant que nous pouvons remplir à loisir, et procédons de la manière suivante : nous remplissons la cour avec le premier bidon autant de fois qu'il est possible de le déverser intégralement sans dépasser le volume souhaité, auquel cas nous passons au deuxième, et ainsi de suite. Comme le dernier bidon a toujours une capacité d'un litre, nous pouvons réaliser tous les volumes possibles.
Si vous parvenez à trouver un volume de mousse pour lequel vous serez à même de remplir la cour avec nos bidons en effectuant moins de versements que nous, vous gagnez. Sinon, vous perdez.
On vous donne les volumes des bidons, écrivez une fonction qui retourne 1 si vous pouvez gagner, 0 sinon.
Contraintes¶
- 1 <= N <= 500 est le nombre de bidons.
- 1 <= Ci <= 1 000 000 000 est leur capacité.
Entrée¶
L'entrée standard contient :
- un entier N représentant le nombre de bidons ;
- la liste des N volumes des bidons. Ils sont rangés dans l'ordre décroissant, et le dernier a pour capacité 1 L.
Sortie¶
Vous devez écrire une ligne sur la sortie standard : 1 si vous pouvez gagner au jeu, 0 sinon.