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.


The only line of the input contains 4 integers x, y (1 ≀ x, y ≀ 100), k (1 ≀ k ≀ 100), and s (1 ≀ s ≀ 200).


The program should print the minimum absolute difference possible to obtain by performing at most k operations.


14 50 2 32


We are allowed to perform only 2 operations. So, these are the possible outcomes after 2 operations:
  1. (0, 0) β†’ 0 units
  1. (14, 0) β†’ 14 units
  1. (0, 50) β†’ 50 units
  1. (0, 14) β†’ 14 units
  1. (14, 36) β†’ 50 units
  1. (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.


Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue