P6960: 牛奶桶
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
农夫约翰收到了M个单位牛奶的订单(1≤M≤200)，他需要马上交货。不幸的是，他的高级挤奶机刚刚坏了，他只有两个大小为X和Y的牛奶桶(1≤X,Y≤100)，他可以用来测量牛奶。两个桶最初都是空的。使用这两个桶，他最多可以执行K次以下操作(1≤K≤100):
1.他可以把任何一个桶都装满。
2.他可以把两个桶都倒空。
3.他可以把一个桶里的东西倒进另一个桶里，当前者变空或后者变满时停止(以先发生的为准)。
尽管FJ意识到他可能无法在两桶中得到M单位的牛奶，但请帮助他计算M与两桶中牛奶总量之间的最小误差量。即，请计算|M−M ' |的最小值，使FJ可以在两桶之间共构造M '单位的牛奶。
【输入格式】(paches .in):
第一行，也是唯一的一行，包含X、Y、K和M。
【输出格式】(paches .out):
输出从M到FJ所能生产的奶量的最小距离。
【样例输入】:
14 50 2 32
【样例输出】:
18
【样例说明】
在两个步骤中，FJ可以在他的桶中留下以下数量。
(0,0) = 0个单位
(14,0) = 14个单位
(0,50) = 50个单位
(0,14) = 14个单位
(14,36) = 50个单位
(14,50) = 64个单位
我们最接近32个单位的是14个单位，相差18个单位。请注意，它将需要一个额外的步骤来倒出第一个桶，以得到(0,36)。