Énoncé

On considère n récipients identiques, remplis de liquide à différents niveaux. On souhaite répartir le liquide de manière équilibrée dans les récipients en faisant un minimum de transvasements. Supposons par exemple qu'il y ait 3 récipients initialement remplis à 3L, 7L et 2L. Si on transvase 1L du deuxième vers le premier, on passe à l'état 4L / 6L / 2L. On transvase alors 2L du deuxième vers le troisième et on arrive à l'état 4L / 4L / 4L. Il nous a fallu deux transvasements.

Entrée

L'entrée du programme sera la liste des volumes contenus initialement dans les récipients, séparés par des espaces, le tout suivi d'un retour à la ligne. Pour simplifier et éviter les problèmes d'arrondis, les volumes seront toujours des entiers, et leur moyenne sera aussi toujours entière (donc l'équilibre que l'on souhaite atteindre sera pour une valeur entière d'unités de volume dans chaque récipient).

Sortie

La sortie de votre programme devra être le nombre minimum de transvasements requis (chaque transvasement se faisant depuis exactement 1 récipient vers exactement 1 récipient) pour arriver dans l'état où tous les récipients contiennent la même quantité de liquide. Ce nombre devra être suivi d'un retour à la ligne.

Exemples

Entrée	Sortie
3 7 2	2
21 10 9 1 1 1 1 1 0	6
43 10 9 9 1 1 1 1 1 1 1 1 1 0 0 0	12

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;;
  
let liste_volumes = map int_of_string (split_spaces (input_line stdin));;

(* liste_volumes est maintenant une "int list" qui contient la liste des volumes *)

(* 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;;
  
let liste_volumes = List.map int_of_string (split_spaces (input_line stdin));;

(* liste_volumes est maintenant une "int list" qui contient la liste des volumes *)

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