RiseOJ – 우유 들통

설명

농부 존은 정확히 $$M$$ 단위의 우유 주문을 받았고 ( $1 \leq M \leq 200$ ), 이를 당장 채워야 한다. 안타깝게도 그의 근사한 착유기가 방금 고장 나서, 우유를 잴 수 있는 것이라고는 정수 크기 $$X$$ 와 $$Y$$ 의 우유 들통 두 개뿐이다 ( $1 \leq X, Y \leq 100$ ). 두 들통은 처음에 모두 비어 있다. 이 두 들통으로 그는 다음 종류의 작업을 최대 $$K$$ 번 수행할 수 있다 ( $1 \leq K \leq 100$ ).

두 들통 중 하나를 꼭대기까지 가득 채울 수 있다.
두 들통 중 하나를 비울 수 있다.
한 들통의 내용물을 다른 들통에 부을 수 있다. 붓던 들통이 비거나 받는 들통이 가득 차면 (둘 중 먼저 일어나는 시점에) 멈춘다.

농부 존은 두 들통에 담긴 우유의 총량을 정확히 $$M$$ 단위로 만들지 못할 수도 있다는 것을 알고 있지만, $$M$$ 과 두 들통의 우유 총량 사이의 최소 오차를 계산하는 것을 도와주자. 즉, 농부 존이 두 들통에 합쳐서 $$M'$$ 단위의 우유를 만들 수 있을 때 $$|M-M'|$$ 의 최솟값을 계산하여라.

출제자: Brian Dean

제약

출제자: Brian Dean

입력 형식

입력은 한 줄로 이루어지며, $$X$$ , $$Y$$ , $$K$$ , $$M$$ 이 주어진다.

출력 형식

농부 존이 만들 수 있는 우유 양과 $$M$$ 사이의 최소 차이를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 pails.in · 출력을 쓸 파일 pails.out

예제 1

입력

14 50 2 32

출력

설명

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).

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2015-2016 > February > Silver

올림피아드 > USACO > 2015-2016 > February > Silver

태그

JudgeUSACO

우유 들통

평가 및 의견

풀이 제출