h*********r
发帖数: 76 | 1 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
怎么做了。
输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
例子：
输入： 5 3
代表第一个水桶5L，第二个水桶3L
（输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
的容积可能相同）
那么输出
1: 4 最少4次操作得到1L水
2: 2
3: 1
4: 6
5: 1
如果无法得到x L的水，输出x: impossible
每次盛水必须装满该桶，从桶1导入桶2的时候，必须要么桶1倒光，要么桶2接满水
我这题只会做两个水桶的，就是不断把一个水桶装满然后倒入第二个水桶，看看当中出
现过那些容积的水
但是多个水桶的不太会做
各位有什么思路么 |
h**********c
发帖数: 4120 | 2 两桶水曾经在电影die hard series 中一集出现
以后就很少见红博flex their brain |
s***5
发帖数: 2136 | 3 interesting. why the answer is 4? 2*3-5 = 1, isn't it 2?
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
l****h
发帖数: 1189 | 4 为什么1：4？
如果有1升的水桶呢？ 你的条件不是 1-20吗？
是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
量？然后其中操作最多的一个是4次？
修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
腾就能得到目标。还是不对， 我找一个3，一个2，一次操作不就完事了？1：1； 2：1
； 3：1.。。。
是我糊涂，没看到有给定的输入。
我的笨办法，是建立 table,
操作次数
T1： b1, b2, b3 b4, b5
T2: 所有bi+-T1
T3: 所有 bi+-T2
T4: ....
..
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
h*********r
发帖数: 76 | 5 这个例子的输入是 5 3
代表第一个水桶5L，第二个水桶3L
输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的的
容积可能相同
：1
【在 l****h 的大作中提到】
: 为什么1：4？
: 如果有1升的水桶呢？ 你的条件不是 1-20吗？
: 是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
: 量？然后其中操作最多的一个是4次？
: 修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
: 再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
: 腾就能得到目标。还是不对， 我找一个3，一个2，一次操作不就完事了？1：1； 2：1
: ； 3：1.。。。
: 是我糊涂，没看到有给定的输入。
: 我的笨办法，是建立 table,
|
h*********r
发帖数: 76 | 6 首先装满小桶，这时候两个桶水量为3,0
然后小桶倒入大桶，水量分别为0,3
装满小桶，3,3
小桶导入大桶，1,5
这时候小桶剩余1L
4次操作
【在 s***5 的大作中提到】
: interesting. why the answer is 4? 2*3-5 = 1, isn't it 2?
|
d**********6
发帖数: 4434 | |
B*********t
发帖数: 105 | 8 我还以为是脑筋急转弯。假设桶是圆柱体形状的话，把桶倾斜到刚好看到底面的时候，
剩余的水量刚好是1/2.
所以如果是3和5升的两个桶，那么用2.5-1.5就可以得到1升的水了。。
没看到必须倒满这个条件。感觉是很傻的一个题目。。 |
o***e
发帖数: 28 | 9 说白了就是求一个整系数不定方程的整数解 .. a_0 x_0 + a_1 x_1 + .. + a_{n-1} x
_{n-1} = b, a_i 为桶的容积, b 为最终目标的水量
如果 b 是所有 a_i 的最大公约数及其倍数, 则 (可能) 有解; 否则无解 |
f*********s
发帖数: 1881 | 10 基本同意这个，但是有两点细节需要优化，具体到下面两个例子，
例子1: 【5，3】
1:4
例子2: 【7，3】
1:4
例子1说明每次做加法count加 2，减法加1.例子2说明有时候减法也有加2。
我觉得可能需要分情况建立一个library，index是count，然后在library里search
：1
【在 l****h 的大作中提到】
: 为什么1：4？
: 如果有1升的水桶呢？ 你的条件不是 1-20吗？
: 是不是这样的意思：５个水桶是随机给的，任意给定的每组水桶都要能产生出1升的测
: 量？然后其中操作最多的一个是4次？
: 修改：看来理解还是不对，给了5个20升水桶，怎么也不能产生1.
: 再修改：你要在1-20的水桶中找5个水桶（不能用和目标一样大的水桶），最快几次倒
: 腾就能得到目标。还是不对， 我找一个3，一个2，一次操作不就完事了？1：1； 2：1
: ； 3：1.。。。
: 是我糊涂，没看到有给定的输入。
: 我的笨办法，是建立 table,
|
|
|
v*****1
发帖数: 2200 | 11 桶太小
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
B*******g
发帖数: 1593 | 12 这很像硬币凑数的题目啊，不过有减法，次数统计也不像数硬币那么直接，应该可以dp?
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
c**********8
发帖数: 1052 | 13
像DP
一个hashtable（L数，操作次数）
初始化，已有桶的L数，对应次数是1，其他是impossible
然后对已有的L数做相减操作，对应次数相加
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
a***u
发帖数: 318 | 14 小桶装满 3L 倒入 大桶 （3L/5L）
再次装满小桶，倒满大桶 (2L+3L/5L),
最后剩下 1L 在小桶内 |
h*********r
发帖数: 76 | 15 题目不是就求这一个诶。。
【在 a***u 的大作中提到】
: 小桶装满 3L 倒入 大桶 （3L/5L）
: 再次装满小桶，倒满大桶 (2L+3L/5L),
: 最后剩下 1L 在小桶内
|
h*********r
发帖数: 76 | |
i********y
发帖数: 34 | 17 1. check if x is possible (as someone mentioned, x is only possible if it's
a multiple of greatest common divisor K of all buckets)
2. get max steps for each x (1 if x = bucket_i. For others, use max(bucket_i
) and bucket_j where their GCD is K. Repeatedly pour one to the other until
all x are found)
3. get min steps for each x. Use recursive method and try all possibilities,
dynamically update max steps for other x along the way. Number of recursive
depth can't exceed the max step for x.
【在 h*********r 的大作中提到】
: 标题这道题相信大家都熟的不能再熟了，现在遇到一个更加general的题目，就不知道
: 怎么做了。
: 输入为每个水桶的容积[1, 20]， 水桶个数为 1-5个，相同容积的水桶可能重复
: 输出格式为x:y，代表最少y次操作得到x的水，x 属于[1, max(输入水桶容积)]
: 例子：
: 输入： 5 3
: 代表第一个水桶5L，第二个水桶3L
: （输入的水桶个数最多有5个，每个水桶的容积是 1 - 20 L，并且为整数，水桶之间的
: 的容积可能相同）
: 那么输出
|
