题目描述】8 K- y9 V- K3 E y' H
1 p h8 O6 F4 e% C6 o
农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的,而桶 C 里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。请你编写一个程序判断,当 A 桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。6 |. G5 H0 u( `! L& U6 {
+ C! L1 A8 t! f' L) F3 X1 L【输入格式】+ n/ U5 T/ t3 [; B$ P! @, L
1 f1 |, X2 b7 g8 \
共一行,包含三个整数 A,B,C。& C9 W0 T+ b/ N. l. S
2 v9 L( ~; c* m d A* q0 P$ J
【输出格式】 % r% J- C" P9 U$ T p2 f/ S, z& Y e. W; B
共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。 & s1 A& T8 i _# ]- f) g, `% [0 o' ]. n' b: |; o1 C
【数据范围】 ' u. w0 C) S2 N: x- a7 `+ s# o7 U% X2 w' P( O
1≤A,B,C≤20 4 k2 S. U. E. R8 L5 W, S6 |8 u; ^ 6 d. O( {) T4 z7 y3 b- z) P【输入样例】8 {0 f# w1 g$ @+ {) V% J
4 B0 v5 d- ^2 T( Z [: y/ A5 ^
8 9 10: ?3 w2 K: K# @0 l) Z
【输出样例】: H* b6 k' J' r
9 a7 o R1 [& i9 P0 Q3 C; s0 Y( b
1 2 8 9 10 / ]1 {% b/ v. n \# i5 U; I6 e0 c4 G 【解题思路】/ }+ j7 {* t0 M) M G- p
& |; e% G/ G6 Y" [. F+ l, w
BFS简答模拟一下倒牛奶的过程。
from collections import *2 q, J* z' w; W5 _& c; n# b+ F2 E
a,b,c = map(int,input().split()) 9 I' R, t/ M; s3 P: \- Q2 S
n = 22 \" j3 K4 d2 Q& N0 J, b
st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]1 g I2 o8 ~# }5 `8 n+ `
0 Q9 }% X1 X6 `/ ~3 O
q = deque()( H l T0 r8 p7 r0 ]
def ins(a_,b_,c_): 1 J: S. O0 J+ k7 q g
global q % m; z4 y5 g\" s
if st[a_][b_][c_]:return + e; ?# k! v1 V4 H/ E\" I2 D8 ]' Z- C
q.append([a_,b_,c_]): R; N& o. u! d/ O4 l
st[a_][b_][c_]=1 9 b4 E5 ~; q4 U/ `# V9 u6 p3 ]
def bfs(): / ?3 t7 O ~: x
q.append([0,0,c]) ) s4 r9 o\" P\" }7 e$ K
st[0][0][c]=1. @6 D, k' U6 |4 V! j
while q: b# a: i\" W1 X4 f; U
a_,b_,c_ = q.popleft(); m K1 ~* k* @ o; b8 t
ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ ) Q! E3 a G8 a% s* L9 B# B