- 在线时间
- 478 小时
- 最后登录
- 2026-4-9
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7788 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2922
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1171
- 主题
- 1186
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】
- A8 ^, H: s1 Y; U% f
1 e% P3 ^% Q I; L) h6 _ 农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的,而桶 C 里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。请你编写一个程序判断,当 A 桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。0 x0 L6 v, e! @+ o' M
( z. G. E' P/ c5 G9 p( N/ ^. ^' c4 y+ W8 o【输入格式】
' h& V. r2 U* }' w: i( b- @2 ~: P1 d! z$ |% `: `$ W& i$ \
共一行,包含三个整数 A,B,C。
/ ?* ?8 V e) \: ^: h9 V0 W* V
9 v$ J3 S% \5 d( g: [" z) B: E【输出格式】
) Y H; o5 D3 ~% N8 @
" y+ N9 z. v$ ^# f! K" l 共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。8 I1 r) m6 W( s) S& e* L: A! E. L
" W+ U+ r" ^# u0 }% ]4 z4 T9 G: }0 |【数据范围】
! A0 Y1 h0 u! x& z* c2 ]( k+ m$ K' l+ `& k3 J
1≤A,B,C≤20
3 T! s( K& w3 G1 J, W/ I9 ]2 m& k% P% H. v6 Q
【输入样例】
5 o! S% V9 w9 J5 n. P4 e) c# v, Q+ Y6 G
8 9 107 z2 I6 B: _9 k( X) q( f* U, X0 m
【输出样例】
* s8 A4 k! E1 T& p* b5 m! X
9 H- }# \ Z3 F& ?1 2 8 9 103 [- l5 | d) a' ?; q
【解题思路】
4 t8 W$ _6 Y8 ^8 v, ~
0 A _5 Y+ t9 q* h BFS简答模拟一下倒牛奶的过程。- from collections import *8 A5 o8 t% m\" w4 w. }+ N# o* ^7 k, L
- a,b,c = map(int,input().split())7 E0 h5 ^4 A! T5 z9 Y
- n = 22% c1 \$ w1 l# k
- st = [[[0 for _ in range(n)] for _ in range(n)] for _ in range(n)]% P9 l# O/ V) K5 K2 p1 t
-
7 D Y4 |% z/ Y! `2 S7 ^ - q = deque()- V+ ~( x2 P# B) @8 _\" t
- def ins(a_,b_,c_):* h8 G1 o# C0 A: I r7 }
- global q0 Q3 d# ^7 F% u' b6 S; a5 Z
- if st[a_][b_][c_]:return
/ @5 d0 B3 L7 g% t0 V - q.append([a_,b_,c_])
& L, J( Q: V- ~\" O - st[a_][b_][c_]=1
8 @# c3 v* K, S' f' a3 g - def bfs():2 Q d) J- W. n: r* L2 O
- q.append([0,0,c])
. P5 S8 b: v' x! ?/ U J# v - st[0][0][c]=1
4 T0 D% D5 S% r3 o# J. A0 \; l/ J - while q:
' Z3 `! B( @* u6 U0 } - a_,b_,c_ = q.popleft(); A, h6 z\" ]1 q8 N! d
- ins( a_-min(a_,b-b_) , b_+min(a_,b-b_) , c_ )
. n. w* b. e# {% o& o - ins( a_-min(a_,c-c_) , b_ , c_+min(a_,c-c_) )
) N% a7 [8 H1 R2 O - ins( a_+min(b_,a-a_) , b_-min(b_,a-a_) , c_ )
\" s: J; @; z! u* w! E/ e8 ]2 E - ins( a_ , b_-min(b_,c-c_) , c_+min(b_,c-c_) )
^6 W2 J/ k6 R, n - ins( a_+min(c_,a-a_) , b_ , c_-min(c_,a-a_) )
1 ~; F7 h% u: S. w7 X. ^ - ins( a_ , b_+min(c_,b-b_) , c_-min(c_,b-b_) )
- R3 {: g6 B( ?% I( p$ L - bfs()
; V5 E$ b6 `* o - for c_ in range(c+1):
5 C\" I. h. y4 M C! K4 x - for b_ in range(b+1):9 |- Y$ I6 ^9 @/ |
- if st[0][b_][c_]:
5 M7 x# M9 E, \ u; p: c - print(c_,end=' ')
m! u' H; } {+ h3 z0 P: c - break
复制代码 + k2 G( K7 `9 O( `4 a, @
|
zan
|