Hydratation – Qualification 2012

Niveau 3

Énoncé

En salle machine, il fait souvent très chaud, c'est pourquoi nous abreuvons nos candidats. Par souci de précision, nous leur permettons même de demander le nombre de centilitres de jus d'orange qu'ils souhaitent. Hélas, bien que nous ayons une quantité infinie de jus d'orange, nous ne disposons que de deux gobelets, respectivement de a et b centilitres (a < b).

Vous pouvez :

  • remplir un gobelet à ras bord de jus d'orange ;
  • vider un gobelet intégralement ;
  • verser un gobelet dans un autre jusqu'à ce que l'un soit vide ou que l'autre soit plein.

Combien de commandes différentes comprises entre 1 et b centilitres pouvons-nous satisfaire ?

Contraintes

  • 1 <= a < b <= 999 999 999 sont les contenances de nos gobelets, en centilitres.

Entrée

L'entrée standard contient deux entiers a et b (dans cet ordre) représentant les contenances de nos gobelets, en centilitres.

Sortie

Vous devez écrire une ligne sur la sortie standard : le nombre de commandes différentes comprises entre 1 et b centilitres que nous pouvons satisfaire.

Contraintes d'exécution

Utilisation mémoire maximum
2000 kilo-octets
Temps d'exécution maximum
200 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
2
8
Exemple de sortie
4
Commentaire

Exemple de versement, avec des gobelets de 2 et 8 cL

  • Remplir le gobelet de 8 cL à ras bord nous permet d'obtenir 8 cL.
  • Verser le gobelet de 8 cL dans celui de 2 cL nous permet d'obtenir 6 cL.
  • Vider le gobelet de 2 cL puis y verser 6 cL de jus d'orange nous permet d'obtenir 4 cL.

Les volumes que nous pouvons effectuer sont donc 2, 4, 6 et 8 cL, soit 4 commandes différentes en tout.

Exemple d'entrée
41
42
Exemple de sortie
42
Commentaire

Avec des gobelets de 41 et 42 cL, nous pouvons satisfaire toutes les commandes. La réponse est donc, comme vous le savez déjà, 42.