- 在线时间
- 480 小时
- 最后登录
- 2026-6-1
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7823 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2934
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1174
- 主题
- 1189
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
题目描述】4 v- x# C0 Z0 [* ~
+ |* o7 X8 C3 H
农夫约翰有三个容量分别为 A,B,C 升的挤奶桶。最开始桶 A 和桶 B 都是空的,而桶 C 里装满了牛奶。有时,约翰会将牛奶从一个桶倒到另一个桶中,直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。这一过程中间不能有任何停顿,并且不会有任何牛奶的浪费。请你编写一个程序判断,当 A 桶是空的时候,C桶中可能包含多少升牛奶,找出所有的可能情况。+ G7 s/ @$ t1 V' C! i1 I1 ^
- w; B6 g# @4 v- L% q F1 l% P8 O7 {【输入格式】: f4 a8 B& n+ C
0 w( c8 C: R. I 共一行,包含三个整数 A,B,C。
" D4 w2 w2 Y" w' h) K
% V5 c( m. W7 }8 @( U【输出格式】6 Z* @: L- y" i6 P$ b* J
( O: ]7 `+ N4 {( j/ V n 共一行,包含若干个整数,表示 C 桶中牛奶存量的所有可能情况,请将这些数字按升序排列。2 Y7 k( H+ d$ C* b" a" w6 x# R* w2 F
2 K, z' i+ u0 a. j; c【数据范围】
+ ^% b2 D' q* I: e* K* t- n( d8 b7 `+ f% {4 f6 @. ?
1≤A,B,C≤20
8 V2 Z6 ?. B% F) L! z" \
; d9 w3 E6 ~: w3 e% w2 q3 v【输入样例】
1 w7 U9 n1 M1 b6 p& s3 R' b* j, S/ Z: M
8 9 10% B) o; |4 k# a( f. ?7 \
【输出样例】* h7 l" j, \+ s+ a' z8 {& q+ k2 [
2 {5 ^6 ^" @- i1 [8 j. Y8 x1 2 8 9 10
5 _; T" G1 Q( W& [7 B 【解题思路】
5 j+ L* u/ x1 l
, P S9 g! @$ C' q; j( o0 O 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_ )
6 a\" X/ n; j8 V: z% `$ A, ]3 Q( t J7 o - 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
复制代码
5 _1 y# V, s0 g0 m& w7 V |
zan
|