Problem2952--三个水杯

2952: 三个水杯

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 3
[Status] [Submit] [Creator:]

Description

有三个水杯,编号分别为 A、B、C。   

A 杯的容积为 a 升,B 杯的容积为 b 升,C 杯的容积为 c 升。  

初始时,三个杯子都是空的。  

然后你需要执行若干次操作,每次操作,你可以:  

- 选择任意一个水杯,并将水杯中装满水;或者
- 选择任意一个水杯,并将水杯中的水都倒掉;或者
- 从某一个水杯中倒水到另一个水杯中,直至倒水的水杯变空或者接水的水杯变满才停止。  

你希望最终:A 杯中的水恰好有 x 升,同时 B 杯中的水恰好有 y 升,同时 C 杯中的水恰好有 z 升。  

问:能否实现?若能实现,最少需要执行多少次操作?

Input

第一行,三个整数 a, b, c,表示三个水杯的容积。  

第二行,三个整数 x, y, z,表示最终每个水杯中水的体积。  

Output

如果不能达到最终的局面,输出 -1;否则,输出一个整数,表示最少需要进行几次操作能达到最终的局面。  

Sample Input Copy

10 7 3
5 5 0

Sample Output Copy

10

HINT

【样例解释】

方便起见,我们用三元组 (a, b, c) 表示当前的局面,它表示:当前 A 杯中有水 a 升,B 杯中有水 b 升,C 杯中有水 c 升。

最少需要 10 步,每一步对应的具体操作如下:  

1. 先将 A 杯装满水,状态变为 (10, 0, 0);
2. 再将 A 杯中的水倒入 B 杯(倒入了 7 升,还剩下 3 升),状态变为 (3, 7, 0);
3. 再将 B 杯中的水倒入 C 杯(导入了 3 升,还剩下 4 升),状态变为 (3, 4, 3);
4. 再将 C 杯中的水全部倒入 A 杯,状态变为 (6, 4, 0);
5. 再将 B 杯中的水倒入 C 杯(倒入了 3 升,还剩下 1 升),状态变为 (6, 1, 3);
6. 再将 C 杯中的水全部倒入 A 杯,状态变为 (9, 1, 0);
7. 再将 B 杯中的水全部倒入 C 杯,状态变为 (9, 0, 1);
8. 再将 A 杯中的水倒入 B 杯(倒入了 7 升,还剩下 2 升),状态变为 (2, 7, 1);
9. 再将 B 杯中的水倒入 C 杯(倒入了 2 升,还剩下 5 升),状态变为 (2, 5, 3);
10. 再将 C 杯中的水全部倒入 A 杯,状态变为 (5, 5, 0)。

【数据规模与约定】

- 对于 30% 的数据,a, b, c ≤ 10
- 对于 100% 的数据,1 ≤ a, b, c ≤ 100; 0 ≤ x ≤ a; 0 ≤ y ≤ b; 0 ≤ z ≤ c

Source/Category