Il y a 8 valeurs usuelles pour les pièces en euros : 1c, 2c, 5c, 10c, 20c, 50c, 1€=100c et 2€=200c. De combien de manières possibles peut-on payer une somme donnée en n'utilisant que des pièces ?
NB. On ne tient pas compte ici de l'ordre dans lequel on donne les pièces. Par exemple, pour payer 3c, il y a 2 manières : ou bien on paye 1c+1c+1c, ou bien on paye 2c+1c.Lorsque certaines valeurs de pièces ne sont pas disponibles, et qu'on n'a accès par exemple qu'aux pièces de 1c et de 5c, le nombre de manières d'obtenir une somme diminue (par exemple, il n'y a plus que 3 manières de faire 12c : 12 fois 1c, 5c et 7 fois 1c, ou bien 2 fois 5c et 2 fois 1c).
La première ligne de l'entrée du programme contient la liste des valeurs de pièces de monnaie disponibles (en cents), la seconde contient la somme totale à payer. Le tout est suivi d'un retour à la ligne. Les entrées seront telles que la réponse ne sera jamais supérieure à 20000.
La sortie du programme doit être le nombre de manières de payer la valeur d'entrée avec les pièces disponibles (il n'y a pas de limite au nombre de pièces qu'on utilise pour une valeur disponible donnée). Le tout doit être suivi d'un retour à la ligne.
entrée :
1 2 5 10 20 50 100 200 6
sortie :
5
entrée :
10 20 50 100 200 500
sortie :
450
entrée :
200 200000000
sortie :
1
Squelettes de codes :
(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les
mettre dans des variables, et afficher votre resultat final en sortie. *)
(* fonction pour separer les elements en entree
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
let res = ref [] in
let temp = ref "" in
for i = 0 to String.length chaine - 1 do
if chaine.[i]=' '
then
begin
res := !res @ [!temp];
temp := "";
end
else
temp := !temp ^ (String.sub chaine i 1);
done;
res := !res @ [!temp];
!res;;
(* On lit la liste des pièces de monnaie disponibles *)
let pieces = List.map int_of_string (split_spaces (input_line stdin));;
(* On lit la somme a atteindre, en cents, et on la stocke dans un entier n *)
let n = int_of_string (input_line stdin);;
(* fonction pour afficher votre solution *)
let affiche_solution i =
print_int i;
print_newline();;
(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)
(* Debut de votre programme *)
(* Fin de votre programme *)