Hydratation – Qualification 2012

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

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
200 milliseconds

Input/output samples

Sample input
2
8
Sample output
4
Note

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.

Sample input
41
42
Sample output
42
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.