python 解决母亲的奶牛问题

2744557306

题目描述】

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

【输入格式】

& f5 v- Y2 n& R8 t        共一行，包含三个整数 A,B,C。

4 l! \" X" X% u0 a2 ?【输出格式】

2 u7 d% n9 }+ Q) `3 u        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

: g+ y4 y2 ?9 P7 O9 N【数据范围】

) e- O& T3 |3 H1 v: O        1≤A,B,C≤20

【输入样例】
/ N* g# @9 h7 ~
3 u$ Z! m* i3 D/ q  A2 z% {8 9 10
# m& n7 s  `/ @" x( C. W5 i【输出样例】
4 J2 f# @3 F! J' J5 z
1 2 8 9 10
+ w# n+ e) i/ F 【解题思路】
6 ^: K( T$ I- d, J; J5 I$ T5 U" ?  `) i
        BFS简答模拟一下倒牛奶的过程。

1. from collections import *
   : }: ^8 z; {* L* {
2. a,b,c = map(int,input().split())
   * N  |\" B\" u- t- e3 a6 v- v
3. n = 22  {9 q6 ]0 l3 E$ L* M\" X
   
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]: B' ^1 O! ]\" K2 D) n9 _
   
5. 
   # L7 _# l  a. J! \6 Y8 Q0 x/ i  I/ Z1 |
6. q = deque()7 q' i+ `- i& B5 B( i  R3 `
   
7. def ins(a_,b_,c_):
   ; ?6 C9 W' a3 L6 \
8.     global q
     V! [, f% M8 F2 O9 T
9.     if st[a_][b_][c_]:return
   7 @1 L' N, b% ?* H1 v& D% w4 @+ {
10.     q.append([a_,b_,c_])+ x: {! n6 k- V' K( N4 x; v: B3 C8 a
    
11.     st[a_][b_][c_]=1
    & F  h3 Y+ X5 S* ~5 T) F
12. def bfs():
    - P; N0 j. \: N% L/ a
13.     q.append([0,0,c])
    % l0 O+ V5 ]  ^+ x
14.     st[0][0][c]=1/ U7 U3 o7 N+ A7 ^- V) @
    
15.     while q:
    * F) R* j\" a$ o6 E\" e+ ~/ V$ z
16.         a_,b_,c_ = q.popleft()
    & Q- }  u5 Y  |/ \* v3 t. W9 a( N
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )2 c$ Z) |! H( n
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    . D  [/ P; h\" H' W6 B
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    / P! i2 c5 p$ h% Z
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )1 @3 E4 Q# n, b
    
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )0 C5 Q9 X% d3 k, b! [2 c
    
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
    2 O1 `; q: P% @5 c' _1 O) \: ^
23. bfs()- d8 |0 ]; l* x\" u+ F
    
24. for c_ in range(c+1):; s- ]$ @1 d) A( U: v; @7 ]- J
    
25.     for b_ in range(b+1):
    ! L  l6 w0 W- b. H0 J
26.         if st[0][b_][c_]:- Y4 F( W: H! V\" W/ R2 ]5 G
    
27.             print(c_,end=' ')
    6 r3 D- y3 m6 j* U- l
28.             break

复制代码

! {/ C/ i! R8 j' I+ B( z8 n