Wassereimer
Angenommen, man verfügt nur über zwei Eimer mit den Größen
x und y. Man möchte eine Gesamtmenge Wasser in diesen beiden Eimern erreichen, die dem Zielwert s so nahe wie möglich kommt.Erlaubt sind bis zu
k Aktionen folgender Art:- Einen der Eimer ganz auffüllen
- Einen der Eimer vollständig entleeren
- Den Inhalt eines Eimers in den anderen umschütten, wobei man aufhört, wenn der zweite Eimer voll ist oder der erste leer (was zuerst eintritt).
Anfangs sind beide Eimer leer.
Es kann sein, dass man
s nicht exakt erreichen kann. Daher soll man die kleinste mögliche Differenz |s - s’| ermitteln. Hierbei ist s’ die Gesamtmenge Wasser in beiden Eimern.Eingabe
Die einzige Zeile der Eingabe besteht aus 4 ganzen Zahlen
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100) und s (1 ≤ s ≤ 200).Ausgabe
Das Programm soll die kleinste mögliche absolute Differenz ausgeben, die man mit höchstens
k Aktionen erreichen kann.Beispiele
Input | Output |
14 50 2 32 | 18 |
Erklärung
Es sind nur 2 Aktionen erlaubt. Mögliche Endzustände nach 2 Aktionen sind unter anderem:
- (0, 0) → 0 Einheiten
- (14, 0) → 14 Einheiten
- (0, 50) → 50 Einheiten
- (0, 14) → 14 Einheiten
- (14, 36) → 50 Einheiten
- (14, 50) → 64 Einheiten
Der Zielwert ist 32, und mit diesen Zuständen kommt man dem Wert 32 am nächsten, wenn man 14 Einheiten erreicht. Die Differenz beträgt somit 18.
Beachte, dass man durch weiteres Entleeren des ersten Eimers aus dem Zustand (14, 36) auch 36 hätte erreichen können. Das hätte aber insgesamt 3 Aktionen erfordert, obwohl nur maximal 2 erlaubt sind.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB