python 解决母亲的奶牛问题

2744557306

题目描述】

7 `. E" v9 e" g7 e5 ]4 f        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
; s' m7 M$ ^: o" o* Q" x
【输入格式】
4 n+ e: i! g5 m6 z
- V/ o8 ^; J1 {        共一行，包含三个整数 A,B,C。

1 T0 P4 q& v9 t, v& f  e) e, e3 y【输出格式】

8 H8 J( Z" N3 G: y        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
* \1 X* M& ^" b& q
$ U, ?- G& C4 {+ {+ Q1 L【数据范围】

6 G; k6 X3 t4 C# v3 Y- ~        1≤A,B,C≤20
2 V( P# P8 L( [1 W; U
2 Z6 X8 P8 P: n' m6 Y【输入样例】
0 {) Y2 x0 Z+ P1 \0 k
$ L. a( p% x  m/ y8 9 10
0 S- j# q  _7 E9 @0 v【输出样例】
3 t  k% Q! M, D) W7 v& @
2 @$ y5 x9 P9 @2 L. e9 g- M1 2 8 9 10
【解题思路】

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

1. from collections import *: ?% C% J, Q. e1 b0 G+ T
   
2. a,b,c = map(int,input().split())
   8 m! f2 E5 Y7 L) l: c+ J( p
3. n = 22) p5 p, O$ O8 \2 o% s3 t! Q8 w
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   + G+ X6 z6 E4 F5 W1 S
5. 
   4 W: P5 J% g+ [6 }; Z
6. q = deque()! N. X# y- p  w! v7 i  y% B* L' s
   
7. def ins(a_,b_,c_):. Z9 Z, n# y  }9 J
   
8.     global q+ n# u, L) P# H
   
9.     if st[a_][b_][c_]:return
   8 x* l1 Y( x* w- v7 Q
10.     q.append([a_,b_,c_])
    + m: |( b' }2 l$ W/ {
11.     st[a_][b_][c_]=11 j- l\" N% W$ X7 Z( T\" w
    
12. def bfs():\" [8 |+ m& g4 i& Y\" {
    
13.     q.append([0,0,c])
    . B0 O9 i5 i/ _, D+ j
14.     st[0][0][c]=1+ }8 ~: a$ h- E. G* t* S$ ?: _5 \
    
15.     while q:: B+ o$ l8 L5 k
    
16.         a_,b_,c_ = q.popleft()
    ) |. y/ n, P0 d! \5 r% V, l4 s
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )$ t5 P! i( g& f# J3 K! H1 Z$ G
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ) U2 b) Y% j: i9 _+ `6 q$ x
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    + \4 W/ M7 O, S2 p* z
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    * C! |' l+ ?8 [
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    9 j( j: l$ A+ H7 M1 U+ [/ E* l
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )) z+ O& m- K+ |: I
    
23. bfs()& o; u* S! d2 Y& U
    
24. for c_ in range(c+1):
    6 L2 ^( f8 h' ?  ~) J7 S
25.     for b_ in range(b+1):
    2 a! y4 {0 r+ W
26.         if st[0][b_][c_]:; L. p# ?, W7 r8 c
    
27.             print(c_,end=' '); t1 p7 f2 [/ v# |. G8 H* X
    
28.             break

复制代码

2 d6 o' }6 X; R9 n% p) h6 U