Le compte est presque bon – Regional event 2018

Énoncé¶

Pendant ses pauses, Joseph Marchand aime bien contempler l'activité de son magasin, et il a même inventé un jeu pour se divertir. Pour cela, il choisit un nombre arbitraire $T$, puis observe attentivement chaque table et note le nombre de clients qui y sont assis. À l'aide de ces différents nombres, Joseph tente de les additionner ou de les soustraire pour obtenir au final le nombre $T$ qu'il a fixé avant de jouer. Un nombre peut être utilisé plusieurs fois, ou encore ne jamais être pris en compte lors du calcul. La tâche étant parfois difficile, Joseph s'autorise une marge d'erreur de $X$ unités, c'est-à-dire que si le total prévu est de 10 et la marge de 2 unités, alors 8, 9, 10, 11, et 12 sont tous des résultats valides. De plus, Joseph ne veut pas prendre une pause trop longue et décide de ne pas utiliser plus de $K$ opérations (+ ou -).

Après avoir joué plusieurs fois aujourd'hui, Joseph Marchand remarque qu'il n'est pas toujours possible de résoudre le problème posé par son propre jeu. Pour éviter de perdre trop de temps, Joseph aimerait donc savoir à l'avance si une telle solution existe ou non.

Entrée¶

La première ligne contient quatre entiers, $N$ le nombre de tables, $T$ le total fixé à atteindre, $X$ la marge d'erreur autorisée, et $K$ le nombre maximum d'opérations possibles.

Sur la deuxième ligne, $N$ entiers se suivent (tous compris entre 1 et 100), représentant chacun le nombre de personnes assises à une même table.

Sortie¶

Une seule chaîne de caractère : "OUI" si une solution au problème de Joseph existe, et "NON" dans le cas contraire.

Contraintes¶

• $1 \le N \le 10$
• $1 \le T \le 100$
• $0 \le X \le 50$
• $1 \le K \le 10$

Contraintes de performance¶

• $1 \le N \le 100$
• $1 \le T \le 10000$
• $0 \le X \le 1000$
• $1 \le K \le 100$