📄 usaco 3_2_3 spinning wheels 题解_leokan的blog.mht
字号:
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<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.3 Spinning Wheels =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA02=D4=C202=C8=D5 =D0=C7=C6=DA=C1=F9 =
18:25</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 3.2.3 Spinning Wheels</H2>
<DIV class=3Dt_msgfont>Spinning Wheels<BR>1998 ACM NE Regionals =
<BR>Each of=20
five opaque spinning wheels has one or more wedges cut out of =
their edges.=20
These wedges must be aligned quickly and correctly. Each wheel =
also has an=20
alignment mark (at 0 degrees) so that the wheels can all be =
started in a=20
known position. Wheels rotate in the `plus degrees' direction, so =
that=20
shortly after they start, they pass through 1 degree, 2 degrees, =
etc.=20
(though probably not at the same time). <BR><BR>This is an integer =
problem. Wheels are never actually at 1.5 degrees or 23.51234123 =
degrees.=20
For example, the wheels are considered to move instantaneously =
from 20 to=20
25 degrees during a single second or even from 30 to 40 degrees if =
the=20
wheel is spinning quickly. <BR><BR>All angles in this problem are =
presumed=20
to be integers in the range 0 <=3D angle <=3D 359. The angle =
of 0=20
degrees follows the angle of 359 degrees. Each wheel rotates at a =
certain=20
integer number of degrees per second, 1 <=3D speed <=3D 180. =
<BR><BR>Wedges for each wheel are specified by an integer start =
angle and=20
integer angle size (or `extent'), both specified in degrees. =
Wedges in the=20
test data will be separated by at least one degree. <BR><BR>At the =
start,=20
which is time 0, all the wheels' alignment marks line up. Your =
program=20
must determine the earliest time (integer seconds) at or after the =
start=20
that some wedge on each wheel will align with the wedges on the =
other=20
wheel so that a light beam can pass through openings on all five =
wedges.=20
The wedges can align at any part of the rotation. <BR><BR>PROGRAM =
NAME:=20
spin<BR>INPUT FORMAT<BR>Each of five input lines describes a =
wheel.=20
<BR><BR>The first integer on an input line is the wheel's rotation =
speed.=20
The next integer is the number of wedges, 1 <=3D W <=3D 5. =
The next W=20
pairs of integers tell each wedge's start angle and extent. =
<BR><BR>SAMPLE=20
INPUT (file spin.in) <BR>30 1 0 120<BR>50 1 150 90<BR>60 1 60 =
90<BR>70 1=20
180 180<BR>90 1 180 60<BR><BR>OUTPUT FORMAT<BR>A single line with =
a single=20
integer that is the first time the wedges align so a light beam =
can pass=20
through them. Print `none' (lower case, no quotes) if the wedges =
will=20
never align properly. <BR><BR>SAMPLE OUTPUT (file=20
spin.out)<BR>9<BR><BR><BR><BR>Spinning=20
=
Wheels<BR><BR>=B7=C4=B3=B5=B5=C4=C2=D6=D7=D3<BR>=A1=A1<BR><BR><BR>1998 =
ACM NE=20
Regionals<BR>=A1=A1<BR><BR><BR>=D2=EB by Felicia=20
=
Crazy<BR>=A1=A1<BR><BR>=D2=BB=BC=DC=B7=C4=B3=B5=D3=D0=CE=E5=B8=F6=B7=C4=C2=
=D6=A3=AC=D5=E2=CE=E5=B8=F6=B2=BB=CD=B8=C3=F7=B5=C4=C2=D6=D7=D3=B1=DF=D4=B5=
=C9=CF=B6=BC=D3=D0=D2=BB=D0=A9=C8=B1=BF=DA=A1=A3=D5=E2=D0=A9=C8=B1=BF=DA=B1=
=D8=D0=EB=B1=BB=D1=B8=CB=D9=B6=F8=D7=BC=C8=B7=B5=D8=C5=C5=C1=D0=BA=C3=A1=A3=
=C3=BF=B8=F6=C2=D6=D7=D3=B6=BC=D3=D0=D2=BB=B8=F6=C6=F0=CA=BC=B1=EA=BC=C7=A3=
=A8=D4=DA0=B6=C8=A3=A9=A3=AC=D5=E2=D1=F9=CB=F9=D3=D0=B5=C4=C2=D6=D7=D3=B6=
=BC=BF=C9=D2=D4=D4=DA=CD=B3=D2=BB=B5=C4=D2=D1=D6=AA=CE=BB=D6=C3=BF=AA=CA=BC=
=D7=AA=B6=AF=A1=A3=C2=D6=D7=D3=B0=B4=D5=D5=D4=AD=B7=BD=CF=F2=BC=D3=C9=CF=BD=
=C7=B6=C8=D0=FD=D7=AA=A3=AC=CB=F9=D2=D4=B4=D3=C6=F0=CA=BC=CE=BB=D6=C3=BF=AA=
=CA=BC=A3=AC=D4=DA=D2=BB=B6=A8=B5=C4=CA=B1=BC=E4=C4=DA=A3=AC=CB=FC=C3=C7=D2=
=C0=B4=CE=D7=AA=B9=FD1=B6=C8=A3=AC2=B6=C8=BB=F2=B5=C8=B5=C8=A3=A8=CB=E4=C8=
=BB=D5=E2=D0=A9=C2=D6=D7=D3=BA=DC=BF=C9=C4=DC=B2=BB=BB=E1=CD=AC=CA=B1=D7=AA=
=B9=FD=D5=E2=D0=A9=BD=C7=B6=C8=A3=A9=A1=A3=20
=
<BR><BR>=D5=E2=CA=C7=D2=BB=B8=F6=D5=FB=CA=FD=CE=CA=CC=E2=A1=A3=C2=D6=D7=D3=
=B2=BB=BB=E1=D7=AA=B9=FD1.5=B6=C8=BB=F223.51234123=B6=C8=D5=E2=D1=F9=B5=C4=
=BD=C7=B6=C8=A1=A3=C0=FD=C8=E7=A3=AC=C2=D6=D7=D3=BF=C9=C4=DC=D4=DA=D2=BB=C3=
=EB=D6=D3=C4=DA=D7=AA=B9=FD20=B5=BD25=B6=C8=C9=F5=D6=C130=B5=BD40=B6=C8=A3=
=A8=C8=E7=B9=FB=D7=AA=B5=C3=BF=EC=B5=C4=BB=B0=A3=A9=A1=A3=20
=
<BR><BR>=D5=E2=B8=F6=CE=CA=CC=E2=D6=D0=B5=C4=CB=F9=D3=D0=BD=C7=B6=C8=B6=BC=
=CF=DE=D6=C6=D4=DA 0 <=3D =BD=C7=B6=C8 <=3D 359 =
=D5=E2=B8=F6=B7=B6=CE=A7=C4=DA=A1=A3=C2=D6=D7=D3=D7=AA=B9=FD 359 =
=B6=C8=BA=F3=BD=D3=CF=C2=C0=B4=BE=CD=CA=C7 0=20
=
=B6=C8=A1=A3=C3=BF=B8=F6=C2=D6=D7=D3=B6=BC=D3=D0=D2=BB=B8=F6=C8=B7=B6=A8=B5=
=C4=D0=FD=D7=AA=CB=D9=B6=C8=A3=AC=D2=D4=C3=EB=D7=F7=CE=AA=B5=A5=CE=BB=A1=A3=
1 <=3D =CB=D9=B6=C8 <=3D 180=A1=A3=20
=
<BR><BR>=C2=D6=D7=D3=C9=CF=B5=C4=C8=B1=BF=DA=B5=C4=C6=F0=CA=BC=BD=C7=B6=C8=
=BA=CD=C8=B1=BF=DA=B4=F3=D0=A1=A3=A8=BB=F2=B3=A4=B6=C8=A3=A9=B8=F7=D3=C9=D2=
=BB=B8=F6=D5=FB=CA=FD=B1=ED=CA=BE=A3=AC=B6=BC=D2=D4=B6=C8=CE=AA=B5=A5=CE=BB=
=A1=A3=D4=DA=D2=BB=B8=F6=C2=D6=D7=D3=C9=CF=A3=AC=C1=BD=B8=F6=C8=B1=BF=DA=D6=
=AE=BC=E4=D6=C1=C9=D9=D3=D0=D2=BB=B6=C8=B5=C4=BC=E4=B8=F4=A1=A3=20
=
<BR><BR>=D4=DA=C6=F0=CA=BC=CE=BB=D6=C3=A3=AC=C9=E8=CA=B1=BC=E4=CE=AA=20
=
0=A3=AC=CB=F9=D3=D0=B5=C4=C2=D6=D7=D3=B5=C4=C6=F0=CA=BC=B1=EA=BC=C7=C5=C5=
=C1=D0=B3=C9=D2=BB=CC=F5=D6=B1=CF=DF=A1=A3=C4=E3=B5=C4=B3=CC=D0=F2=B1=D8=D0=
=EB=BC=C6=CB=E3=A3=AC=D7=EE=D4=E7=B3=F6=CF=D6=C3=BF=B8=F6=B5=C4=C2=D6=D7=D3=
=C9=CF=B5=C4=C8=B1=BF=DA=CD=AC=C6=E4=CB=FB=C2=D6=D7=D3=C9=CF=B5=C4=C8=B1=BF=
=DA=B6=D4=D7=BC=A3=A8=D2=B2=BE=CD=CA=C7=D2=BB=CA=F8=B9=E2=BF=C9=D2=D4=CD=A8=
=B9=FD=CE=E5=B8=F6=C2=D6=D7=D3=C9=CF=B5=C4=CE=E5=B8=F6=C8=B1=BF=DA=A3=A9=C7=
=E9=BF=F6=B5=C4=CA=B1=BC=E4=A1=A3=D5=E2=D0=A9=C8=B1=BF=DA=D4=DA=C8=CE=D2=E2=
=D2=BB=B8=F6=BD=C7=B6=C8=B6=D4=D7=BC=A1=A3=20
<BR><BR>PROGRAM NAME: spin<BR>INPUT =
FORMAT<BR>=CA=E4=C8=EB=D6=D0=B5=C4=CE=E5=D0=D0=B6=D4=D3=A6=CE=E5=B8=F6=C2=
=D6=D7=D3=A1=A3=20
=
<BR><BR>=B5=DA=D2=BB=B8=F6=CA=FD=D7=D6=B1=ED=CA=BE=C2=D6=D7=D3=B5=C4=D7=AA=
=B6=AF=CB=D9=B6=C8=A1=A3=CF=C2=D2=BB=B8=F6=CA=FD=D7=D6=CA=C7=C8=B1=BF=DA=B5=
=C4=CA=FD=C4=BF W=A1=A31 <=3D W <=3D =
5=A1=A3=BD=D3=CF=C2=C0=B4=B5=C4 W <SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%B6%D4%CA%FD">=B6=D4=CA=FD</SPAN>=D7=D6=B1=ED=CA=BE=
=C3=BF=B8=F6=C8=B1=BF=DA=B5=C4=C6=F0=CA=BC=BD=C7=B6=C8=BA=CD=B3=A4=B6=C8=A1=
=A3=20
<BR><BR>SAMPLE INPUT (file spin.in)<BR>30 1 0 120<BR>50 1 150 =
90<BR>60 1=20
60 90<BR>70 1 180 180<BR>90 1 180 60<BR><BR>OUTPUT=20
=
FORMAT<BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=B0=FC=C0=A8=D2=BB=B8=F6=D5=FB=CA=
=FD=A3=AC=B1=ED=CA=BE=B9=E2=C4=DC=B9=BB=CD=A8=B9=FD=D5=E2=CE=E5=B8=F6=C2=D6=
=D7=D3=B5=C4=D7=EE=D4=E7=CA=B1=BC=E4=A1=A3=C8=E7=B9=FB=CE=DE=BD=E2=A3=AC=CA=
=E4=B3=F6"none"(=D0=A1=D0=B4=A3=AC=B2=BB=BA=AC=D2=FD=BA=C5=A3=A9=A1=A3=20
<BR><BR>SAMPLE OUTPUT (file spin.out)<BR>9</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 3.2.3 Spinning =
Wheels<BR>=CC=E1=BD=BB=B4=CE=CA=FD:1=B4=CE</STRONG></P>
=
<P><STRONG>=D3=C3=C1=CB=C4=A3=C4=E2+floodfill,=D3=A6=B8=C3=BF=C9=D2=D4=D3=
=C3=CA=FD=D1=A7=B5=C4=B7=BD=B7=A8=CB=E3=D7=EE=D0=A1=B9=AB=B1=B6=CA=FD=B5=C4=
,=B5=AB=CA=C7=CC=AB=C2=E9=B7=B3...</STRONG></P>
<P><STRONG>{<BR>TASK:spin<BR>LANG:PASCAL<BR>}<BR>program=20
spin;<BR>type<BR> gap=3Darray[1..2] of=20
integer;<BR>var<BR> speed:array[1..5] of=20
integer;<BR> wheel:array[1..5,1..5] of=20
gap;<BR> gapp:array[1..5] of =
integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'spin.in');reset(input);<BR> =20
fillchar(wheel,sizeof(wheel),0);<BR> =20
fillchar(gapp,sizeof(gapp),0);<BR> for i:=3D1 to =
5=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
read(speed[i]);<BR> =
=20
=
read(gapp[i]);<BR> &=
nbsp; =20
for j:=3D1 to gapp[i]=20
=
do<BR> &=
nbsp; =20
=
read(wheel[i,j,1],wheel[i,j,2]);<BR> &=
nbsp; =20
readln;<BR> =20
end;<BR> close(input);<BR>end;<BR>procedure=20
work;<BR>var<BR> =20
time,i,j,k:integer;<BR> temp:array[0..359] of=20
integer;<BR>begin<BR> =20
assign(output,'spin.out');rewrite(output);<BR> =20
=
fillchar(temp,sizeof(temp),0);<BR> &nb=
sp;=20
for i:=3D1 to 5=20
=
do<BR> =
for j:=3D1 to gapp[i]=20
=
do<BR> &=
nbsp; =20
for k:=3D0 to wheel[i,j,2]=20
=
do<BR> &=
nbsp; =20
inc(temp[(wheel[i,j,1]+k)mod=20
360]);<BR> for i:=3D0 to =
359=20
=
do<BR> =
if temp[i]=3D5=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
writeln(0);<BR> &nbs=
p; =20
=
close(output);<BR> &=
nbsp; =20
=
exit;<BR> &nbs=
p; =20
end;<BR> for time:=3D1 to 359=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
for i:=3D1 to 5=20
=
do<BR> &=
nbsp; =20
for j:=3D1 to gapp[i]=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p;  =
;=20
=
inc(wheel[i,j,1],speed[i]);<BR> =
&=
nbsp; =20
while wheel[i,j,1]>=3D360 do=20
=
dec(wheel[i,j,1],360);<BR>  =
; =20
=
end;<BR>  =
;=20
=
fillchar(temp,sizeof(temp),0);<BR> &nb=
sp; =20
for i:=3D1 to 5=20
=
do<BR> &=
nbsp; =20
for j:=3D1 to gapp[i]=20
=
do<BR> &=
nbsp; =20
for k:=3D0 to wheel[i,j,2]=20
=
do<BR> &=
nbsp; =20
inc(temp[(wheel[i,j,1]+k)mod=20
=
360]);<BR> &nb=
sp;=20
for i:=3D0 to 359=20
=
do<BR> &=
nbsp; =20
if temp[i]=3D5=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
writeln(time);<BR> &=
nbsp; &n=
bsp; =20
=
close(output);<BR> &=
nbsp; &n=
bsp; =20
=
exit;<BR> &nbs=
p; =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><STRONG>
<HR>
</STRONG>
<P><STRONG>USACO=B7=D6=CE=F6</STRONG></P>
<P><STRONG>The key observation for this problem is that after 360 =
seconds,=20
the wheels have returned to their original locations, so if the =
wheels=20
don't line up in 360 seconds, they will never line up. =
</STRONG></P>
<P><STRONG>To determine if there is a location through which a =
light can=20
be shine, mark, for each wheel, which angles between 0 and 359 a =
light can=20
be shone through. If any location gets marked for all the wheels, =
then a=20
light can be shone through the entire system. Otherwise, no light =
can be=20
shone through all the wheels. </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <assert.h>
#include <string.h>
int speed[5]; /* speed of each wheel */
int wedgest[5][5]; /* start of each wedge (-1 =3D=3D no wedge) */
int wedglen[5][5]; /* length of each wedge */
int pos[5]; /* angular position of each wheel */
int t; /* time (in seconds) since start */
/* (light[deg] >> wid) & 0x1 is true if and only if there
is a wedge in wheel wid that a light can shine through at
angle deg */
int light[360]; =20
=20
/* mark all the degrees we can see through wheel w */
void mark_light(int w)
{
int lv, lv2; /* loop variables */
int wpos; /* wedge position */
for (lv =3D 0; lv < 5; lv++)
{
if (wedglen[w][lv] < 0) /* no more wedges for this wheel */
break;
/* start of wedge */
wpos =3D (pos[w] + wedgest[w][lv]) % 360;
for (lv2 =3D 0; lv2 <=3D wedglen[w][lv]; lv2++)
{ /* throughout extent of wedge */
light[wpos] |=3D (1 << w); /* mark as hole in wheel */
wpos =3D (wpos + 1) % 360; /* go to the next degree */
}
}
}
int main(int argc, char **argv)
{
FILE *fp;
FILE *fout;
int w, f;
int lv, lv2;
fp =3D fopen("spin.in", "r");
fout =3D fopen("spin.out", "w");
assert(fp);
assert(fout);
=20
/* read in the data */
for (lv =3D 0; lv < 5; lv++)
{
fscanf (fp, "%d %d", &speed[lv], &w);
for (lv2 =3D 0; lv2 < w; lv2++)
fscanf (fp, "%d %d", &wedgest[lv][lv2], =
&wedglen[lv][lv2]);
/* mark the rest of the wedges as not existing for this wheel */
for (; lv2 < 5; lv2++)
wedglen[lv][lv2] =3D -1;
}
f =3D 0;
while (t < 360) /* for each time step */
{
memset(light, 0, sizeof(light));
/* mark the degrees we can see through each wheel */
for (lv =3D 0; lv < 5; lv++)
mark_light(lv);
for (lv =3D 0; lv < 360; lv++)
if (light[lv] =3D=3D 31) /* we can shine a light through all five =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -