python 解决母亲的奶牛问题

2744557306

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

: O; f8 M8 s7 |4 }9 |* q- Q【输入格式】
5 ~% L  S; p( b! _: F
        共一行，包含三个整数 A,B,C。
1 w6 y! Q; |# v) {
7 J9 |& W" t% d6 H! L1 X【输出格式】
5 N/ }* E3 Y9 P5 L$ l
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】

& T2 K, e1 v& h  V& [2 m7 ^" }, I: J        1≤A,B,C≤20
$ d3 f3 x4 e9 }
* T' m& `7 g: _【输入样例】
, i( P, |0 O9 t" l6 A
8 9 10
" V' v9 \3 b/ E  Q) G【输出样例】
- _; c0 U0 S' Y$ j& ]
5 @+ O4 V' f1 _: ]( j- _1 2 8 9 10
【解题思路】
# w6 Z7 E3 ?$ M; h9 r
8 r+ Q6 O$ f1 z% V1 |2 X- b        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   : S1 ]/ m6 m* R$ Z
2. a,b,c = map(int,input().split())3 h, U8 G' L; v# L% D
   
3. n = 22$ f1 T. x& \& M
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]\" p9 B3 l0 S/ Q, i$ d0 W+ z
   
5. 6 i. l1 }! Z  k4 p\" K! b4 T6 v- O
   
6. q = deque()0 T- D/ k8 m/ p* N% Q0 [
   
7. def ins(a_,b_,c_):* w\" I4 G! I3 U/ u9 f, g
   
8.     global q
   6 ~! c- ]\" }) G  B
9.     if st[a_][b_][c_]:return/ K. g* H/ t  i; D
   
10.     q.append([a_,b_,c_])
    & u3 I$ w0 W8 B/ {2 U4 y* g
11.     st[a_][b_][c_]=15 |; R0 v) o8 O- p4 f
    
12. def bfs():
    0 a\" {4 ~) E3 ~, o
13.     q.append([0,0,c])
    ( Z1 a' ?& y! [# G- Z
14.     st[0][0][c]=1
    # k) q1 \3 R9 r& ]* }
15.     while q:
    ! P+ F$ c* i; A% A. F1 C/ ?  |
16.         a_,b_,c_ = q.popleft()' b+ S& _  w& _0 w
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )) f: `$ J- Q: |- p
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    & d- c. q  C! S$ [: b
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
      x1 n5 m6 v7 I: K\" W
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )* v$ b' B/ Q# Z* C7 }3 h* M; o0 c
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    3 I2 E+ B2 s& C/ L1 R7 x
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    9 N. h8 F' z& m2 o$ I
23. bfs()( y  X\" v\" H+ A  m8 s4 d; ~
    
24. for c_ in range(c+1):
    & ?' a) s& b1 Y
25.     for b_ in range(b+1):% K( ]; o5 l4 h: B5 Y% O8 u
    
26.         if st[0][b_][c_]:, H( K/ f8 M1 z
    
27.             print(c_,end=' ')9 @5 z! m4 O- @; P8 e) T
    
28.             break

复制代码

( b2 b% P# I/ Z7 r, Y/ O