python 解决母亲的奶牛问题

2744557306

题目描述】

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

8 N$ I- w' B1 R) m3 W【输入格式】
4 }5 B  q3 t; W. ?5 j
        共一行，包含三个整数 A,B,C。
8 ~+ z2 W4 {0 G  x; o0 {6 g
* V7 L4 `1 \! C; k4 h: V【输出格式】

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

【数据范围】
0 U! i' D; u. v! Z4 T6 t2 L
2 V! M% j  ~/ P1 s; _3 z5 ?        1≤A,B,C≤20

" B! |( E; h* f【输入样例】

8 O3 b- H* J6 Y6 I* }3 g, j8 9 10
& L* o5 S+ C. T) n【输出样例】

1 2 8 9 10
9 l# b! A/ g) B2 ~1 E8 j 【解题思路】
$ L4 [0 j' I8 Q/ L* Z7 `
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *# u+ Q5 Y' z$ G2 p) I$ o
   
2. a,b,c = map(int,input().split())/ ~, b$ i6 r+ M; A' f
   
3. n = 22
   # W0 u4 ~9 r- k# I
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]9 E# o# `- C2 `/ u
   
5. 
   5 f4 S3 ~/ K- s( Q' [6 }8 F
6. q = deque()
   ) n, C' Z7 d- n: I
7. def ins(a_,b_,c_):, a7 U2 e\" }+ P9 u, |% J' y
   
8.     global q$ n$ `, u8 z0 o
   
9.     if st[a_][b_][c_]:return% E: a2 f: A6 p1 X0 r/ _
   
10.     q.append([a_,b_,c_])+ E- F4 s- y$ o
    
11.     st[a_][b_][c_]=1+ Y0 V! `4 C  R; h2 @5 w
    
12. def bfs():* K! P3 P7 ^\" m# z8 G' Q
    
13.     q.append([0,0,c]); k4 p2 F5 M% F# ?. h/ ]
    
14.     st[0][0][c]=1$ s/ `+ H5 N- _* w( W5 e
    
15.     while q:
    1 b\" S6 m0 o- |0 L* H: M4 `1 W
16.         a_,b_,c_ = q.popleft()
    7 `5 N; p; }/ b
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )' w( A0 v9 I' u$ @, Q, h) d: }
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )1 R( Y3 J9 j7 p9 m* c
    
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ ): [% V3 [2 @- {! K9 k
    
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )- Z4 k6 I$ ], ]8 Q, e8 u+ r
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    / a) e+ c1 Q$ ~/ m% D3 c0 b: I2 W$ G
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )$ k  i; J+ i5 C9 w+ w
    
23. bfs()  _% K$ {7 C% f5 l
    
24. for c_ in range(c+1):7 r4 Z- R8 B5 S$ C7 ?
    
25.     for b_ in range(b+1):/ _- T: M! {: l, [. R& P
    
26.         if st[0][b_][c_]:$ L4 i) v0 y/ T3 S5 r9 j1 A
    
27.             print(c_,end=' ')
    ; k* x2 Z1 R/ w  L\" C9 G
28.             break

复制代码