python 解决母亲的奶牛问题

2744557306

题目描述】

& C. \( m5 w. b& c1 W$ ^        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
6 A) z0 F! n' G3 v$ i
( g& h5 J5 L: r' R【输入格式】
; n3 T' u: @& G# ^" j- x6 L$ i
        共一行，包含三个整数 A,B,C。
7 |3 w( ]) T: J# ^. n. p1 L
【输出格式】
8 J* A5 u& \; k% j. b0 q  ]
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

【数据范围】
2 y3 i/ s5 N6 G! H
$ {% k+ r. U% S: i        1≤A,B,C≤20
. G# p' n2 n. x' C  x3 N$ J; ^0 Y5 r
# s! `5 l# r5 v# g- s【输入样例】
# F# J3 s+ b, `) U3 v
8 9 10
3 Z& V5 `, S8 @* V5 h' w* p# r【输出样例】
0 R6 ^  C6 B# |0 m- E  S
1 2 8 9 10
/ W% w4 J8 O. n9 k. e- d8 q% P5 p 【解题思路】
3 m. [4 F) s8 q# r) H* [
# f1 j; L* j9 Y( k% d" L        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
     u( G8 @( d. e! J& [# q
2. a,b,c = map(int,input().split())
   - j0 R, D3 d( N: Z# j$ j1 ]  t
3. n = 22\" E  e/ K8 W( H1 Q1 u# n
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   6 y. J) U0 b, j7 Q, X
5. 
   ( k( q\" t% H* C/ X. U3 c6 w
6. q = deque()2 V3 n' W# z( I* |  z+ @
   
7. def ins(a_,b_,c_):
   $ y4 D) u  P8 h/ J3 _
8.     global q* N  H5 Q1 ~1 k! E* A
   
9.     if st[a_][b_][c_]:return% B$ ]/ e6 T; p
   
10.     q.append([a_,b_,c_])9 F* T\" S, j1 |& V) A
    
11.     st[a_][b_][c_]=1$ z* m3 \  `+ S( O9 \
    
12. def bfs():# n$ t$ y8 f/ A4 b8 D
    
13.     q.append([0,0,c])8 N5 T( I5 @( C3 H! w* S  g4 R
    
14.     st[0][0][c]=1
    / Q* `0 v/ O! |- M- o3 p
15.     while q:  e6 }/ l* c5 l! v! V7 B- |
    
16.         a_,b_,c_ = q.popleft()
    9 h8 D5 e\" L. e9 G6 z
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
    9 F\" G) y6 ?4 t2 l! N/ a' O
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) ); u2 Y+ A( M6 c! q
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ ). k: z/ O* E! p$ C2 k  i! p: Q
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    0 M6 P! ?5 R6 l8 B) @+ [
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )3 f- k$ t  ^/ _  k% i+ I
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )1 [- I3 q, F; K0 C( u+ j3 |
    
23. bfs()6 c9 b: G* F7 r# F0 }9 y' Q: @; L
    
24. for c_ in range(c+1):
    2 S- K4 x\" z8 Y' O
25.     for b_ in range(b+1):) ?0 V: p9 f) z# j9 H: R1 U
    
26.         if st[0][b_][c_]:
    ' ^  k9 R3 m2 c6 T, n
27.             print(c_,end=' ')
    - Y4 x6 |& _2 i3 G( H. Z
28.             break

复制代码

2 }( a3 z/ d( r) _