Énoncé

Il y a 8 valeurs usuelles pour les pièces en euros : 1¢, 2¢, 5¢, 10¢, 20¢, 50¢, 1€=100¢ et 2€=200¢. 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 3¢, il y a 2 manières : ou bien on paye 1¢+1¢+1¢, ou bien on paye 2¢+1¢. Lorsque certaines valeurs de pièces ne sont pas disponibles, et qu'on n'a accès par exemple qu'aux pièces de 1¢ et de 5¢, le nombre de manières d'obtenir une somme diminue (par exemple, il n'y a plus que 3 manières de faire 12¢ : 12 fois 1¢, 5¢ et 7 fois 1¢, ou bien 2 fois 5¢ et 2 fois 1¢).

Entrée

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.

Sortie

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.

Exemples

Entrée	Sortie
1 2 5 10 20 50 100 200 6	5
10 20 50 100 200 500	450
200 200000000	1

Squelette CamlLight

(* 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 ^ (sub_string chaine i 1);
  done;
  res := !res @ [!temp];
  !res;;

(* On lit la liste des pièces de monnaie disponibles *)
let pieces = 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 *)

Squelette OCaml

(* 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 *)