python 解决母亲的奶牛问题

2744557306

题目描述】

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

3 R( K! R5 Y4 x9 Y- u$ j$ Y【输入格式】

: ~' g  n5 s5 Q* e        共一行，包含三个整数 A,B,C。
% `! y' {; S3 s' f* ^3 s
【输出格式】

        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

- y+ D& I" C* W! G" j【数据范围】
( i5 T1 j0 L, D5 e* [) s. x2 H" k1 n2 f2 t
; @5 a  \' J$ Y; O2 O2 o2 X        1≤A,B,C≤20
0 A8 x' K" I% E1 z
+ a; `& h8 P* j8 F, m【输入样例】

8 9 10
【输出样例】

1 p# \+ J( F  \7 r7 K6 r1 2 8 9 10
" U$ I' L+ |% u9 y 【解题思路】

$ M3 K3 B0 j, a0 ?1 H; N6 [# M4 `        BFS简答模拟一下倒牛奶的过程。

1. from collections import *4 @- A# Y) H3 O9 y$ |
   
2. a,b,c = map(int,input().split())0 l4 X/ D% j: N* r
   
3. n = 22$ X. q- ~# B  j' }( W
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]& t* k) L' W, b, p
   
5. 
   3 s5 F4 t' b' o* |6 I8 y# A* ^1 S\" `
6. q = deque()
   7 ?& T- q% Y( h6 d2 u9 a
7. def ins(a_,b_,c_):
   5 c* c% ~  P3 }. [8 Z' b
8.     global q
   9 T$ E' G( p2 ~, `* w8 g- N
9.     if st[a_][b_][c_]:return
   ' g( D, O; [6 K, v
10.     q.append([a_,b_,c_])
    ; w& x0 `2 b# n8 N2 T# P# m; B5 \, f
11.     st[a_][b_][c_]=12 ~6 N/ s/ A. y& o+ j
    
12. def bfs():
    ) Q( J7 v. O0 Q  C) i
13.     q.append([0,0,c])
    ' w# s  v: k6 A5 S\" \$ k. d% f
14.     st[0][0][c]=1
    6 |  q$ w  _3 |  c
15.     while q:
    $ S0 Y5 }* O# c8 k5 O2 E' e* u
16.         a_,b_,c_ = q.popleft(). g9 Z) ?% R0 K4 c, D# r, E( q0 G
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )) D% P6 J  H7 ], M2 M
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )* @, ^3 V6 {% B/ }+ `; D
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )  N9 p\" Q. T# ^
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )9 n. L9 c$ m0 l% j1 [$ Q
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )) i/ o\" V  I; o( v  q0 b. q
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )/ s4 _, U7 x: k2 {
    
23. bfs()
    % m( l# A+ k% C1 W& i; a0 a
24. for c_ in range(c+1):: n7 [1 b2 t8 Q) \2 B
    
25.     for b_ in range(b+1):5 \8 n- [4 d3 q7 q! x
    
26.         if st[0][b_][c_]:
    / k* x) h! c* x/ I1 N8 @# E
27.             print(c_,end=' '): c- P6 C& U( j& Y6 k/ _! q/ ]
    
28.             break

复制代码