📄 usaco 1_4_4 mother's milk 题解_leokan的blog.mht
字号:
/* pour from bucket "from" to bucket "to" */
State
pour(State s, int from, int to)
{
int amt;
amt =3D s.a[from];
if(s.a[to]+amt > cap[to])
amt =3D cap[to] - s.a[to];
s.a[from] -=3D amt;
s.a[to] +=3D amt;
return s;
}
void
search(State s)
{
int i, j;
if(seen[s.a[0]][s.a[1]][s.a[2]])
return;
seen[s.a[0]][s.a[1]][s.a[2]] =3D 1;
if(s.a[0] =3D=3D 0) /* bucket A empty */
canget[s.a[2]] =3D 1;
for(i=3D0; i<3; i++)
for(j=3D0; j<3; j++)
search(pour(s, i, j));=20
}
void
main(void)
{
int i;
FILE *fin, *fout;
char *sep;
fin =3D fopen("milk3.in", "r");
fout =3D fopen("milk3.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d %d %d", &cap[0], &cap[1], &cap[2]);
search(state(0, 0, cap[2]));
sep =3D "";
for(i=3D0; i<=3Dcap[2]; i++) {
if(canget[i]) {
fprintf(fout, "%s%d", sep, i);
sep =3D " ";
}
}
fprintf(fout, "\n");
exit(0);
}
</STRONG></PRE>
<P><STRONG>Ran Pang from Canada sends this non-recursive DP =
solution:=20
</STRONG></P><PRE><STRONG>#include<stdio.h>
int m[21][21][21];
int poss[21];
int A, B, C;
int main(void) {
int i,j,k;
int flag;
FILE* in=3Dfopen("milk3.in","r");
fscanf(in, "%d %d %d",&A, &B, &C);
fclose(in);
for(i=3D0;i<21;i++)
for(j=3D0;j<21;j++)
for(k=3D0;k<21;k++)
m[i][j][k]=3D0;
for(i=3D0;i<21;i++)
poss[i]=3D0;
m[0][0][C]=3D1;
for(flag=3D1;flag;) {
flag=3D0;
for(i=3D0;i<=3DA;i++)
for(j=3D0;j<=3DB;j++)
for(k=3D0;k<=3DC;k++) {
if(m[i][j][k]) {
if(i=3D=3D0) poss[k]=3D1;
if(i) {
if(j<B) {
if(B-j>=3Di) {
if( m[0][j+i][k]=3D=3D0) {
m[0][j+i][k]=3D1;
flag=3D1;
}
} else {
if( m[i-(B-j)][B][k] =3D=3D 0) {
m[i-(B-j)][B][k] =3D1;
flag=3D1;
}
}
}
if(k<C) {
if(C-k>=3Di) {
if( m[0][j][k+i]=3D=3D0) {
m[0][j][k+i]=3D1;
flag=3D1;
}
}
else {
if( m[i-(C-k)][j][C] =3D=3D 0) {
m[i-(C-k)][j][C] =3D1;
flag=3D1;
}
}
}
}
if(j) {
if(i<A) {
if(A-i>=3Dj) {
if( m[i+j][0][k]=3D=3D0) {
m[i+j][0][k]=3D1;
flag=3D1;
}
} else {
if( m[A][j-(A-i)][k] =3D=3D 0) {
m[A][j-(A-i)][k] =3D1;
flag=3D1;
}
}
}
if(k<C) {
if(C-k>=3Dj) {
if( m[i][0][k+j]=3D=3D0) {
m[i][0][k+j]=3D1;
flag=3D1;
}
} else {
if( m[i][j-(C-k)][C] =3D=3D 0) {
m[i][j-(C-k)][C] =3D1;
flag=3D1;
}
}
}
}
if(k) {
if(i<A) {
if(A-i>=3Dk) {
if( m[i+k][j][0]=3D=3D0) {
m[i+k][j][0]=3D1;
flag=3D1;
}
} else {
if( m[A][j][k-(A-i)] =3D=3D 0) {
m[A][j][k-(A-i)] =3D1;
flag=3D1;
}
}
}
if(j<B) {
if(B-j>=3Dk) {
if( m[i][j+k][0]=3D=3D0) {
m[i][j+k][0]=3D1;
flag=3D1;
}
} else {
if( m[i][B][k-(B-j)] =3D=3D 0) {
m[i][B][k-(B-j)] =3D1;
flag=3D1;
}
}
}
}
} =20
}
}
{
FILE* out=3Dfopen("milk3.out", "w");
for(i=3D0;i<21;i++) {
if(poss[i]) {
fprintf(out,"%d",i);
i++;
break;
}
}
for(;i<21;i++) {
if(poss[i]) {
fprintf(out, " %d", i);
}
}
fprintf(out,"\n");
}
return 0;
}
</STRONG></PRE>
<P><STRONG>Daniel Jasper from Germany writes: </STRONG></P>
<P><STRONG>Both other solutions (recursive and non-recursive) use =
a=20
3D-array to store the states, so that the memory usage is=20
O(N<SUP>3</SUP>). However a 2D Array and O(N<SUP>2</SUP>) would be =
enough=20
since a state is uniquely defined by the amount of milk in bucket =
B and C.=20
The amount of milk in bucket A is size-of-C minus amount-in-C =
minus=20
amount-in-B. This solution works with it, and is a little bit =
shorter=20
(though not more elegant): </STRONG></P><PRE><STRONG>#include =
<stdio.h>
int A, B, C;
int CB[21][21]; // All states
void readFile() {
FILE *f;
f =3D fopen("milk3.in", "r");
fscanf(f, "%d%d%d", &A, &B, &C);
fclose(f);
}
void writeFile() {
FILE *f; int i;
f =3D fopen("milk3.out", "w");
for(i =3D 0; i <=3D C; i++) {
if(CB[i][C - i] =3D=3D 1) {
if((i !=3D C-B) && (i !=3D 0)) fprintf(f, " ");
fprintf(f, "%d", i);
}
}
fprintf(f, "\n");
fclose(f);
}
// do brute-force search, c/b: current state
void search(int c, int b) {
int a;
if(CB[c][b] =3D=3D 1) return; // already searched
CB[c][b] =3D 1;
a =3D C-b-c; // calc amount in A
// do all moves:
// c->b
if(B < c+b) search(c - (B - b), B);
else search(0, c + b);
// b->c
if(C < c+b) search(C, b - (C - c));
else search(c + b, 0);
// c->a
if(A < c+a) search(c - (A - a), b);
else search(0, b);
// a->c
if(C < c+a) search(C, b);
else search(c + a, b);
// b->a
if(A < b+a) search(c, b - (A - a));
else search(c, 0);
// a->b
if(B < b+a) search(c, B);
else search(c, b + a);
}
=20
int main () {
readFile();
search(C, 0);
writeFile();
return 0;
}
</STRONG></PRE>
<P></P>
<P></P>
<P></P>
<P></P>
<P></P></DIV></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/97970a08cee73834e82488f8.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.3.3 Calf Flac =CC=E2=BD=E2', 'USACO 1.3.3 =
Calf Flac =
=CC=E2=BD=E2','/leokan/blog/item/ae3ec417efcb470dc83d6dd5.html'];
var post =3D [true,'=B8=DF=D6=D0 =C0=FA=CA=B7 =B1=D8=D0=DE=D2=BB =
=B8=DF=D2=BB =D6=AA=CA=B6=CA=E1=C0=ED =
=B9=C5=B4=FA=D6=D0=B9=FA=D6=C6=B6=C8 =
=B8=DF=D2=BB=C0=FA=CA=B7=CA=E1=C0=ED =
=B8=DF=D2=BB=C0=FA=CA=B7=B8=B4=CF=B0=D7=CA=C1=CF','=B8=DF=D6=D0 =
=C0=FA=CA=B7 =B1=D8=D0=DE=D2=BB =B8=DF=D2=BB =
=D6=AA=CA=B6=CA=E1=C0=ED...', =
'/leokan/blog/item/ddbf38fa49b4538d9f514651.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%201%2E4%2E4=
%20Mother%26%2339%3Bs%20Milk%20%CC%E2%BD%E2&item=3D97970a08cee73834e82488=
f8">=B8=FC=B6=E0>></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
}
if(RelatedDocData =3D=3D -1){ // not supported xhr
var script =3D document.createElement('script');
script.type =3D 'text/javascript';
script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%201%2E4%2E4%20Mother%26%2339%3Bs%20Mil=
k%20%CC%E2%BD%E2&item=3D97970a08cee73834e82488f8&t=3D' + new =
Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</SCRIPT>
<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>
var g_spAnnony=3Dtrue;
var g_read=3D[
=09
["viviandme","9f8a5f736f6d656f6e655102","_someone"],
=09
["z97s04","19547a39377330341702","z97s04"],
{}
];
g_read.length=3Dg_read.length-1;
var _rh1=3D"";
var _rh2=3D"";
function wrreader(){
_rh1 +=3D '<table width=3D"100%" ><tr>';
_rh2+=3D'<tr>';
if(g_spAnnony){
_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+=3D'<td> </td>';
if(g_read.length>0){
_rh1+=3D'<td align=3D"left" width=3D"12%">';
}else{
_rh1+=3D'<td align=3D"left" width=3D"100%">';
}
_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
_rh2+=3D'<td> </td>'
}
if(g_read.length=3D=3D0){
if(!g_spAnnony){
_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
_rh2+=3D'<td> </td>';
}
}else{
for(i=3D0,len=3Dg_read.length;i<len;i++){
_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -