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 *
/ ~4 t2 d# h) {: O4 d
a,b,c = map(int,input().split())1 B4 ?! K) f: U) g9 t\" N# D
n = 22
8 z6 Z: g' [& S$ o3 y% j# e4 A! }
st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]0 C0 s+ o+ R$ Y x7 z
\" B1 u\" |. K2 ]* }% z$ k
q = deque()8 s2 O9 p+ f3 ?1 ?6 r+ L% h E
def ins(a_,b_,c_):
3 R$ v/ I1 o; s: q2 R$ i
global q\" h% K3 w1 b5 x3 q. m+ V% l
if st[a_][b_][c_]:return+ R q U9 T& Z\" u# N
q.append([a_,b_,c_])
6 L9 f/ [( `0 D; @8 v7 z
st[a_][b_][c_]=1\" M& E8 @8 A/ r! b( B
def bfs():
+ ~9 G9 K9 s\" A4 M
q.append([0,0,c])
- f; C5 h) k5 v0 T1 E; L# A6 k
st[0][0][c]=1
7 c6 l; z8 l6 b: ?. i& l
while q:6 z' M5 z3 X, B1 j
a_,b_,c_ = q.popleft()
8 i* T: V# a+ m3 t+ c4 t
ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
; n ]3 L; w$ J8 J: K
ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
! S. v# x# g5 X3 }$ [6 e
ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )$ r1 F2 H; u, G% G0 [, ~
ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )/ R1 V% z g\" ~\" I- V% P: h
ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
( C6 o! A/ v3 i
bfs()
. X1 c* m0 u2 \) m: d
for c_ in range(c+1):
4 _7 U# [\" S5 N+ v- d: d+ X N
for b_ in range(b+1):
1 W' J6 I; q+ Y+ X3 b
if st[0][b_][c_]:2 d, w$ F8 R# O0 _
print(c_,end=' ')! l1 K+ H0 G1 i; B7 c
break