📄 usaco 3_2_4 feed ratios 题解_leokan的blog.mht
字号:
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 3.2.4 Feed Ratios =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
19:29</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.2.4 Feed Ratios</H2>
<DIV class=3Dt_msgfont>
<P>Farmer John feeds his cows only the finest mixture of cow food, =
which=20
has three components: Barley, Oats, and Wheat. While he knows the =
precise=20
mixture of these easily mixable grains, he can not buy that =
mixture! He=20
buys three other mixtures of the three grains and then combines =
them to=20
form the perfect mixture.</P>
<P>Given a set of integer ratios barley:oats:wheat, find a way to =
combine=20
them IN INTEGER MULTIPLES to form a mix with some goal ratio =
x:y:z.</P>
<P>For example, given the goal <TT><FONT =
face=3DNSimsun>3:4:5</FONT></TT>=20
and the ratios of three mixtures:</P><PRE>1:2:3
3:7:1
2:1:2</PRE>your program should find some minimum number of =
integer=20
units (the `mixture') of the first, second, and third mixture that =
should=20
be mixed together to achieve the goal ratio or print `NONE'. =
`Minimum=20
number' means the sum of the three non-negative mixture integers =
is=20
minimized.=20
<P>For this example, you can combine eight units of mixture 1, one =
unit of=20
mixture 2, and five units of mixture 3 to get seven units of the =
goal=20
ratio:</P><PRE>8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) =3D (21:28:35) =
=3D 7*(3:4:5)</PRE>
<P>Integers in the goal ratio and mixture ratios are all =
non-negative and=20
smaller than 100 in magnitude. The number of units of each type of =
feed in=20
the mixture must be less than 100. The mixture ratios are not =
linear=20
combinations of each other.</P>
<H3>PROGRAM NAME: ratios</H3>
<H3>INPUT FORMAT</H3>
<TABLE border=3D1>
<TBODY>
<TR>
<TD>Line 1:</TD>
<TD>Three space separated integers that represent the goal=20
ratios</TD></TR>
<TR>
<TD>Line 2..4:</TD>
<TD>Each contain three space separated integers that represent =
the=20
ratios of the three mixtures =
purchased.</TD></TR></TBODY></TABLE>
<H3>SAMPLE INPUT (file ratios.in)</H3><PRE>3 4 5
1 2 3
3 7 1
2 1 2</PRE>
<H3>OUTPUT FORMAT</H3>
<P>The output file should contain one line containing four =
integers or the=20
word `NONE'. The first three integers should represent the number =
of units=20
of each mixture to use to obtain the goal ratio. The fourth number =
should=20
be the multiple of the goal ratio obtained by mixing the initial =
feed=20
using the first three integers as mixing ratios.</P>
<H3>SAMPLE OUTPUT (file ratios.out)</H3><PRE>8 1 5 =
7</PRE><BR><BR><BR>Feed Ratios <BR>=CB=C7=C1=CF=B5=F7=C5=E4 <BR><BR>1998 =
ACM=20
Finals, Dan Adkins <BR><BR>=D2=EB by Felicia Crazy=20
=
<BR><BR>=C5=A9=B7=F2=D4=BC=BA=B2=B4=D3=C0=B4=D6=BB=D3=C3=B5=F7=C5=E4=B5=C3=
=D7=EE=BA=C3=B5=C4=CB=C7=C1=CF=C0=B4=CE=AA=CB=FB=B5=C4=C4=CC=C5=A3=A1=A3=CB=
=C7=C1=CF=D3=C3=C8=FD=D6=D6=D4=AD=C1=CF=B5=F7=C5=E4=B3=C9=A3=BA=B4=F3=C2=F3=
=A3=AC=D1=E0=C2=F3=BA=CD=D0=A1=C2=F3=A1=A3=CB=FB=D6=AA=B5=C0=D7=D4=BC=BA=B5=
=C4=CB=C7=C1=CF=BE=AB=C8=B7=B5=C4=C5=E4=B1=C8=A3=AC=D4=DA=CA=D0=B3=A1=C9=CF=
=CA=C7=C2=F2=B2=BB=B5=BD=D5=E2=D1=F9=B5=C4=CB=C7=C1=CF=B5=C4=A1=A3=CB=FB=D6=
=BB=BA=C3=B9=BA=C2=F2=C6=E4=CB=FB=C8=FD=D6=D6=BB=EC=BA=CF=CB=C7=C1=CF=A3=A8=
=CD=AC=D1=F9=B6=BC=D3=C9=C8=FD=D6=D6=C2=F3=D7=D3=D7=E9=B3=C9=A3=A9=A3=AC=C8=
=BB=BA=F3=BD=AB=CB=FC=C3=C7=BB=EC=BA=CF=A3=AC=C0=B4=B5=F7=C5=E4=CB=FB=B5=C4=
=CD=EA=C3=C0=CB=C7=C1=CF=A1=A3=20
<BR><BR>=B8=F8=B3=F6=C8=FD=D7=E9=D5=FB=CA=FD=A3=AC=B1=ED=CA=BE =
=B4=F3=C2=F3=A3=BA=D1=E0=C2=F3=A3=BA=D0=A1=C2=F3 =
=B5=C4=B1=C8=C0=FD=A3=AC=D5=D2=B3=F6=D3=C3=D5=E2=C8=FD=D6=D6=CB=C7=C1=CF=B5=
=F7=C5=E4 x=A3=BAy=A3=BAx =B5=C4=CB=C7=C1=CF=B5=C4=B7=BD=B7=A8=A1=A3 =
<BR><BR>=C0=FD=C8=E7=A3=AC=B8=F8=B3=F6=C4=BF=B1=EA=CB=C7=C1=CF=20
3=A3=BA4=A3=BA5 =
=BA=CD=C8=FD=D6=D6=CB=C7=C1=CF=B5=C4=B1=C8=C0=FD=A3=BA <BR><BR>1:2:3=20
=
<BR>3:7:1 <BR>2:1:2<BR>=C4=E3=B1=D8=D0=EB=B1=E0=B3=CC=D5=D2=B3=
=F6=CA=B9=D5=E2=C8=FD=D6=D6=CB=C7=C1=CF=D3=C3=C1=BF=D7=EE=C9=D9=B5=C4=B7=BD=
=B0=B8=A3=AC=D2=AA=CA=C7=B2=BB=C4=DC=D3=C3=D5=E2=C8=FD=D6=D6=CB=C7=C1=CF=B5=
=F7=C5=E4=C4=BF=B1=EA=CB=C7=C1=CF=A3=AC=CA=E4=B3=F6=A1=B0NONE=A1=B1=A1=A3=
=A1=B0=D3=C3=C1=BF=D7=EE=C9=D9=A1=B1=D2=E2=CE=B6=D7=C5=C8=FD=D6=D6=CB=C7=C1=
=CF=B5=C4=D3=C3=C1=BF=A3=A8=D5=FB=CA=FD=A3=A9=B5=C4=BA=CD=B1=D8=D0=EB=D7=EE=
=D0=A1=A1=A3=20
=
<BR>=B6=D4=D3=DA=C9=CF=C3=E6=B5=C4=C0=FD=D7=D3=A3=AC=C4=E3=BF=C9=D2=D4=D3=
=C38=B7=DD=CB=C7=C1=CF1=A3=AC2=B7=DD=CB=C7=C1=CF2=A3=AC=BA=CD5=B7=DD=CB=C7=
=C1=CF3=A3=AC=C0=B4=B5=C3=B5=BD7=B7=DD=C4=BF=B1=EA=CB=C7=C1=CF=A3=BA =
<BR><BR>8*(1:2:3) +=20
1*(3:7:1) + 5*(2:1:2) =3D (21:28:35) =3D 7*(3:4:5)=20
=
<BR><BR>=B1=ED=CA=BE=CB=C7=C1=CF=B1=C8=C0=FD=B5=C4=D5=FB=CA=FD=A3=AC=B6=BC=
=CA=C7=D0=A1=D3=DA100=A3=A8=CA=FD=C1=BF=BC=B6=A3=A9=B5=C4=B7=C7=B8=BA=D5=FB=
=CA=FD=A1=A3=B1=ED=CA=BE=B8=F7=D6=D6=CB=C7=C1=CF=B5=C4=B7=DD=CA=FD=B5=C4=D5=
=FB=CA=FD=A3=AC=B6=BC=D0=A1=D3=DA100=A1=A3=D2=BB=D6=D6=BB=EC=BA=CF=CE=EF=B5=
=C4=B1=C8=C0=FD=B2=BB=BB=E1=D3=C9=C6=E4=CB=FB=BB=EC=BA=CF=CE=EF=B5=C4=B1=C8=
=C0=FD=D6=B1=BD=D3=CF=F2=BC=D3=B5=C3=B5=BD=A1=A3=20
<BR><BR>PROGRAM NAME: ratios <BR>INPUT FORMAT <BR>Line =
1: =20
=
=C8=FD=B8=F6=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=D5=FB=CA=FD=A3=AC=B1=ED=CA=
=BE=C4=BF=B1=EA=CB=C7=C1=CF <BR>Line 2..4: =20
=
=C3=BF=D0=D0=B0=FC=C0=A8=C8=FD=B8=F6=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=D5=
=FB=CA=FD=A3=AC=B1=ED=CA=BE=C5=A9=B7=F2=D4=BC=BA=B2=C2=F2=BD=F8=B5=C4=CB=C7=
=C1=CF=B5=C4=B1=C8=C0=FD <BR><BR>SAMPLE INPUT (file=20
ratios.in) <BR>3 4 5 1 2 3 3 7 1 2 1 2 <BR>OUTPUT FORMAT=20
=
<BR>=CA=E4=B3=F6=CE=C4=BC=FE=D2=AA=B0=FC=C0=A8=D2=BB=D0=D0=A3=AC=D5=E2=D2=
=BB=D0=D0=D2=AA=C3=B4=D3=D0=CB=C4=B8=F6=D5=FB=CA=FD=A3=AC=D2=AA=C3=B4=CA=C7=
=A1=B0NONE=A1=B1=A1=A3=C7=B0=C8=FD=B8=F6=D5=FB=CA=FD=B1=ED=CA=BE=C8=FD=D6=
=D6=CB=C7=C1=CF=B5=C4=B7=DD=CA=FD=A3=AC=D3=C3=D5=E2=D1=F9=B5=C4=C5=E4=B1=C8=
=BF=C9=D2=D4=B5=C3=B5=BD=C4=BF=B1=EA=CB=C7=C1=CF=A1=A3=B5=DA=CB=C4=B8=F6=D5=
=FB=CA=FD=B1=ED=CA=BE=BB=EC=BA=CF=C7=B0=C8=FD=D6=D6=CB=C7=C1=CF=BA=F3=B5=C3=
=B5=BD=B5=C4=C4=BF=B1=EA=CB=C7=C1=CF=B5=C4=B7=DD=CA=FD=A1=A3=20
<BR><BR>SAMPLE OUTPUT (file ratios.out) <BR>8 1 5 7</DIV>
<HR>
<P></P>
<P><STRONG>=D7=F6=B7=A8=D2=BB=C8=D5=D6=BE:</STRONG></P>
<P><STRONG>USACO 3.2.4 Feed =
Ratios<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D2=D4=C7=B0=D7=F6=B9=FD,=CF=D6=D4=DA=BB=BB=C1=CB=D6=D3=B7=BD=B7=
=A8=D7=F6,=D2=D4=C7=B0=CA=C7=C3=B6=BE=D9=D4=AD=C1=CF=D4=D9=C5=C5=D0=F2,=CF=
=D6=D4=DA=CF=C8=C3=B6=BE=D9=CB=C7=C1=CF,=D4=D9=C3=B6=BE=D9=C1=BD=D6=D6=D4=
=AD=C1=CF,=BF=C9=D2=D4=B1=DC=C3=E2=C5=C5=D0=F2.<BR>=D0=C2=B5=C4=CC=E5=BB=E1=
:true=BA=CDfalse=D2=B2=BF=C9=D2=D4=D3=C3=C0=B4xor=B5=C4,=D5=E2=D1=F9=C5=D0=
=B6=CF=C1=BD=B8=F6=CC=F5=BC=FE=CA=C7=B7=F1=D3=D0=CF=E0=CD=AC=D7=B4=CC=AC=BE=
=CD=B7=BD=B1=E3=BA=DC=B6=E0=C1=CB.</STRONG></P>
<P><STRONG>{<BR>TASK:ratios<BR>LANG:PASCAL<BR>}<BR>program=20
ratios;<BR>var<BR> feed:array[0..3,1..3] of=20
integer;<BR>procedure init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'ratios.in');reset(input);<BR> for =
i:=3D0 to=20
3 do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to 3=20
=
do<BR> &=
nbsp; =20
=
read(feed[i,j]);<BR>  =
; =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>procedure=20
work;<BR>var<BR> =
i1,i2,i0:integer;<BR> =20
a,b,c,d,e,f:longint;<BR>begin<BR> =20
assign(output,'ratios.out');rewrite(output);<BR> =
for=20
i0:=3D1 to 100 do<BR> =20
=
begin<BR> &nbs=
p;=20
for i1:=3D0 to 100=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
if feed[0,1]*i0-feed[1,1]*i1<0 then=20
=
break;<BR> &nb=
sp; =20
if feed[0,2]*i0-feed[1,2]*i1<0 then=20
=
break;<BR> &nb=
sp; =20
if feed[0,3]*i0-feed[1,3]*i1<0 then=20
=
break;<BR> &nb=
sp; =20
for i2:=3D0 to 100=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
;=20
=
a:=3Dfeed[0,1]*i0-feed[1,1]*i1-feed[2,1]*i2;<BR> &=
nbsp; &n=
bsp; =20
=
b:=3Dfeed[0,2]*i0-feed[1,2]*i1-feed[2,2]*i2;<BR> &=
nbsp; &n=
bsp; =20
=
c:=3Dfeed[0,3]*i0-feed[1,3]*i1-feed[2,3]*i2;<BR> &=
nbsp; &n=
bsp; =20
if (a<0)or(b<0)or(c<0) then=20
=
break;<BR> &nb=
sp; &nbs=
p;=20
if ((a=3D0)xor(feed[3,1]=3D0)) then=20
=
continue;<BR> =
&=
nbsp;=20
if ((b=3D0)xor(feed[3,2]=3D0)) then=20
=
continue;<BR> =
&=
nbsp;=20
if ((c=3D0)xor(feed[3,3]=3D0)) then=20
=
continue;<BR> =
&=
nbsp;=20
if (a<>0)and (a mod feed[3,1]<>0) then=20
=
continue;<BR> =
&=
nbsp;=20
if (b<>0)and (b mod feed[3,2]<>0) then=20
=
continue;<BR> =
&=
nbsp;=20
if (c<>0)and (c mod feed[3,3]<>0) then=20
=
continue;<BR> =
&=
nbsp;=20
if a=3D0 then d:=3D-1 else d:=3Da div=20
=
feed[3,1];<BR>  =
; =
=20
if b=3D0 then e:=3D-1 else e:=3Db div=20
=
feed[3,2];<BR>  =
; =
=20
if c=3D0 then f:=3D-1 else f:=3Dc div=20
=
feed[3,3];<BR>  =
; =
=20
if ((d=3De)or(d=3D-1)or(e=3D-1)) and ((e=3Df)or(f=3D-1)or(e=3D-1)) =
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
write(i1,' ',i2,'=20
=
');<BR> =
&=
nbsp; =20
if d<>-1 then=20
=
write(d)<BR> &=
nbsp; &n=
bsp; &nb=
sp;=20
else if e<>-1 then=20
=
write(e)<BR> &=
nbsp; &n=
bsp; &nb=
sp; =20
else if f<>-1 then=20
=
write(f)<BR> &=
nbsp; &n=
bsp; &nb=
sp; =20
else=20
=
write(0);<BR> =
&=
nbsp; =20
writeln('=20
=
',i0);<BR> &nb=
sp; &nbs=
p; =20
=
close(output);<BR> &=
nbsp; &n=
bsp; =20
=
exit;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
=
end;<BR>  =
; =20
end;<BR> =20
end;<BR> writeln('NONE');<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</STRONG></P>
<P><STRONG>USACO 3.2.4 Feed =
Ratios<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
<P><STRONG>=D7=F6=B7=A8=B6=FE=C8=D5=D6=BE:</STRONG></P>
=
<P><STRONG>=BF=B4=C1=CBUSACO=B5=C4=B7=D6=CE=F6=BA=F3=D3=D6=D7=F6=C1=CB=D2=
=BB=B4=CE,=D5=E2=B5=C0=CC=E2=D6=BB=D0=E8=D2=AA=C3=B6=BE=D9=C4=BF=B1=EA=CB=
=C7=C1=CF=B5=C4=D6=B5=BE=CD=BF=C9=D2=D4=C1=CB,=C6=E4=CB=FB=B5=C4=BF=C9=D2=
=D4=BD=E2=B7=BD=B3=CC=B5=C3=B5=BD.<BR>[a1,b1,c1=20
[k1 [d1<BR>a2,b2,c2 k2 =3D d2 *k<BR>a3,b3,c3] k3] =
d3]<BR>=CF=C8=BD=E2=B5=C3<BR>[a1,b1,c1=20
<BR>a2,b2,c2 =
<BR>a3,b3,c3]<BR>=B5=C4=C4=E6=BE=D8=D5=F3,=C8=BB=BA=F3=BE=CD=BF=C9=D2=D4=CD=
=A8=B9=FD=CF=FB=C8=A5<BR>[a1,b1,c1 <BR>a2,b2,c2=20
=
<BR>a3,b3,c3],<BR>=C8=BB=BA=F3=D5=E2=B8=F6=B3=CB=D2=D4=CB=FC=B5=C4=C4=E6=BE=
=D8=D5=F3,=BE=CD=BF=C9=D2=D4=B5=C3=B3=F6k1,k2,k3=B5=C4=D6=B5=C1=CB.<BR>[d=
1<BR>d2=20
*k<BR>d3]</STRONG></P>
=
<P><STRONG>=C8=BB=BA=F3=D5=E2=B8=F6=BF=C9=D2=D4=D3=D0=D2=BB=B8=F6=BB=AF=BC=
=F2,=B2=BB=D0=E8=D2=AA=C4=E6=BE=D8=D5=F3</STRONG></P>
=
<P><STRONG>=D3=C3=C4=BF=B1=EA=B5=C4=D6=B5=CC=E6=BB=BB=D4=AD=BE=D8=D5=F3=C3=
=BF=D2=BB=C1=D0,=CB=E3=B3=F6=C0=B4=B5=C4=D0=D0=C1=D0=CA=BD=B3=FD=D2=D4=D4=
=AD=BE=D8=D5=F3=B5=C4=D0=D0=C1=D0=CA=BD=BE=CD=B5=C3=B5=BD=C1=CB=C3=BF=D2=BB=
=D6=D6=CB=C7=C1=CF=B5=C4=C8=A1=B5=C3=B7=DD=CA=FD.</STRONG></P>
=
<P><STRONG>=D6=A4=C3=F7=C1=CB=BA=C3=BE=C3...<BR>......=D1=D0=BE=BF=B4=F3=D1=
=A7=CA=FD=D1=A7=BF=CE=B1=BE=D1=D0=BE=BF=C1=CB=BA=C3=BE=C3</STRONG></P>
=
<P><STRONG>{<BR>TASK:ratios<BR>LANG:PASCAL<BR>}<BR>{$D-,L-,Y-,R-,S-,I-,Q-=
}<BR>program=20
ratios;<BR>type<BR> matrix=3Darray[1..3,1..3] of =
longint;<BR>var<BR> =
feed:matrix;<BR> =20
goal:array[1..3] of integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'ratios.in');reset(input);<BR> for =
j:=3D1 to=20
3 do<BR> =20
read(goal[j]);<BR> readln;<BR> =
for=20
i:=3D1 to 3 do<BR> =20
=
begin<BR> &nbs=
p;=20
for j:=3D1 to 3=20
=
do<BR> &=
nbsp; =20
=
read(feed[j,i]);<BR>  =
; =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>function=20
=
determinant(temp:matrix):longint;{=D0=D0=C1=D0=CA=BD}<BR>var<BR> &nb=
sp; =20
num:longint;<BR>begin<BR> =20
=
num:=3Dtemp[1,1]*temp[2,2]*temp[3,3]+<BR> &n=
bsp; =20
=
temp[1,3]*temp[2,1]*temp[3,2]+<BR> &nb=
sp;=20
=
temp[1,2]*temp[2,3]*temp[3,1]-<BR> &nb=
sp;=20
=
temp[1,3]*temp[2,2]*temp[3,1]-<BR> &nb=
sp;=20
=
temp[1,2]*temp[2,1]*temp[3,3]-<BR> &nb=
sp;=20
temp[1,1]*temp[2,3]*temp[3,2];<BR> =20
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -