python 解决母亲的奶牛问题

2744557306

题目描述】

+ {( i+ \; j4 |" f: u        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

. H2 W1 d) ?  f( ]  k7 \【输入格式】
3 M. O) E8 N  z5 a  f( _" I# ~$ e3 M
3 V) r0 ~9 g6 E% d+ T9 Z9 m        共一行，包含三个整数 A,B,C。

【输出格式】
5 m: k  V7 N8 `5 }
* L  e8 T! c) D        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

3 ~; G5 P9 ]& A. n; ?8 m" ~0 a【数据范围】
# Y% N& _1 u9 Y0 o) e$ ]
; Y" L; `4 u6 @; |        1≤A,B,C≤20
. a. C3 }0 m' u
【输入样例】
* L$ d% I* i  v/ Y0 P
8 9 10
【输出样例】

1 2 8 9 10
【解题思路】

        BFS简答模拟一下倒牛奶的过程。

1. from collections import *\" w  a6 z9 `% r2 ?% Z9 L
   
2. a,b,c = map(int,input().split())\" s7 g- D/ r9 _4 E+ j; m
   
3. n = 22$ F# m1 i: b: y0 S* h- y
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   / I( [7 R1 E( ], f( i
5. * g5 Z- ?+ d4 ^\" F9 b
   
6. q = deque()! [. O3 K0 s\" {3 i& C! Y$ z
   
7. def ins(a_,b_,c_):
   . @( r& m8 C1 K0 C1 R( Z
8.     global q
   $ L8 n4 p5 A- _7 v% a/ d- {$ J3 ]1 q
9.     if st[a_][b_][c_]:return/ j, ?2 ], F+ B. k0 I/ W
   
10.     q.append([a_,b_,c_])# J; }; e+ o3 @. W
    
11.     st[a_][b_][c_]=1
    \" J# H' J+ M) ~
12. def bfs():6 |9 V! s  V- v
    
13.     q.append([0,0,c])
    ( ^4 C5 c( t/ {2 A
14.     st[0][0][c]=14 q, a) I, n5 W: U$ r' }& P, I: q
    
15.     while q:
    4 {; p4 Y4 Z& [& Q9 p; T
16.         a_,b_,c_ = q.popleft()( `. I% U\" i2 G7 b2 D* Q
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    3 G/ K2 D0 K\" e( m8 I, W& m: H
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    7 M- N$ Y0 l; _1 k0 O+ H
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    - b8 ?  S8 {\" e7 W! _/ l/ j4 f
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )\" L8 D5 n* X  j, x
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )* E& `: K5 V  }0 T9 E- n\" g
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )6 r, }, O0 N8 N* |
    
23. bfs()2 m3 m+ v! F9 Y  a: L  a* ~
    
24. for c_ in range(c+1):
    1 s) t6 P. K( K: s
25.     for b_ in range(b+1):2 j- s, \6 \! o
    
26.         if st[0][b_][c_]:, F5 S\" g8 s  j9 E\" y: \
    
27.             print(c_,end=' ')
    ( H6 b\" A. l6 d7 M\" K6 s( X- ?# H
28.             break

复制代码

3 D6 g1 W! d4 r* b