Milk Pails

题目描述

农夫约翰收到了一份需要立刻完成的订单：恰好 $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'$ 表示约翰能够通过操作在两个桶中合计得到的牛奶总量。

输入格式

第一行也是唯一一行输入包含 $X$、$Y$、$K$ 和 $M$。

输出格式

输出 $M$ 与约翰能够得到的某个牛奶总量之间的最小距离。

14 50 2 32

18

提示

在两步操作内，约翰的桶中可能剩下如下数量（按 (桶1, 桶2) 表示）： (0, 0) = 0 units (14, 0) = 14 units (0, 50) = 50 units (0, 14) = 14 units (14, 36) = 50 units (14, 50) = 64 units 最接近 32 的总量是 14，差值为 18。注意，要把第一个桶倒空并最终得到 (0, 36)，还需要额外一步。 题目作者：Brian Dean

标签: USACO|2016|Silver

来源

USACO|2016|Silver