📄 usaco 4_1_1 beef mcnuggets 题解_leokan的blog.mht
字号:
<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 4.1.1 Beef McNuggets =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C220=C8=D5 =D0=C7=C6=DA=C8=FD =
00:09</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 4.1.1 Beef McNuggets</H2>
<DIV class=3Dt_msgfont>Beef McNuggets<BR>Hubert Chen <BR>Farmer =
Brown's cows=20
are up in arms, having heard that McDonalds is considering the=20
introduction of a new product: Beef McNuggets. The cows are trying =
to find=20
any possible way to put such a product in a negative light. =
<BR><BR>One=20
strategy the cows are pursuing is that of `inferior packaging'. =
``Look,''=20
say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and =
10, you=20
can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or =
17=20
McNuggets. Bad packaging: bad product.'' <BR><BR>Help the cows. =
Given N=20
(the number of packaging options, 1 <=3D N <=3D 10), and a =
set of N=20
positive integers (1 <=3D i <=3D 256) that represent the =
number of=20
nuggets in the various packages, output the largest number of =
nuggets that=20
can not be purchased by buying nuggets in the given sizes. Print 0 =
if all=20
possible purchases can be made or if there is no bound to the =
largest=20
number. <BR><BR>The largest impossible number (if it exists) will =
be no=20
larger than 2,000,000,000. <BR><BR>PROGRAM NAME: nuggets<BR>INPUT=20
FORMAT<BR>Line 1: N, the number of packaging options =
<BR>Line=20
2..N+1: The number of nuggets in one kind of=20
box <BR><BR>SAMPLE INPUT (file nuggets.in)=20
<BR>3<BR>3<BR>6<BR>10<BR><BR>OUTPUT FORMAT<BR>The output file =
should=20
contain a single line containing a single integer that represents =
the=20
largest number of nuggets that can not be represented or 0 if all =
possible=20
purchases can be made or if there is no bound to the largest =
number.=20
<BR>SAMPLE OUTPUT (file nuggets.out)<BR>17<BR><BR><BR><BR>Beef=20
McNuggets<BR><BR>=C2=F3=CF=E3=C5=A3=BF=E9<BR><BR>Hubert Chen =
<BR><BR>=D2=EB by ragazza=20
=
gatti<BR><BR>=C5=A9=B7=F2=B2=BC=C0=CA=B5=C4=C4=CC=C5=A3=C3=C7=D5=FD=D4=DA=
=BD=F8=D0=D0=B6=B7=D5=F9=A3=AC=D2=F2=CE=AA=CB=FC=C3=C7=CC=FD=CB=B5=C2=F3=B5=
=B1=C0=CD=D5=FD=D4=DA=BF=BC=C2=C7=D2=FD=BD=F8=D2=BB=D6=D6=D0=C2=B2=FA=C6=B7=
=A3=BA=C2=F3=CF=E3=C5=A3=BF=E9=A1=A3=C4=CC=C5=A3=C3=C7=D5=FD=D4=DA=CF=EB=BE=
=A1=D2=BB=C7=D0=B0=EC=B7=A8=C8=C3=D5=E2=D6=D6=BF=C9=C5=C2=B5=C4=C9=E8=CF=EB=
=C5=DD=CC=C0=A1=A3=C4=CC=C5=A3=C3=C7=BD=F8=D0=D0=B6=B7=D5=F9=B5=C4=B2=DF=C2=
=D4=D6=AE=D2=BB=CA=C7=A1=B0=C1=D3=D6=CA=B5=C4=B0=FC=D7=B0=A1=B1=A1=A3=A1=B0=
=BF=B4=A3=AC=A1=B1=A3=AC=C4=CC=C5=A3=C3=C7=CB=B5=A3=AC=A1=B0=C8=E7=B9=FB=C4=
=E3=D3=C3=D6=BB=D3=D0=D2=BB=B4=CE=C4=DC=D7=B03=BF=E9=A1=A26=BF=E9=BB=F210=
=BF=E9=B5=C4=C8=FD=D6=D6=B0=FC=D7=B0=BA=D0=D7=B0=C2=F3=CF=E3=C5=A3=BF=E9=A3=
=AC=C4=E3=BE=CD=B2=BB=BF=C9=C4=DC=C2=FA=D7=E3=CF=EB=D2=AA=D2=BB=B4=CE=D6=BB=
=CF=EB=C2=F21=A1=A22=A1=A24=A1=A25=A1=A27=A1=A28=A1=A211=A1=A214=BB=F217=BF=
=E9=C2=F3=CF=E3=C5=A3=BF=E9=B5=C4=B9=CB=BF=CD=C1=CB=A1=A3=C1=D3=D6=CA=B5=C4=
=B0=FC=D7=B0=D2=E2=CE=B6=D7=C5=C1=D3=D6=CA=B5=C4=B2=FA=C6=B7=A1=A3=A1=B1<=
BR>=C4=E3=B5=C4=C8=CE=CE=F1=CA=C7=B0=EF=D6=FA=D5=E2=D0=A9=C4=CC=C5=A3=A1=A3=
=B8=F8=B3=F6=B0=FC=D7=B0=BA=D0=B5=C4=D6=D6=C0=E0=CA=FDN(1<=3DN<=3D1=
0)=BA=CDN=B8=F6=B4=FA=B1=ED=B2=BB=CD=AC=D6=D6=C0=E0=B0=FC=D7=B0=BA=D0=C8=DD=
=C4=C9=C2=F3=CF=E3=C5=A3=BF=E9=B8=F6=CA=FD=B5=C4=D5=FD=D5=FB=CA=FD(1<=3D=
i<=3D256)=A3=AC=CA=E4=B3=F6=B9=CB=BF=CD=B2=BB=C4=DC=D3=C3=C9=CF=CA=F6=B0=
=FC=D7=B0=BA=D0(=C3=BF=D6=D6=BA=D0=D7=D3=CA=FD=C1=BF=CE=DE=CF=DE)=C2=F2=B5=
=BD=C2=F3=CF=E3=C5=A3=BF=E9=B5=C4=D7=EE=B4=F3=BF=E9=CA=FD=A1=A3=C8=E7=B9=FB=
=D4=DA=CF=DE=B6=A8=B7=B6=CE=A7=C4=DA=CB=F9=D3=D0=B9=BA=C2=F2=B7=BD=B0=B8=B6=
=BC=C4=DC=B5=C3=B5=BD=C2=FA=D7=E3=A3=AC=D4=F2=CA=E4=B3=F60=A1=A3<BR>=B7=B6=
=CE=A7=CF=DE=D6=C6=CA=C7=CB=F9=D3=D0=B2=BB=B3=AC=B9=FD2,000,000,000=B5=C4=
=D5=FD=D5=FB=CA=FD=A1=A3<BR><BR>PROGRAM=20
NAME: nuggets<BR><BR>INPUT FORMAT<BR><BR>=B5=DA1=D0=D0: =
=B0=FC=D7=B0=BA=D0=B5=C4=D6=D6=C0=E0=CA=FDN=20
<BR>=B5=DA2=D0=D0=B5=BDN+1=D0=D0: =
=C3=BF=B8=F6=D6=D6=C0=E0=B0=FC=D7=B0=BA=D0=C8=DD=C4=C9=C2=F3=CF=E3=C5=A3=BF=
=E9=B5=C4=B8=F6=CA=FD <BR><BR>SAMPLE INPUT (file=20
nuggets.in)<BR><BR>3<BR>3<BR>6<BR>10<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=CA=E4=B3=F6=CE=C4=BC=FE=D6=BB=D3=D0=D2=BB=D0=D0=CA=FD=D7=D6=
=A3=BA=B9=CB=BF=CD=B2=BB=C4=DC=D3=C3=B0=FC=D7=B0=BA=D0=C2=F2=B5=BD=C2=F3=CF=
=E3=C5=A3=BF=E9=B5=C4=D7=EE=B4=F3=BF=E9=CA=FD=BB=F20(=C8=E7=B9=FB=D4=DA=CF=
=DE=B6=A8=B7=B6=CE=A7=C4=DA=CB=F9=D3=D0=B9=BA=C2=F2=B7=BD=B0=B8=B6=BC=C4=DC=
=B5=C3=B5=BD=C2=FA=D7=E3)=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file nuggets.out)<BR><BR>17</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 4.1.1 Beef =
McNuggets<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
<P><STRONG>AC=BA=F3=CB=FB=CB=B5:NEW GRADER -- report=20
=
problems!=CA=C7=B5=BD=C1=CB=D0=C2=B5=C8=BC=B6=B5=C4=D2=E2=CB=BC=C3=B4?=BA=
=C7=BA=C7<BR>=D5=E2=CC=E2=BA=DC=C8=F5,=B6=AF=CC=AC=B9=E6=BB=AE=BF=C9=D7=F6=
,f(i)=3Df(i)or f(i-nug(j))=BB=F2=D5=DF=B5=DD=CD=C6,if f(i)=20
then=20
=
f(i+nug[j])=3Dtrue,=B7=B4=D5=FD=D5=E2=D1=F9=BF=C9=D2=D4=B5=C3=B5=BD=CB=F9=
=D3=D0=B5=C4=BF=C9=B5=C3=B5=BD=B5=C4=CA=FD,=D4=DA=C6=E4=D6=D0=D5=D2=D2=BB=
=B8=F6=D7=EE=B4=F3=B5=C4,2=B8=F6=BC=F4=D6=A6,=C8=E7=B9=FBn=B8=F6=CA=FD=B5=
=C4=D7=EE=B4=F3=B9=AB=D4=BC=CA=FD=CA=C71,=C4=C7=C3=B4=D5=E2n=B8=F6=CA=FD(=
=C9=E8=D7=EE=B4=F3=D6=B5=CE=AANmax,n=B8=F6=CA=FD=B5=C4=D7=EE=D0=A1=B9=AB=B1=
=B6=CA=FD=CE=AAx)=B1=D8=C8=BB=BF=C9=D2=D4=CD=A8=B9=FD=C4=B3=D6=D6=D7=E9=BA=
=CF=B5=C3=B5=BD=C1=AC=D0=F8=B5=C4x+1..x+Nmax=B8=F6=CA=FD,=D3=C3=CA=FD=D1=A7=
=B9=E9=C4=C9=B7=A8=BF=C9=D2=D4=B5=C3=B5=BD=D3=C9x=BF=AA=CA=BC,=BA=F3=C3=E6=
=B5=C4=CA=FD=B6=BC=BF=C9=D2=D4=C1=AC=D0=F8=B5=C3=B5=BD.=C1=ED(=C9=E8n=B8=F6=
=CA=FD=D7=EE=D0=A1=CE=AANmin)=C8=E7=B9=FB=C1=AC=D0=F8Nmin=B8=F6=CA=FD=B6=BC=
=BF=C9=D2=D4=B5=C3=B5=BD=B5=C4=BB=B0=BA=F3=C3=E6=B5=C4=CA=FD=B6=BC=BF=C9=D2=
=D4=C1=AC=D0=F8=B5=C3=B5=BD,=D2=B2=CA=C7=D3=C3=CA=FD=D1=A7=B9=E9=C4=C9=B7=
=A8=D6=A4=C3=F7=B5=C4.</STRONG></P>
=
<P><STRONG>=C1=ED=D3=D0=C1=BD=B8=F6=C3=BB=D3=C3=B5=BD=B5=C4=D3=C5=BB=AF,=BC=
=C7=C2=BC=C6=E4=D6=D0x(x<n)=B8=F6=CA=FD=B5=C4=D7=EE=B4=F3=B9=AB=D4=BC=CA=
=FDxa=BA=CD=D7=EE=D0=A1=B9=AB=B1=B6=CA=FDxb,=C4=C7=C3=B4=D4=DA=C3=B6=BE=D9=
=B5=BDxb=BA=F3=C8=F4Nmin>xa=D4=F2=BF=C9=D2=D4=BD=ABxa=B8=B3=D6=B5=B8=F8=
Nmin,=BB=B9=D3=D0=C3=B6=BE=D9=B5=C4=C9=CF=CF=DE=CA=C7n=B8=F6=CA=FD=B5=C4=D7=
=EE=D0=A1=B9=AB=B1=B6=CA=FD,=B9=FD=C1=CB=D5=E2=B8=F6=BF=C9=D2=D4=B2=BB=BC=
=CC=D0=F8=C3=B6=BE=D9,=CA=E4=B3=F6=B5=B1=C7=B0=BD=E2.<BR>{<BR>TASK:nugget=
s<BR>LANG:PASCAL<BR>}<BR>program=20
nuggets;<BR>const<BR> =
maxn=3D20000;<BR> =20
maxq=3D10000;<BR> maxc=3D1 shl=20
16;<BR>type<BR> nugtype=3Darray[1..256] of=20
integer;<BR>var<BR> =
nug:nugtype;<BR> =20
f:array[1..maxn] of integer;<BR> =
gcd:array[0..256] of=20
integer;<BR> n,fn:integer;<BR>procedure=20
init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'nuggets.in');reset(input);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
readln(nug[i]);<BR> =
close(input);<BR>end;<BR>function=20
gcdof2(x,y:integer):integer;<BR>var<BR> =20
r,i,j,t:integer;<BR>begin<BR> if x>y=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
i:=3Dy;<BR> &n=
bsp;=20
j:=3Dx;<BR> =20
end<BR> else=20
=
begin<BR> &nbs=
p;=20
=
i:=3Dx;<BR> &n=
bsp;=20
j:=3Dy;<BR> =20
end;<BR> r:=3Dj-i;<BR> while =
r>0=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if i<r=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
t:=3Di;<BR> &n=
bsp; =20
=
i:=3Dr;<BR> &n=
bsp; =20
=
r:=3Dt;<BR> &n=
bsp; =20
=
end;<BR>  =
;=20
=
j:=3Di;<BR> &n=
bsp;=20
=
i:=3Dr;<BR> &n=
bsp;=20
r:=3Dj-i;<BR> =20
end;<BR> exit(i);<BR>end;<BR>procedure=20
bfs;<BR>var<BR> queue:array[1..256] of=20
integer;<BR> visit:array[1..256] of=20
boolean;<BR> =20
open,closed,temp,i,j,now:integer;<BR>begin<BR> =20
fillchar(visit,sizeof(visit),0);<BR> =20
closed:=3D0;<BR> for i:=3D1 to n+1=20
do<BR> for j:=3Di+1 to n =
=
do<BR> =
=
begin<BR> &nbs=
p; =20
=
temp:=3Dgcdof2(nug[i],nug[j]);<BR> &nb=
sp; =20
if not visit[temp]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
visit[temp]:=3Dtrue;<BR> &=
nbsp; &n=
bsp; =20
=
inc(closed);<BR> &nb=
sp; &nbs=
p; =20
=
queue[closed]:=3Dtemp;<BR>  =
; =20
=
end;<BR>  =
;=20
end;<BR> open:=3D0;<BR> while=20
open<>closed =
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(open);<BR>  =
; =20
=
now:=3Dqueue[open];<BR> &n=
bsp; =20
for i:=3D1 to n=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
temp:=3Dgcdof2(nug[i],now);<BR> =
=
if not visit[temp]=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(closed);<BR> &nb=
sp; &nbs=
p; =20
=
queue[closed]:=3Dtemp;<BR>  =
; =
=20
=
visit[temp]:=3Dtrue;<BR> &=
nbsp; &n=
bsp; =20
=
end;<BR>  =
; =20
end;<BR> =20
end;<BR> if not visit[1]=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
writeln(0);<BR> &nbs=
p; =20
=
close(output);<BR> &=
nbsp; =20
halt;<BR> =20
end;<BR> gcd[0]:=3D0;<BR> for =
i:=3D1 to=20
256 do<BR> if visit[i]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
inc(gcd[0]);<BR> &nb=
sp; =20
=
gcd[gcd[0]]:=3Di;<BR> &nbs=
p; =20
end;<BR>end;<BR>procedure work;<BR>var<BR> =20
i,j,min,max:longint;<BR> f:array[0..maxc+256] of =
boolean;<BR> =
ok:boolean;<BR>begin<BR> =20
=
assign(output,'nuggets.out');rewrite(output);<BR> =20
bfs;<BR> =
fillchar(f,sizeof(f),0);<BR> =20
min:=3Dmaxint;<BR> for i:=3D1 to n=20
do<BR> if nug[i]<min =
then=20
min:=3Dnug[i];<BR> =
f[0]:=3Dtrue;<BR> =20
max:=3D0;<BR> for i:=3D0 to maxc=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if not f[i] then=20
=
max:=3Di;<BR> =
=20
if f[i]=20
=
then<BR>  =
; =20
for j:=3D1 to n=20
=
do<BR> &=
nbsp; =20
=
f[i+nug[j]]:=3Dtrue;<BR> &=
nbsp; =20
=
ok:=3Dtrue;<BR> &nbs=
p; =20
for j:=3Di+1 to i+min=20
=
do<BR> &=
nbsp; =20
ok:=3Dok and=20
=
f[j];<BR> &nbs=
p;=20
if ok then break;<BR> =20
end;<BR> writeln(max);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
<P><STRONG></STRONG></P>
<P><STRONG>This problem is fairly straight-forward dynamic =
programming. We=20
know that a value X is possible if and only if X - v<SUB>i</SUB> =
is=20
possible, where v<SUB>i</SUB> is the number of nuggets in one of =
the=20
package types. </STRONG></P>
<P><STRONG>The only way for there to be no bound to the largest =
number=20
which is unobtainable is if the greatest common divisor of the =
package=20
sizes is greater than 1, so first check for that. </STRONG></P>
<P><STRONG>Otherwise, go through the sizes in increasing order. =
For each=20
impossible value, update the largest number found thus far. =
Otherwise, if=20
X is possible, mark X + v<SUB>i</SUB> for each i as being =
possible.=20
Whenever the last 256 of the sizes have all been possible, you =
know that=20
all the sizes from here on out are also possible (you actually =
only need=20
the last min {v<SUB>i</SUB>} to be possible, but doing the extra =
256 steps=20
takes almost no time). </STRONG></P><PRE><STRONG>#include =
<stdio.h>
/* the number and value of the package sizes */
int nsize;
int sizes[10];
/* cando specifies whether a given number is possible or not */
/* since max size =3D 256, we'll never need to mark more than 256
in the future, so we use a sliding window */
int cando[256];
int gcd(int a, int b)
{ /* uses standard gcd algorithm to computer greatest common divisor */
int t;
while (b !=3D 0)
{
t =3D a % b;
a =3D b;
b =3D t;
}
return a;
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2; /* loop variable */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -