Seaux d’eau
Étant donné que l’on ne dispose que de deux récipients de tailles
x et y, on souhaite obtenir une quantité totale d’eau dans ces deux récipients qui soit la plus proche possible de la somme cible s.Vous êtes autorisé à effectuer jusqu’à
k opérations parmi les actions suivantes :- Remplir complètement l’un des seaux
- Vider l’un des seaux
- Transvaser le contenu d’un seau dans l’autre, en s’arrêtant quand le second est plein ou que le premier est vide (selon ce qui se produit en premier).
Au début, les deux seaux sont vides.
Il se peut qu’il soit impossible d’atteindre la somme totale
s dans les deux seaux. Il est donc demandé de trouver la plus petite différence |s - s’|, où s’ représente la quantité d’eau cumulée dans les deux seaux.Entrée
La seule ligne d’entrée contient 4 entiers
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) et s (1 ≤ s ≤ 200).Sortie
Le programme doit afficher la différence absolue minimale que l’on peut obtenir en effectuant au plus
k opérations.Exemples
Entrée | Sortie |
14 50 2 32 | 18 |
Explication
Nous ne pouvons effectuer que 2 opérations. Voici les différents résultats obtenus après ces 2 opérations :
- (0, 0) → 0 unités
- (14, 0) → 14 unités
- (0, 50) → 50 unités
- (0, 14) → 14 unités
- (14, 36) → 50 unités
- (14, 50) → 64 unités
Ainsi, la valeur la plus proche de 32 est 14, ce qui donne une différence de 18.
Notez qu’il aurait été possible d’obtenir 36 en vidant le premier seau à partir de (14, 36). Cependant, cela aurait nécessité 3 étapes, alors que nous ne pouvons en exécuter qu’au plus 2.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB