Prologin
2023
É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 !