python 解决母亲的奶牛问题

2744557306

题目描述】
/ L. _4 T& J. R6 J2 I8 u
        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

' s9 f$ l! R' R8 c8 s【输入格式】

, b$ q; N. Z5 c0 n        共一行，包含三个整数 A,B,C。

【输出格式】
! ]7 c; e$ c  D; r$ y
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

1 d8 m4 {% j% r! C7 v) j6 e9 h【数据范围】
3 L3 q4 z3 \4 k7 i, E
        1≤A,B,C≤20
* {* ]$ X) ~2 B5 p7 N4 W! `: g
【输入样例】
4 q2 @+ `+ S& {$ o! B7 X& K
8 9 10
【输出样例】

1 2 8 9 10
【解题思路】

6 `- m3 B$ g" I5 r$ L0 @, @! p& k        BFS简答模拟一下倒牛奶的过程。

1. from collections import */ S) K3 P% O) n
   
2. a,b,c = map(int,input().split())
   3 |. v: e1 F: w+ p
3. n = 22
   - Z0 j5 N6 Y, x# Z/ i/ ^7 K5 m# V
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]) S\" _% {5 j* S) s; z1 b
   
5. 1 P) u, X: f! O* ?) Z$ S9 r
   
6. q = deque()
   . ?9 c  y8 ~5 A+ ?, W% m- w
7. def ins(a_,b_,c_):9 T! ~8 G& T( m6 e) C( N
   
8.     global q' N. C: g5 @$ H' R. t( B
   
9.     if st[a_][b_][c_]:return  `+ A& s3 A  C- B7 G! }
   
10.     q.append([a_,b_,c_])6 B/ l1 Y0 X- p# H3 ~: K
    
11.     st[a_][b_][c_]=1
    & Y& Q+ P9 F) f* U( E4 a+ w
12. def bfs():
    / V: h: l, W, G
13.     q.append([0,0,c])% u8 f( D# k% M- Y
    
14.     st[0][0][c]=1! s5 n9 ~- M* m' C\" E' ?3 e3 G
    
15.     while q:
    * ]  n0 T8 Q* H\" ]) J9 I$ ?
16.         a_,b_,c_ = q.popleft()
    9 w: z4 r; W# h- a4 y7 L* X& d
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )7 m7 b  Y+ R4 i4 v3 h& r2 O
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    , R7 H  C0 ~# i* Y, f- C8 ]4 V3 Y
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )! a8 v! p4 |, g) F! ?
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    ) P5 b! _0 y5 H+ t
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    / R+ M' W& z% I8 j5 G3 C\" x% {
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )5 s, N  G% \# _9 P! N2 O5 @& r\" C
    
23. bfs()
    ) o* p\" F3 j. [% O: f& b
24. for c_ in range(c+1):( ?* f8 z! Z3 N# M; W  u
    
25.     for b_ in range(b+1):\" V/ L1 H, P# y9 z0 c
    
26.         if st[0][b_][c_]:
    ' \  E% _2 r2 y  D- C% a- S9 R
27.             print(c_,end=' ')0 H) r6 Q0 H( a0 _4 a: N5 M
    
28.             break

复制代码