python 解决母亲的奶牛问题

2744557306

题目描述】

4 i2 t! ^' e( ^5 X4 }* T        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
; E5 H9 `" Y! v5 |4 ^
' B1 G1 X" s" ~4 s. b/ m【输入格式】

. L0 Z% R6 R! d) _* Q, ]        共一行，包含三个整数 A,B,C。
7 z5 S' O7 U6 `1 M+ E
9 ^" o8 N5 o  Z# u( [【输出格式】
: M8 L* I# T1 D# s8 n  }
" ^2 j7 x4 Y5 ^: S! T6 m. u8 M        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】
8 V/ x- H; R0 l) ~, C5 O/ V# x
        1≤A,B,C≤20

! z* z( N6 j: k, c7 T& O【输入样例】

* c9 o2 Y( J0 b, |/ q  [- Q8 9 10
【输出样例】

1 V- b1 w+ N' f% ?# f1 2 8 9 10
) h4 H, I" D( p) N" y 【解题思路】
- C, r% `& F3 R- F: e9 a8 e2 t
  t5 n0 @( L9 K  ?3 x" e        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   7 a' f1 Y' s: n3 W4 G6 p+ f  r  \
2. a,b,c = map(int,input().split())
   - e3 E7 H# g0 u6 F
3. n = 22
   : \% K% B: |& y! q/ z
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   ) `. d& A, Y: b6 V- a
5. 
   ) y9 i, I$ ~  K) O
6. q = deque()
   / K: `) K6 s; K
7. def ins(a_,b_,c_):1 z; Q3 l  r6 E
   
8.     global q
   , a2 X' F( j* ]* E+ e. [
9.     if st[a_][b_][c_]:return! q! e# }' s4 B6 o5 n
   
10.     q.append([a_,b_,c_])
    ; H/ N3 H9 }: K  Z# M3 h
11.     st[a_][b_][c_]=1
    2 Q5 S0 N+ j4 j: t1 A: U# ]% U
12. def bfs():$ m/ }( V, p) b9 y
    
13.     q.append([0,0,c])
    : Z7 Z  `1 V+ A% `& p- F* |
14.     st[0][0][c]=1$ n' _- F. }' U' {/ W
    
15.     while q:
    ; h! }7 P! J9 P( o' n
16.         a_,b_,c_ = q.popleft()+ k6 q; S( a! |' ~3 _
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    7 u& V5 G5 D$ |2 D9 W8 A
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    ' U& W* C  w( |. Z2 f$ S' `
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )' A) n% O2 n; i
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    3 ]  f* l6 S\" @! V. s4 W$ E
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    9 D; v; Z+ b- Q1 x2 Z
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    * k- \- ~7 _) |* N8 Q
23. bfs()
    ) ^. M/ H+ R  _5 t
24. for c_ in range(c+1):3 L* w6 N( Z' M& @' ]# l8 x/ ~
    
25.     for b_ in range(b+1):4 K5 z/ o3 G1 x* @' z) Y: Y
    
26.         if st[0][b_][c_]:* |9 X4 h% k9 d) j
    
27.             print(c_,end=' ')
    9 }5 t% F7 `: `
28.             break

复制代码

' F* G( j9 q/ d" R5 q! z9 h$ I