python 解决母亲的奶牛问题

2744557306

题目描述】
* ?* N1 R: k* e1 Z9 Q
0 q; o2 N5 L! B        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

5 D8 F5 h; g3 R# ^. a% N! o【输入格式】
0 m; J- {# S% m+ L5 Y
! X' X2 I3 n+ T' P; e) C6 x+ C8 \        共一行，包含三个整数 A,B,C。
, r8 r5 ^; m& Y& j
【输出格式】
5 L6 d" ~" w6 W2 D
* x# A( _) [# d# R, }7 ^" F- U        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
' H. C! l1 g' k- n
【数据范围】
4 V: c; \9 ^& Y* {/ H/ z0 ^/ E
) v- n3 U) S/ I: p" W        1≤A,B,C≤20
: h* D' I" I1 @5 H; E
3 L) s, e7 R# u" G; J4 S+ \【输入样例】

8 9 10
: @; d1 [, x2 o1 t" g/ q/ J【输出样例】

1 2 8 9 10
% R) S! g7 \6 |( ~6 C: o4 { 【解题思路】
# B4 b9 l1 |( u, D2 t4 r- m  f
/ Y0 K% Y/ b. P- b4 K- u        BFS简答模拟一下倒牛奶的过程。

1. from collections import *- x$ n- j0 c8 D
   
2. a,b,c = map(int,input().split())
   # B# ^* Y7 _& M* Q- M2 t
3. n = 22
   8 t6 p/ D  N& x5 Q* U, Q
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]' ]! J9 \* n/ ]3 ]6 k
   
5. 
   ! p2 S  R\" g! b, u
6. q = deque()
   4 [9 |& {: G) k
7. def ins(a_,b_,c_):
   * ?\" s2 Y% R0 `0 {9 N
8.     global q8 q. U8 Y! ?3 }0 U4 I
   
9.     if st[a_][b_][c_]:return
   ( H5 c7 N4 W- J6 O: d
10.     q.append([a_,b_,c_])
    8 j5 H1 W/ w# s4 W3 i6 R( z1 i
11.     st[a_][b_][c_]=1! y\" K/ Y+ m4 e- o6 T
    
12. def bfs():
    ' W& H9 @0 H; l$ P' _
13.     q.append([0,0,c])
    * q& C# S. W2 y) Y1 I! l. @5 e
14.     st[0][0][c]=1
    1 f) p# ?' M/ V, o) b
15.     while q:* s, z\" G6 r$ o8 z5 A2 _
    
16.         a_,b_,c_ = q.popleft()# k) t6 c4 q! o% ]( W$ P) W
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )) A4 q' X+ N) ], l
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ' n1 a$ F+ v7 M3 f; S/ L
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    % i$ r6 F2 [6 }. Z* j1 G# Z8 w
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )( e6 w4 [* p. I/ n8 X9 I5 H
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    \" ~+ D5 e) ]! m6 |  i
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )9 k\" D1 g9 [  r/ |
    
23. bfs()7 D1 ?4 \9 y, u\" {& C& H\" q  ^
    
24. for c_ in range(c+1):
    1 P8 _# p, `# Y+ w
25.     for b_ in range(b+1):
    ( D8 [- c9 v. ]2 ?* y/ B
26.         if st[0][b_][c_]:
    ! K4 }4 n' |\" G0 l+ L  x
27.             print(c_,end=' '): S- [# P4 o! [4 h9 ^
    
28.             break

复制代码

3 M" S. e5 J* ~8 s