Water Pails
Given only two cups of sizes
x and y, you would like to obtain a total amount of water in those two cups as close to the target sum s as possible.You are allowed to perform up to
k operations of the following form:- Fill one of the pails completely to the top
- Empty one of the pails
- Pour the contents of one pail into the other, stopping when the latter becomes full or the first one becomes empty (whichever happens first).
Initially, both of the pails are empty.
It might not be possible to obtain a total sum
s in both pails, so you are asked to find the smallest difference |s - s’|, where s’ is the collective water between two pails.Input
The only line of the input contains 4 integers
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100), and s (1 ≤ s ≤ 200).Output
The program should print the minimum absolute difference possible to obtain by performing at most
k operations.Examples
Input | Output |
14 50 2 32 | 18 |
Explanation
We are allowed to perform only 2 operations. So, these are the possible outcomes after 2 operations:
- (0, 0) → 0 units
- (14, 0) → 14 units
- (0, 50) → 50 units
- (0, 14) → 14 units
- (14, 36) → 50 units
- (14, 50) → 64 units
Therefore, the closest to 32 we can get is 14, making the difference 18.
Note that we could’ve obtained 36 by emptying the first pail from (14, 36), yet that would require 3 steps, while we’re only allowed to perform at most 2.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB