📄 usaco 1_4_4 mother's milk 题解_leokan的blog.mht
字号:
<DIV class=3Dt_msgfont>
<P>Mother's Milk<BR><BR>Farmer John has three milking buckets of =
capacity=20
A, B, and C liters. Each of the numbers A, B, and C is an integer =
from 1=20
through 20, inclusive. Initially, buckets A and B are empty while =
bucket C=20
is full of milk. Sometimes, FJ pours milk from one bucket to =
another until=20
the second bucket is filled or the first bucket is empty. Once =
begun, a=20
pour must be completed, of course. Being thrifty, no milk may be =
tossed=20
out. <BR><BR>Write a program to help FJ determine what amounts of =
milk he=20
can leave in bucket C when he begins with three buckets as above, =
pours=20
milk among the buckets for a while, and then notes that bucket A =
is empty.=20
<BR><BR>PROGRAM NAME: milk3<BR>INPUT FORMAT<BR>A single line with =
the=20
three integers A, B, and C. <BR><BR>SAMPLE INPUT (file milk3.in) =
<BR>8 9=20
10<BR><BR>OUTPUT FORMAT<BR>A single line with a sorted <SPAN =
class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t of all the possible =
amounts of milk=20
that can be in bucket C when bucket A is empty. <BR><BR>SAMPLE =
OUTPUT=20
(file milk3.out)<BR>1 2 8 9 10<BR><BR>SAMPLE INPUT (file milk3.in) =
<BR>2 5=20
10<BR><BR>SAMPLE OUTPUT (file milk3.out)<BR>5 6 7 8 9=20
10<BR><BR><BR><BR>Mother's =
Milk<BR><BR>=C4=B8=C7=D7=B5=C4=C5=A3=C4=CC<BR><BR>=D2=EB by=20
=
Leontea<BR><BR>=C5=A9=C3=F1=D4=BC=BA=B2=D3=D0=C8=FD=B8=F6=C8=DD=C1=BF=B7=D6=
=B1=F0=CA=C7A,B,C=C9=FD=B5=C4=CD=B0=A3=ACA,B,C=B7=D6=B1=F0=CA=C7=C8=FD=B8=
=F6=B4=D31=B5=BD20=B5=C4=D5=FB=CA=FD=A3=AC=D7=EE=B3=F5=A3=ACA=BA=CDB=CD=B0=
=B6=BC=CA=C7=BF=D5=B5=C4=A3=AC=B6=F8C=CD=B0=CA=C7=D7=B0=C2=FA=C5=A3=C4=CC=
=B5=C4=A1=A3=D3=D0=CA=B1=A3=AC=D4=BC=BA=B2=B0=D1=C5=A3=C4=CC=B4=D3=D2=BB=B8=
=F6=CD=B0=B5=B9=B5=BD=C1=ED=D2=BB=B8=F6=CD=B0=D6=D0=A3=AC=D6=B1=B5=BD=B1=BB=
=B9=E0=CD=B0=D7=B0=C2=FA=BB=F2=D4=AD=CD=B0=BF=D5=C1=CB=A1=A3=B5=B1=C8=BB=C3=
=BF=D2=BB=B4=CE=B9=E0=D7=A2=B6=BC=CA=C7=CD=EA=C8=AB=B5=C4=A1=A3=D3=C9=D3=DA=
=BD=DA=D4=BC=A3=AC=C5=A3=C4=CC=B2=BB=BB=E1=D3=D0=B6=AA=CA=A7=A1=A3<BR>=D0=
=B4=D2=BB=B8=F6=B3=CC=D0=F2=C8=A5=B0=EF=D6=FA=D4=BC=BA=B2=D5=D2=B3=F6=B5=B1=
A=CD=B0=CA=C7=BF=D5=B5=C4=CA=B1=BA=F2=A3=ACC=CD=B0=D6=D0=C5=A3=C4=CC=CB=F9=
=CA=A3=C1=BF=B5=C4=CB=F9=D3=D0=BF=C9=C4=DC=D0=D4=A1=A3<BR><BR>PROGRAM=20
NAME: milk3<BR><BR>INPUT =
FORMAT<BR><BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=C0=A8=C8=FD=B8=F6=D5=FB=
=CA=FDA,B=BA=CDC=A1=A3<BR><BR>SAMPLE=20
INPUT (file milk3.in)<BR><BR>8 9 10<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=C1=D0=B3=F6=B5=B1A=CD=B0=CA=C7=
=BF=D5=B5=C4=CA=B1=BA=F2=A3=ACC=CD=B0=C5=A3=C4=CC=CB=F9=CA=A3=C1=BF=B5=C4=
=CB=F9=D3=D0=BF=C9=C4=DC=D0=D4=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
milk3.out)<BR><BR>1 2 8 9 10<BR><BR>SAMPLE INPUT (file milk3.in) =
<BR><BR>2=20
5 10<BR><BR>SAMPLE OUTPUT (file milk3.out)<BR><BR>5 6 7 8 9 10</P>
<P>`</P>
<P>`</P>
<P>`</P>
<P>`</P>
<P><STRONG>USACO 1.4.4 Mother's =
Milk<BR>19=B4=CEAC=A1=A3</STRONG></P>
<P><STRONG>TASK: milk3<BR>LANG: PASCAL</STRONG></P>
<P><STRONG>Compiling...<BR>Compile: OK</STRONG></P>
<P><STRONG>Executing...<BR> Test 1: =
TEST OK=20
[0 secs]<BR> Test 2: TEST OK [0=20
secs]<BR> Test 3: TEST OK [0=20
secs]<BR> Test 4: TEST OK [0=20
secs]<BR> Test 5: TEST OK [0=20
secs]<BR> Test 6: TEST OK [0=20
secs]<BR> Test 7: TEST OK [0=20
secs]<BR> Test 8: TEST OK [0=20
secs]<BR> Test 9: TEST OK [0=20
secs]<BR> Test 10: TEST OK [0=20
secs]</STRONG></P>
<P><STRONG>All tests OK.<BR>Your program ('milk3') produced all =
correct=20
answers! This is your<BR>submission #19 for this problem.=20
Congratulations!</STRONG></P>
<P><STRONG>Here are the test data inputs:</STRONG></P>
<P><BR><STRONG>------- test 1 -------<BR>2 5 10<BR>------- test 2=20
-------<BR>20 20 20<BR>------- test 3 -------<BR>5 11 =
15<BR>------- test 4=20
-------<BR>2 12 20<BR>------- test 5 -------<BR>19 4 11<BR>------- =
test 6=20
-------<BR>5 11 13<BR>------- test 7 -------<BR>3 20 20<BR>------- =
test 8=20
-------<BR>7 16 20<BR>------- test 9 -------<BR>20 10 9<BR>------- =
test 10=20
-------<BR>7 12 18<BR>----------------------</STRONG></P>
<P><STRONG>Keep up the good work! </STRONG></P>
=
<P><STRONG>=D6=AE=CB=F9=D2=D4=D5=E2=C3=B4=B6=E0=B4=CE=CC=E1=BD=BB=B2=C5ac=
=CA=C7=D2=F2=CE=AA=D3=D0=CE=D2=CE=B4=CF=EB=B5=BD=B5=C4=B4=ED=CE=F3=B2=BB=CB=
=AC=A3=AC=C8=BB=BA=F3=B5=BC=D6=C2=D0=C4=C7=E9=B2=BB=CC=AB=BA=C3=A3=AC=D7=D4=
=BC=BA=B2=BB=B5=F7=CA=D4=D6=B1=BD=D3=CC=E1=BD=BB=C8=C3usaco=B2=EE=B4=ED=A1=
=A3</STRONG></P>
=
<P><STRONG>=D5=E2=B4=CE=B5=C4=B3=CC=D0=F2=B0=B4=D5=D5=C0=CF=CA=A6=B5=C4=D2=
=AA=C7=F3=CB=F5=BD=F8=C1=CB...=B8=D0=BE=F5=BA=CD=D2=D4=C7=B0=B2=EE=B1=F0=B2=
=BB=B4=F3=A3=AC=B2=BB=B9=FD=BE=CD=CA=C7=B6=E0=B0=B4=B4=CEtab=C2=EF=A3=AC=D2=
=B2=C3=BB=CA=B2=C3=B4=D2=AA=BD=F4=B5=C4=A1=A3</STRONG></P>
=
<P><STRONG>=D2=D4a=A3=ACb=CD=B0=B5=C4=C8=DD=C1=BF=D7=F7=CE=AA=D7=B4=CC=AC=
=A3=AC=D4=F2c=3D=D7=DC=C1=BF-a-b=A3=AC=C3=B6=BE=D9=B8=F7=D6=D6=C7=E3=B5=B9=
=D7=B4=BF=F6=A3=AC=BC=C7=C2=BC=D6=D8=B8=B4=B3=F6=CF=D6=B5=C4=D7=B4=BF=F6=A3=
=AC=C8=E7=B9=FBa=3D0=BE=CD=BC=C7=C2=BCc=B5=C4=D6=B5=D7=F7=CE=AA=B4=F0=B0=B8=
=A1=A3</STRONG></P>
=
<P><STRONG>=CE=B4=CF=EB=B5=BD=B5=C4=B4=ED=CE=F3=CA=C7=B3=CC=D0=F2=D6=D0=D4=
=CB=D0=D0=D7=C5=A3=AC=B7=A2=CF=D6c=CE=AA=B8=BA=CA=FD=C1=CB=A3=AC=C8=BB=BA=
=F3=D4=DA=B3=CC=D0=F2=D6=D0=BC=D3=D2=BB=BE=E4if c<0 then=20
=
exit=A3=AC=D7=F7=CE=AAdfs=B5=C4=D6=D5=D6=B9=CC=F5=BC=FE=A3=AC=BE=CDac=C1=CB=
=A1=A3 </STRONG></P>
=
<P><STRONG>{<BR>TASK:milk3<BR>LANG:PASCAL<BR>}<BR>{$D-,L-,Y-,R-,S-,I-,Q-}=
<BR>program=20
milk3;<BR> =20
var<BR> =
hash:array[0..20,0..20]=20
of boolean;<BR> =
ans:array[0..20]=20
of boolean;<BR> =20
ta,tb,tc:integer;</STRONG></P>
<P><STRONG>procedure init;<BR> =20
begin<BR> =20
=
assign(input,'milk3.in');reset(input);<BR> &=
nbsp; =20
readln(ta,tb,tc);<BR> =20
=
fillchar(hash,sizeof(hash),false);<BR>  =
; =20
=
fillchar(ans,sizeof(ans),false);<BR> &=
nbsp;=20
close(input);<BR> end;<BR>procedure=20
pourab(a,b:integer;var x,y:integer);<BR> =20
begin<BR> if a>tb-b=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
x:=3Da-(tb-b);<BR> &=
nbsp; =20
=
y:=3Dtb;<BR> &=
nbsp;=20
=
end<BR> =
=20
else=20
=
begin<BR> &nbs=
p; =20
=
x:=3D0;<BR> &n=
bsp; =20
=
y:=3Db+a;<BR> =
=20
end;<BR> end;<BR>procedure =
pourac(a,b:integer;var=20
x,y:integer);<BR> =20
begin<BR> =20
x:=3D0;<BR> =20
y:=3Db;<BR> end;<BR>procedure =
pourba(a,b:integer;var=20
x,y:integer);<BR> =20
begin<BR> if b>ta-a=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
y:=3Db-(ta-a);<BR> &=
nbsp; =20
=
x:=3Dta;<BR> &=
nbsp;=20
=
end<BR> =
=20
else=20
=
begin<BR> &nbs=
p; =20
=
y:=3D0;<BR> &n=
bsp; =20
=
x:=3Db+a;<BR> =
=20
end;<BR> end;<BR>procedure =
pourbc(a,b:integer;var=20
x,y:integer);<BR> =20
begin<BR> =20
y:=3D0;<BR> =20
x:=3Da;<BR> end;<BR>procedure =
pourca(a,b:integer;var=20
x,y:integer);<BR> =20
var<BR> =20
c:integer;<BR> =20
begin<BR> =20
c:=3Dtc-a-b;<BR> if =
c>ta-a=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
x:=3Dta;<BR> &=
nbsp; =20
=
y:=3Db;<BR> &n=
bsp;=20
=
end<BR> =
=20
else=20
=
begin<BR> &nbs=
p; =20
=
x:=3Da+c;<BR> =
=20
=
y:=3Db;<BR> &n=
bsp;=20
end;<BR> end;<BR>procedure =
pourcb(a,b:integer;var=20
x,y:integer);<BR> =20
var<BR> =20
c:integer;<BR> =20
begin<BR> =20
c:=3Dtc-a-b;<BR> if =
c>tb-b=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
y:=3Dtb;<BR> &=
nbsp; =20
=
x:=3Da;<BR> &n=
bsp;=20
=
end<BR> =
=20
else=20
=
begin<BR> &nbs=
p; =20
=
y:=3Dc+b;<BR> =
=20
=
y:=3Da;<BR> &n=
bsp;=20
end;<BR> end;<BR>procedure=20
dfs(a,b:integer);<BR> =20
var<BR> =20
c:integer;<BR> =20
tempa,tempb:integer;<BR> =20
begin<BR> =20
c:=3Dtc-a-b;<BR> if =
c<0 then=20
exit;<BR> if hash[a,b] =
then=20
exit;<BR> =20
hash[a,b]:=3Dtrue;<BR> =
if a=3D0 then=20
ans[tc-b]:=3Dtrue;<BR> =
if=20
(a>0)and(b<tb)=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
pourab(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
end;<BR> if a>0=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
pourac(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
end;<BR> if =
(b>0)and(a<ta)=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
pourba(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
end;<BR> if b>0=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
pourbc(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
end;<BR> if =
a+b<>tc=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
pourca(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
=
pourcb(a,b,tempa,tempb);<BR> &nb=
sp; =20
=
dfs(tempa,tempb);<BR> &nbs=
p; =20
end;<BR> end;<BR>procedure =
work;<BR> =20
var<BR> =20
i:integer;<BR> =20
begin<BR> if tb>=3Dtc =
then=20
ans[0]:=3Dtrue;<BR> =20
dfs(0,0);<BR> =20
=
assign(output,'milk3.out');rewrite(output);<BR> &n=
bsp; =20
for i:=3D0 to 20=20
=
do<BR> =
if ans[i] then begin=20
=
write(i);ans[i]:=3Dfalse;break;end;<BR> &nbs=
p; =20
for i:=3Di to 20=20
=
do<BR> =
if ans[i] then write(' =
',i);<BR> =20
writeln;<BR> =20
close(output);<BR> =
end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P>
<P><STRONG>`</STRONG></P>
<P><STRONG>`</STRONG></P>
<P><STRONG>`</STRONG></P>
=
<P><STRONG>`USACO=B5=C4=B7=D6=CE=F6=A3=AC=D7=EE=BA=F3=D2=BB=D6=D6=B7=BD=B7=
=A8=BA=CD=CE=D2=CF=E0=CB=C6=A3=AC=B6=BC=CA=C7=D3=C3=C6=E4=D6=D02=CD=B0=D7=
=F7=CE=AA=D7=B4=CC=ACdfs=A3=AC=C4=C7=B8=F6DP=C3=B2=CB=C6=D0=A7=C2=CA=B2=BB=
=CC=AB=B8=DF......=B5=A5=B4=D3=B3=CC=D0=F2=D0=B4=B5=C4=B8=B4=D4=D3=B6=C8=C0=
=B4=BF=B4=BE=CD=B2=BB=BB=AE=CB=E3=C1=CB=A1=A3</STRONG></P>
<P><STRONG>`</STRONG></P>
<P><STRONG>We use a simple depth-first search to find all the =
possible=20
states for the three buckets, pruning the search by not =
researching from=20
states we've seen before.</STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#define MAX 20
typedef struct State State;
struct State {
int a[3];
};
int seen[MAX+1][MAX+1][MAX+1];
int canget[MAX+1];
State
state(int a, int b, int c)
{
State s;
s.a[0] =3D a;
s.a[1] =3D b;
s.a[2] =3D c;
return s;
}
int cap[3];
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -