Composition de crêpes – Regional event 2018

Level 6

Énoncé

Joseph Marchand a un excellent ami mathématicien qui est aussi, par le plus grand des hasards, un véritable fou furieux des crêpes. Ce dernier possède des goûts bien spécifiques et a attribué à chaque ingrédient du magasin de Joseph un degré de satisfaction $S_i$. Ce client un peu particulier adore composer ses propres crêpes en fonction de ces différents indices, et a même inventé un jeu pour se distraire dans la queue ! Le but est simple : trouver un ensemble d'ingrédients tels que la somme de leurs degrés de satisfaction soit exactement égale à un nombre $X$ préalablement fixé. Chaque ingrédient peut être ignoré ou utilisé une seule fois, et le mathématicien gagne s'il parvient à trouver cet ensemble avant de passer sa commande.

Joseph trouve que le jeu est trop facile, et veut rendre la tâche du mathématicien davantage complexe. Cependant, Joseph n'y connaît pas grand-chose en mathématiques et décide donc de simplement rajouter plus d'ingrédients, augmentant alors le nombre de possibilités !

L'ami de Joseph a besoin de votre aide afin de déterminer s'il existe ou non, un ensemble d'ingrédients (en ne réutilisant jamais deux fois un ingrédient) tel que la somme de leurs degrés soit exactement égale à $X$.

Entrée

Sur la première ligne deux entiers $N$ et $X$, $N$ représentant le nombre d'ingrédients dans le magasin et $X$ le nombre fixé par le mathématicien avant d'entrer.

$N$ entiers suivent sur la deuxième ligne indiquant pour chacun le degré de satisfaction $S_i$ associé à l'ingrédient $i$.

Sortie

Vous devez afficher sur la sortie "GAGNE" s'il est possible de former un tel ensemble ou "IMPOSSIBLE" dans le cas contraire.

Contraintes

  • $1 \le N \le 40$
  • $1 \le X \le 10^{16}$
  • $1 \le S_i \le X$

Note

Attention à utiliser des types de variables adaptés pour gérer les grands entiers !

Runtime constraints

Maximum memory usage
128000 kilobytes
Maximum execution time
3000 milliseconds

Input/output samples

Sample input
5 42
7 17 22 13 3
Sample output
GAGNE
Note

On peut utiliser les ingrédients de degrés 17, 22 et 3 puisque 17 + 22 + 3 = 42.

Sample input
4 31
5 16 4 9
Sample output
IMPOSSIBLE
Note

Il est impossible de trouver un sous-ensemble d'ingrédients tels que la somme de ses éléments soit égal à 31 dans ces conditions.

Submit your solution

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