
USACO 2016 February Contest, Silver
Problem 3. Milk Pails
Contest has ended.

Log in to allow submissions in analysis mode
- He can fill either pail completely to the top.
- He can empty either pail.
- He can pour the contents of one pail into the other, stopping when the former becomes empty or the latter becomes full (whichever of these happens first).
Although FJ realizes he may not be able to end up with exactly $M$ total units of milk in the two pails, please help him compute the minimum amount of error between $M$ and the total amount of milk in the two pails. That is, please compute the minimum value of $|M-M'|$ such that FJ can construct $M'$ units of milk collectively between the two pails.
INPUT FORMAT (file pails.in):
The first, and only line of input, contains $X$, $Y$, $K$, and $M$.OUTPUT FORMAT (file pails.out):
Output the smallest distance from $M$ to an amount of milk FJ can produce.SAMPLE INPUT:
14 50 2 32
SAMPLE OUTPUT:
18
In two steps FJ can be left with the following quanities in his pails
(0, 0) = 0 units (14, 0) = 14 units (0, 50) = 50 units (0, 14) = 14 units (14, 36) = 50 units (14, 50) = 64 units
The closest we can come to 32 units is 14 for a difference of 18. Note that it would require an extra step to pour out the first pail to end up with (0, 36).
Problem credits: Brian Dean