logo AlgoBeat OnlineJudge
登录 注册

#104413. [BZOJ 4413] [Usaco2016 Feb]Milk Pails

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

FJ 最近刚收到了解决 个单位牛奶的指令。他有两个桶,大小分别为

他可以选择执行如下操作 次:

他可以在任意一个桶中装满牛奶;他可以倒空任意一个桶;他可以将一个桶里的奶倒入另一个桶中,直到倒空或另一个桶被倒满

尽管 FJ 意识到他可能不能在两个桶中刚好装下 个单位的牛奶,但请你算出他经过操作后,两桶牛奶的和同 的差值最小是多少。

输入格式

输入的第一行(也是唯一一行)包含

输出格式

输出从 到 FJ 能够生产的牛奶量的最小距离。

样例

样例输入 #1

14 50 2 32

样例输出 #1

18

数据范围与提示

只需两步,FJ 的桶里就会剩下以下数量

(0, 0) = 0 单位
(14, 0) = 14 单位
(0, 50) = 50 单位
(0, 14) = 14 单位
(14, 36) = 50 单位
(14, 50) = 64 单位

最接近 个单位的数是 ,相差

请注意,需要额外的步骤才能倒出第一桶牛奶,最终得到 。 对于 的数据,