python 解决母亲的奶牛问题

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2024-3-20 11:38 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

题目描述】

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

【输入格式】

      共一行，包含三个整数 A,B,C。

【输出格式】

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

【数据范围】

      1≤A,B,C≤20

【输入样例】

8 9 10
【输出样例】

1 2 8 9 10
【解题思路】

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

from collections import *
0 D. I* N/ _/ {- `# c9 H
a,b,c = map(int,input().split())' n' t+ ^' t) z( H! ?9 s
n = 226 {) D% y9 {# h. G1 t
st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)] O& p+ |( @' f2 B% c t
& }4 `5 Z8 J( k* n6 c' }
q = deque()
; a\" h; |9 `# D) I. e
def ins(a_,b_,c_):
, x: g$ n, l& a+ a/ n
global q& ~3 g1 O/ k, O0 }* {3 Q' @
if st[a_][b_][c_]:return
\" u! x! t3 g# _
q.append([a_,b_,c_])
) B% L. C2 U7 Z1 `1 S4 I3 j
st[a_][b_][c_]=1
! { c/ y$ p7 }/ G6 F
def bfs():
2 x3 J% J/ Y. f5 X
q.append([0,0,c])0 @ |7 h9 }7 n
st[0][0][c]=1
while q:\" S' |+ ?& ?: B' H3 A! h) S3 x4 Y
a_,b_,c_ = q.popleft() Y: k$ e5 ?0 f& x5 f& p7 a, A
ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
1 I# |7 p* O\" L- A3 w& D( \- j
ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )3 l6 q6 ^% u) c& Q. ?\" W5 d, K( _
ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ ): e. |' f+ X. j! O5 Q
ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )+ v; t7 n2 s9 v# U4 Z9 D) y/ S
ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )9 P$ U& T; U\" e- |5 w4 j
ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )7 f+ d/ x( ]3 H3 S' E
bfs()
9 p8 K8 }3 }) P0 @7 u
for c_ in range(c+1):
V% g2 J5 X! t- g\" x; H% m
for b_ in range(b+1):
7 o- u1 H\" e& B1 y7 j5 l# \, N
if st[0][b_][c_]:$ p\" a7 q9 e+ @! ?
print(c_,end=' ')
- Y2 K: y( K7 D\" s3 y
break