Énoncé

On cherche à réaliser un algorithme de rendu de pièces pour un distributeur automatique. Ce distributeur est destiné à être mis en place dans des pays de la zone euro, et on cherche à en simplifier au maximum la maintenance.

On part donc avec le problème suivant : on a un nombre de pièces limité et connu dans la machine. Lorsqu'un paiement est réalisé, les pièces utilisées par le consommateur sont mises dans un pot commun et ne sont donc pas réutilisables pour rendre la monnaie. On va chercher à rendre la monnaie avec un nombre minimal de pièces, afin de garder un maximum de pièces dans la machine.

Cependant, on veut limiter au maximum le temps d'indisponibilité de la machine. Lorsqu'une machine n'a plus assez de pièce pour rendre la monnaie, il faut faire intervenir un technicien, qui va venir remplir la machine (et vider le pot commun). Cette intervention est coûteuse, et le temps pendant lequel la machine ne peut plus rendre la monnaie entraîne un préjudice financier non négligeable. On veut donc garder la machine opérationnelle le plus longtemps possible, et prévenir le technicien au bon moment.

Pour atteindre ce résultat, on introduit la notion de réserve de pièces. Le but est de garder cette réserve intacte le plus longtemps possible. Lorsque cette réserve est entamée, le technicien est appelé et en attendant sa venue on va pouvoir utiliser les pièces qui s'y trouvent, en cherchant toujours à minimiser le nombre de pièces rendues. La réserve est de 2 pièces de 2 euros, 4 pièces de 1€, 4 pièces de 50 cts, 5 pièces de 20 cts, 4 pièces de 10 cts, 4 pièces de 5 cts, 5 pièces de 2 cts, et 4 pièces de 1 cts.

Dans cet exercice, on vous donne à chaque fois le prix à payer et le prix payé par le client, tous les prix sont donnés en centimes. On vous donne également le nombre de chacune des pièces initialement dans la machine. Les valeurs des pièces sont triées par ordre décroissant.

Entrée

L'entrée du programme est donnée sur 3 lignes :

le prix à payer par le client
la somme payée par le client, qui ne dépassera pas 10000 cts
le nombre de pièces au total (y compris la réserve) restantes dans la machine pour chacune des valeurs (max. 10000 par valeur), sous la même forme est dans le même ordre que pour les valeurs (le premier nombre représente le nombre de pièces de la plus forte valeur, le dernier nombre représente le nombre de pièces de la plus faible valeur)

Sortie

La sortie sera le nombre de pièces nécessaires pour rendre la monnaie (-1 si impossible) en essayant avant tout de ne pas entamer la réserve, suivi d'un 1 si il faut appeler le technicien pour reremplir, ou d'un 0 si le distributeur n'a pas entamé la réserve. On appellera le technicien si la réserve est déjà entamée avant même de rembourser le client. Le paiement du client sera toujours suffisant.

Exemples

Entrée	Sortie
30 200 6 10 9 7 5 8 10 5	3 0

Squelette CamlLight Corrigé

(* 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];
    let res_int = map int_of_string !res in
    let tab = vect_of_list res_int in
    tab;;

let affiche_solution nb_pieces reserve =
   print_int nb_pieces;
   print_string " ";
   print_int reserve;
   print_newline();;

(* Recuperation du prix a payer *)
let prix = int_of_string (input_line stdin);;
(* Recuperation du prix paye *)
let paye =  int_of_string (input_line stdin);;
(* Tableau de valeur des differentes pieces *)
let valeurs  = [|200;100;50;20;10;5;2;1|];; 
(* Tableau contenant le nombre de pieces de chaque valeur *)
let disponibles = split_spaces (input_line stdin);;

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

(* 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];
    let res_int = List.map int_of_string !res in
    let tab = Array.of_list res_int in
    tab;;

let affiche_solution nb_pieces reserve =
   print_int nb_pieces;
   print_string " ";
   print_int reserve;
   print_newline();;

(* Recuperation du prix a payer *)
let prix = int_of_string (input_line stdin);;
(* Recuperation du prix paye *)
let paye =  int_of_string (input_line stdin);;
let valeurs  = [|200;100;50;20;10;5;2;1|];; 
(* Tableau contenant le nombre de pieces de chaque valeur *)
let disponibles = split_spaces (input_line stdin);;

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