水のバケツ
x と y の容量をもつ 2 つのバケツだけが与えられているとき、これら 2 つのバケツにためる水の合計を、目標値 s にできるだけ近づけたいとします。操作は最大で
k 回まで行え、以下のいずれかを 1 回の操作とみなします:- どちらか一方のバケツを満杯になるまで水で満たす
- どちらか一方のバケツを空にする
- 一方のバケツの水をもう一方に移す。ただし、移す先が満杯になるか、移す元が空になるかのどちらか早い方で操作を止める
初期状態では、両方のバケツは空です。
もし 2 つのバケツの合計をちょうど
s にすることができなくても、なるべく近い値 s' を作りたいと考えます。そのときの差の絶対値 |s - s'| の最小値を求めてください。入力
入力は 1 行で、4 つの整数
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100), s (1 ≤ s ≤ 200) が与えられます。出力
最大
k 回の操作を行ったときに得られる、s との差の絶対値の最小値を出力してください。サンプル
Input | 入力 |
14 50 2 32 | 18 |
解説
操作は最大 2 回までなので、2 回の操作で可能な水の合計は以下の通りです:
- (0, 0) → 0 単位
- (14, 0) → 14 単位
- (0, 50) → 50 単位
- (0, 14) → 14 単位
- (14, 36) → 50 単位
- (14, 50) → 64 単位
目標の
32 にもっとも近づけるのは 14 で、そのときの差は 18 となります。実は (14, 36) の状態から最初のバケツを空にして 36 を得ることも可能ですが、この操作を含めると 3 回必要になるため、最大 2 回という制限を超えてしまいます。
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB