Prologin
2025
Énoncé¶
Entre certaines missions vous prenez du temps pour vous balader dans les marchés extra-terrestres, un événement qui vous fascine tout particulièrement, pour son incroyable mélange de culture et de curiosité venu de toutes les galaxies. Cela sera l'occasion de ramener un souvenir de votre dernière mission P.A.N.D.A (Parachutage Auto Négociant la Descente Astrale).
Vous avez repéré un marchand de minerai rare et inconnu de la planète Terre. En tant que fin connaisseur des cultures extra-terrestres, vous êtes évidemment au courant de la coutume locale, et de l'importance de la contigüité. Pour faire plaisir au vendeur (qui semble grincheux et légèrement xénophobe), vous vous appliquez donc pour choisir uniquement des minerais contigus sur le fil.
Pour éviter que ce souvenir prenne trop de place, vous souhaitez choisir un nombre minimal de minerai, toujours contigus sur le fil, tel que la somme de leurs prix soit exactement égale à votre budget cadeau $B$.
Entrée¶
Sur la première ligne un entier $N$ indiquant le nombre de minerai rare.
La deuxième ligne est constituée de $N$ entiers séparés par des espaces, représentant le prix de chaque minerai.
Enfin, la dernière ligne contient $B$, le total d'argent que vous souhaitez dépenser dans ce souvenir.
Sortie¶
Le nombre minimal de minerai que vous rapporterez, ou -1 si ce n'est pas possible de résoudre le problème.
Contraintes¶
- $1 ≤ N ≤ 100$
- $0 ≤ prix ≤ 100$
- $1 ≤ B ≤ 10000$
Contraintes de performance¶
- $1 ≤ N ≤ 10^6$
- $1 ≤ B ≤ 10^8$