P3139 [USACO16FEB]牛奶桶Milk Pails

    • 112通过
    • 269提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2016
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Farmer John has received an order for exactly $M$ units of milk ($1 \leq M \leq 200$) that he needs to fill right away. Unfortunately, his fancy milking machine has just become broken, and all he has are two milk pails of integer sizes $X$ and $Y$ ($1 \leq X, Y \leq 100$) with which he can measure milk. Both pails are initially empty. Using these two pails, he can perform up to $K$ of the following types of operations ($1 \leq K \leq 100$):

    • 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. FJ最近刚收到了解决M(1<=m<=200)个单位牛奶的指令。他有三个桶,大小分别为X,Y(1<=X,Y<=100)。

    他可以选择执行如下操作k(1<=k<=100)次:

    他可以在任意一个桶中装满牛奶。

    他可以倒空任意一个桶

    他可以将一个桶里的奶倒入另一个桶中,直到倒空或另一个桶被倒满

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

    输入输出格式

    输入格式:

    The first, and only line of input, contains $X$, $Y$, $K$, and $M$.

    输出格式:

    Output the smallest distance from $M$ to an amount of milk FJ can produce.

    输入输出样例

    输入样例#1: 复制
    14 50 2 32
    输出样例#1: 复制
    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).

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。