Sujet 3 (C)

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).

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

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

Exemple 1

entrée :

1 2 5 10 20 50 100 200
6

sortie :

5

Exemple 2

entrée :

10 20 50 100 200
500

sortie :

450

Exemple 3

entrée :

200
200000000

sortie :

1

Commentaires

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


Source : http://www.france-ioi.org/