python 解决母亲的奶牛问题

2744557306

题目描述】

: H: ^0 X; o4 r7 a5 u  [% H, R        农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的，而桶 C 里装满了牛奶。有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。请你编写一个程序判断，当 A 桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
4 m* f8 h+ d" z" U  Z
【输入格式】

( S) O: l7 C& L        共一行，包含三个整数 A,B,C。

! h9 T* ~7 W! d: x; ?6 [【输出格式】
3 y: g* P' b8 l0 e
        共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。
1 _+ e3 U- l' F5 H: G7 V
  y1 Z1 i- I! l$ [' d- q- C【数据范围】
/ f1 z( J7 I7 l" F6 W! `
0 V8 o% u( Z) A0 o- X0 `        1≤A,B,C≤20
8 Y# {; _' q! v
【输入样例】

  A. ?9 Z1 }4 r# u# @  n# g8 9 10
【输出样例】
% u; C- g( V8 R! x) I
) S' w9 G) `6 W" }2 h. ]; ]+ S1 2 8 9 10
2 k2 o+ s) M5 y6 X5 ]: J" s 【解题思路】

        BFS简答模拟一下倒牛奶的过程。

1. from collections import ** N3 W5 g- H8 `3 E: m& m/ K
   
2. a,b,c = map(int,input().split())
   * N, K\" u- i# \! V% y3 K% e. S  Z
3. n = 22
   ( H6 p- P3 s. g2 Y5 H+ g
4. st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]
   ) d6 k; u* t5 N
5. 
   \" h3 M! d, k, z& L0 f4 A
6. q = deque()% P( P3 A5 \- y3 N. _
   
7. def ins(a_,b_,c_):& G$ \1 z7 I: _
   
8.     global q% x2 D- ^9 N# @7 r# r
   
9.     if st[a_][b_][c_]:return
   6 m1 S, T# t7 \
10.     q.append([a_,b_,c_])
    3 Q5 q6 C9 x# Q0 h% d
11.     st[a_][b_][c_]=1
    % e5 d9 p7 ^: e
12. def bfs():
    + B+ n% f1 ~8 F& @
13.     q.append([0,0,c]): c$ K- W5 k8 w( K
    
14.     st[0][0][c]=1
    & d0 i9 l' i( a  ^7 `
15.     while q:0 n+ |9 m: n9 D
    
16.         a_,b_,c_ = q.popleft()' H5 X: y, {+ C; }8 N, s( D7 O+ Y
    
17.         ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ ); g& ~1 g2 U6 K
    
18.         ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
    $ a0 s$ `; U/ n: ~
19.         ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
    6 ^/ G; Q: {$ B2 Z  g: Z9 k
20.         ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
    1 _; d+ a0 Y* n
21.         ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
    % w0 U4 K% W. M7 d. l5 Y5 [  i
22.         ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) ); j, k8 N; G\" D: N9 _\" C6 o1 c
    
23. bfs()
    \" X* a  S7 U% U$ v, Z- n' r
24. for c_ in range(c+1):
    % j% h4 _  `, l5 I0 z% T
25.     for b_ in range(b+1):( }/ A% C3 ]\" p9 s+ f) o
    
26.         if st[0][b_][c_]:
    9 J* v( ?0 O% Q3 e: Y; W6 f3 ~
27.             print(c_,end=' ')
    $ B/ X1 W! d& i' g* w8 [8 S
28.             break

复制代码