📄 usaco 2_2_4 party lamps 题解_leokan的blog.mht
字号:
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</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>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.2.4 Party Lamps =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C228=C8=D5 =D0=C7=C6=DA=D2=BB =
23:03</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.2.4 Party Lamps</H2>
<DIV class=3Dt_msgfont>Party Lamps<BR>IOI 98 <BR>To brighten up =
the gala=20
dinner of the IOI'98 we have a set of N (10 <=3D N <=3D 100) =
colored=20
lamps numbered from 1 to N. <BR><BR>The lamps are connected to =
four=20
buttons:<BR><BR><BR>Button 1: When this button is pressed, all the =
lamps=20
change their state: those that are ON are turned OFF and those =
that are=20
OFF are turned ON. <BR>Button 2: Changes the state of all the odd =
numbered=20
lamps. <BR>Button 3: Changes the state of all the even numbered =
lamps.=20
<BR>Button 4: Changes the state of the lamps whose number is of =
the form=20
3xK+1 (with K>=3D0), i.e., 1,4,7,... <BR>A counter C records =
the total=20
number of button presses. <BR><BR>When the party starts, all the =
lamps are=20
ON and the counter C is set to zero. <BR><BR>You are given the =
value of=20
counter C (0 <=3D C <=3D 10000) and the final state of some =
of the lamps=20
after some operations have been executed. Write a program to =
determine all=20
the possible final configurations of the N lamps that are =
consistent with=20
the given information, without repetitions. <BR><BR>PROGRAM NAME:=20
lamps<BR>INPUT FORMAT<BR>Line 1: N <BR>Line =
2: Final value of C <BR>Line 3: =
Some=20
lamp numbers ON in the final configuration, separated by one space =
and=20
terminated by the integer -1. <BR>Line 4: =
Some lamp=20
numbers OFF in the final configuration, separated by one space and =
terminated by the integer -1. <BR>No lamp will be <SPAN =
class=3Dt_tag href=3D"tag.php?name=3Dlis">lis</SPAN>ted twice in =
the=20
input. <BR><BR>SAMPLE INPUT (file lamps.in)=20
<BR>10<BR>1<BR>-1<BR>7 -1<BR><BR>In this case, there are 10 lamps =
and only=20
one button has been pressed. Lamp 7 is OFF in the final =
configuration.=20
<BR><BR>OUTPUT FORMAT<BR>Lines with all the possible final =
configurations=20
(without repetitions) of all the lamps. Each line has N =
characters, where=20
the first character represents the state of lamp 1 and the last =
character=20
represents the state of lamp N. A 0 (zero) stands for a lamp that =
is OFF,=20
and a 1 (one) stands for a lamp that is ON. The lines must be =
ordered from=20
least to largest (as binary numbers). <BR><BR>If there are no =
possible=20
configurations, output a single line with the single word =
`IMPOSSIBLE'=20
<BR><BR>SAMPLE OUTPUT (file=20
lamps.out)<BR>0000000000<BR>0101010101<BR>0110110110<BR><BR>In =
this case,=20
there are three possible final configurations: <BR>All lamps are =
OFF=20
<BR>Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON. =
<BR>Lamps=20
1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.=20
<BR><BR><BR><BR>Party =
Lamps<BR><BR>=C5=C9=B6=D4=B5=C6<BR><BR>IOI98<BR><BR>=D2=EB by=20
=
Leontea<BR><BR>=D4=DAIOI98=B5=C4=BD=DA=C8=D5=D1=E7=BB=E1=C9=CF=A3=AC=CE=D2=
=C3=C7=D3=D0N(10<=3DN<=3D100)=D5=B5=B2=CA=C9=AB=B5=C6=A3=AC=CB=FB=C3=
=C7=B7=D6=B1=F0=B4=D31=B5=BDN=B1=BB=B1=EA=C9=CF=BA=C5=C2=EB=A1=A3<BR>=D5=E2=
=D0=A9=B5=C6=B6=BC=C1=AC=BD=D3=B5=BD=CB=C4=B8=F6=B0=B4=C5=A5=A3=BA<BR><BR=
>=B0=B4=C5=A51=A3=BA=B5=B1=B0=B4=CF=C2=B4=CB=B0=B4=C5=A5=A3=AC=BD=AB=B8=C4=
=B1=E4=CB=F9=D3=D0=B5=C4=B5=C6=A3=BA=B1=BE=C0=B4=C1=C1=D7=C5=B5=C4=B5=C6=BE=
=CD=CF=A8=C3=F0=A3=AC=B1=BE=C0=B4=CA=C7=B9=D8=D7=C5=B5=C4=B5=C6=B1=BB=B5=E3=
=C1=C1=A1=A3=20
=
<BR>=B0=B4=C5=A52=A3=BA=B5=B1=B0=B4=CF=C2=B4=CB=B0=B4=C5=A5=A3=AC=BD=AB=B8=
=C4=B1=E4=CB=F9=D3=D0=C6=E6=CA=FD=BA=C5=B5=C4=B5=C6=A1=A3 =
<BR>=B0=B4=C5=A53=A3=BA=B5=B1=B0=B4=CF=C2=B4=CB=B0=B4=C5=A5=A3=AC=BD=AB=B8=
=C4=B1=E4=CB=F9=D3=D0=C5=BC=CA=FD=BA=C5=B5=C4=B5=C6=A1=A3=20
=
<BR>=B0=B4=C5=A54=A3=BA=B5=B1=B0=B4=CF=C2=B4=CB=B0=B4=C5=A5=A3=AC=BD=AB=B8=
=C4=B1=E4=CB=F9=D3=D0=D0=F2=BA=C5=CA=C73*K+1(K>=3D0)=B5=C4=B5=C6=A1=A3=
=C0=FD=C8=E7=A3=BA1,4,7...=20
=
<BR>=D2=BB=B8=F6=BC=C6=CA=FD=C6=F7C=BC=C7=C2=BC=B0=B4=C5=A5=B1=BB=B0=B4=CF=
=C2=B5=C4=B4=CE=CA=FD=A1=A3<BR>=B5=B1=D1=E7=BB=E1=BF=AA=CA=BC=A3=AC=CB=F9=
=D3=D0=B5=C4=B5=C6=B6=BC=C1=C1=D7=C5=A3=AC=B4=CB=CA=B1=BC=C6=CA=FD=C6=F7C=
=CE=AA0=A1=A3<BR>=C4=E3=BD=AB=B5=C3=B5=BD=BC=C6=CA=FD=C6=F7C(0<=3DC<=
;=3D10000)=C9=CF=B5=C4=CA=FD=D6=B5=BA=CD=BE=AD=B9=FD=C8=F4=B8=C9=B2=D9=D7=
=F7=BA=F3=CB=F9=D3=D0=B5=C6=B5=C4=D7=B4=CC=AC=A1=A3=D0=B4=D2=BB=B8=F6=B3=CC=
=D0=F2=C8=A5=D5=D2=B3=F6=CB=F9=D3=D0=B5=C6=D7=EE=BA=F3=BF=C9=C4=DC=B5=C4=D3=
=EB=CB=F9=B8=F8=B3=F6=D0=C5=CF=A2=CF=E0=B7=FB=B5=C4=D7=B4=CC=AC=A3=AC=B2=A2=
=C7=D2=C3=BB=D3=D0=D6=D8=B8=B4=A1=A3<BR><BR>PROGRAM=20
NAME: lamps<BR>INPUT =
FORMAT<BR>=B2=BB=BB=E1=D3=D0=B5=C6=BB=E1=D4=DA=CA=E4=C8=EB=D6=D0=B3=F6=CF=
=D6=C1=BD=B4=CE=A1=A3<BR>=B5=DA=D2=BB=D0=D0: N=A1=A3 =
<BR>=B5=DA=B6=FE=D0=D0:=20
=
C=D7=EE=BA=F3=CF=D4=CA=BE=B5=C4=CA=FD=D6=B5=A1=A3 <BR>=B5=DA=C8=
=FD=D0=D0: =20
=
=D7=EE=BA=F3=C1=C1=D7=C5=B5=C4=B5=C6,=D3=C3=D2=BB=B8=F6=BF=D5=B8=F1=B7=D6=
=BF=AA=A3=AC=D2=D4-1=CE=AA=BD=E1=CA=F8=A1=A3 <BR>=B5=DA=CB=C4=D0=
=D0: =20
=
=D7=EE=BA=F3=B9=D8=D7=C5=B5=C4=B5=C6,=D3=C3=D2=BB=B8=F6=BF=D5=B8=F1=B7=D6=
=BF=AA=A3=AC=D2=D4-1=CE=AA=BD=E1=CA=F8=A1=A3 <BR><BR>SAMPLE INPUT (file=20
lamps.in)<BR><BR>10<BR>1<BR>-1<BR>7=20
=
-1<BR><BR>=D4=DA=D5=E2=B8=F6=D1=F9=C0=FD=D6=D0=A3=AC=D3=D010=D5=B5=B5=C6=A3=
=AC=D6=BB=D3=D01=B8=F6=B0=B4=C5=A5=B1=BB=B0=B4=CF=C2=A1=A3=D7=EE=BA=F37=BA=
=C5=B5=C6=CA=C7=B9=D8=D7=C5=B5=C4=A1=A3<BR><BR>OUTPUT=20
=
FORMAT<BR><BR>=C3=BF=D2=BB=D0=D0=CA=C7=CB=F9=D3=D0=B5=C6=BF=C9=C4=DC=B5=C4=
=D7=EE=BA=F3=D7=B4=CC=AC(=C3=BB=D3=D0=D6=D8=B8=B4)=A1=A3=C3=BF=D2=BB=D0=D0=
=D3=D0N=B8=F6=D7=D6=B7=FB=A3=AC=B5=DA1=B8=F6=D7=D6=B7=FB=B1=ED=CA=BE1=BA=C5=
=B5=C6=A3=AC=D7=EE=BA=F3=D2=BB=B8=F6=D7=D6=B7=FB=B1=ED=CA=BEN=BA=C5=B5=C6=
=A1=A30=B1=ED=CA=BE=B9=D8=B1=D5=A3=AC1=B1=ED=CA=BE=C1=C1=D7=C5=A1=A3=D5=E2=
=D0=A9=D0=D0=B1=D8=D0=EB=B4=D3=D0=A1=B5=BD=B4=F3=C5=C5=C1=D0=A3=A8=BF=B4=D7=
=F7=CA=C7=B6=FE=BD=F8=D6=C6=CA=FD=A3=A9=A1=A3<BR>=C8=E7=B9=FB=C3=BB=D3=D0=
=BF=C9=C4=DC=B5=C4=D7=B4=CC=AC=A3=AC=D4=F2=CA=E4=B3=F6=D2=BB=D0=D0'IMPOSS=
IBLE'=A1=A3<BR><BR>SAMPLE=20
OUTPUT (file=20
=
lamps.out)<BR><BR>0000000000<BR>0101010101<BR>0110110110<BR><BR>=D4=DA=D5=
=E2=B8=F6=D1=F9=C0=FD=D6=D0=A3=AC=D3=D0=C8=FD=D6=D6=BF=C9=C4=DC=B5=C4=D7=B4=
=CC=AC=A3=BA<BR><BR>=CB=F9=D3=D0=B5=C6=B6=BC=B9=D8=D7=C5=20
=
<BR>1,4,7,10=BA=C5=B5=C6=B9=D8=D7=C5=A3=AC2,3,5,6,8,9=C1=C1=D7=C5=A1=A3 =
<BR>1,3,5,7,9=BA=C5=B5=C6=B9=D8=D7=C5=A3=AC2, 4, 6, 8, =
10=C1=C1=D7=C5=A1=A3</DIV>
<P></P>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.2.4 Party Lamps =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE</STRONG></P>
=
<P><STRONG>=BA=DC=C8=C3=CE=D2=D7=A5=BF=F1=B5=C4=D2=BB=B5=C0=CC=E2=C4=BF=A3=
=AC=D7=F6=C1=CB=BD=D3=BD=FC2=B8=F6=D0=A1=CA=B1...=D3=C9=D3=DA=B3=CC=D0=F2=
=B3=A4=B6=F8=CE=D2=B1=E0=B3=CC=BE=AD=D1=E9=D3=D6=B2=BB=B9=BB=A3=AC=D6=AE=C7=
=B0=B5=F7=CA=D4=C1=CB=BA=DC=BE=C3=B2=C5=C4=DC=B9=FD=D1=F9=C0=FD=CA=FD=BE=DD=
=A1=A3=C3=BF=B8=F6=B0=B4=C5=A5=D6=BB=D3=D0=B0=B4=C6=E6=CA=FD=B4=CE=BB=F2=D5=
=DF=B0=B4=C5=BC=CA=FD=B4=CE=C1=BD=D6=D6=D1=A1=D4=F1=A3=AC=CB=F9=D2=D4=D2=BB=
=B9=B2=D2=B2=BE=CD15=D6=D6=C7=E9=BF=F6=A3=AC=B6=F8=CE=D2=BE=B9=C8=BB=B2=BB=
=D6=AA=CE=AA=BA=CE=B1=E0bfs+=C5=C5=D0=F2=B6=F8=B2=BB=BD=BB=B1=ED......=CE=
=BB=D4=CB=CB=E3=D3=C3=B6=E0=C1=CB=BF=B4=B5=BD=BF=C9=D2=D4=CE=BB=B5=C4=CC=E2=
=C4=BF=C1=A2=BF=CC=BE=CD=CF=EB=CE=BB=C1=CB=A3=AC=C6=E4=CA=B5=B2=BB=CE=BB=BB=
=E1=B8=FC=BC=F2=B5=A5=A1=A3=C4=A3=C4=E2=C1=CB=D2=BB=CF=C2=B7=A2=CF=D6=A3=AC=
=D5=E2=B8=F6=D7=B4=CC=AC=BF=C9=D2=D4=D1=B9=CB=F5=B5=BD6=B8=F6=B5=C6=A3=AC=
=BA=F3=C3=E6=B5=C4=BB=E1=D6=D8=B8=B4=B5=C4=A3=AC=C8=BB=BA=F3=BE=CD=C2=ED=C9=
=CF=BD=AB=C1=BD=D6=D6=CF=DE=D6=C6=B4=E6=C8=EB=C1=BD=B8=F6check=D6=D0=A3=AC=
bfs=B5=C3=B3=F6=CB=F9=D3=D0=C7=E9=BF=F6=A3=AC=B0=B4=CB=B3=D0=F2=C5=D0=B6=CF=
=C3=BF=D6=D6=C7=E9=BF=F6=CA=C7=B7=F1=BF=C9=D0=D0=C8=BB=BA=F3=BD=AB=D5=E2=B8=
=F6=CA=FD=D7=AA=B6=FE=BD=F8=D6=C6=CA=E4=B3=F6=A3=AC=CA=E4=B3=F6=D5=E2=B7=BD=
=C3=E6=CE=D2=D3=D6=CF=EB=D3=C3=CE=BB=D4=CB=CB=E3=A3=A8=BE=CD=D5=E2=C3=B4=BC=
=B8=D1=AD=BB=B7=A3=AC=CE=BB=D4=CB=CB=E3=C4=DC=BF=EC=B6=E0=C9=D9=A3=BF=A3=A1=
)=A3=AC=CF=C8=CA=C7and1=20
shl r>0=A3=AC=B2=BB=B6=D4=BA=F3=CE=D2=D4=D9=D3=C3and 1=3D1,shr =
1=B5=C8=B5=C8=A3=AC=C8=BB=BA=F3=B7=A2=CF=D6=A3=AC=C6=E4=CA=B5=B2=BB=CA=C7=
=D5=E2=C0=EF=CE=CA=CC=E2=A3=AC=CA=C7=C9=CF=C3=E6=B5=C4check=B1=E4=C1=BF=CF=
=DE=D6=C6=B9=D8=B5=C6=B5=C4=CE=D2=CD=FC=C1=CBxor (1=20
shl 6 =
-1)=C8=A1=B7=B4=C1=CB......=B2=BB=B8=C3=D3=C3=CE=BB=D4=CB=CB=E3=B5=C4=CC=E2=
=C4=BF=D3=C3=C1=CB=CE=BB=D4=CB=CB=E3=BE=CD=CA=C7=C2=E9=B7=B3=B0=A1.<BR></=
STRONG></P>
<P><STRONG>Compiling...<BR>Compile: OK</STRONG></P>
<P><STRONG>Executing...</STRONG></P>
<P><STRONG> Test 1: TEST OK [0=20
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]</STRONG></P>
<P><STRONG>{<BR>TASK:lamps<BR>LANG:PASCAL<BR>}<BR>program=20
lamps;<BR>const<BR> index:array[0..5]of=20
integer=3D(6,1,2,3,4,5);<BR>var<BR> =20
n,c,check1,check2,h,t:integer;<BR> =20
queue,count:array[1..20] of integer;<BR>procedure=20
init;<BR>var<BR> =20
x:integer;<BR>begin<BR> =20
assign(input,'lamps.in');reset(input);<BR> =20
readln(n);<BR> readln(c);<BR> =20
check1:=3D0;{=BF=AA=B4=F2=CF=DE=D6=C6}<BR> =
read(x);<BR> =20
while x<>-1 do<BR> =
=
begin<BR> &nbs=
p;=20
x:=3Dx mod 6;if x=3D0 then=20
=
x:=3D6;<BR> &n=
bsp;=20
check1:=3Dcheck1 or (1 shl=20
=
(6-x));<BR> &n=
bsp;=20
read(x);<BR> =20
end;<BR> readln;<BR> =20
read(x);<BR> while x<>-1=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
x:=3Dx mod 6;if x=3D0 then=20
=
x:=3D6;<BR> &n=
bsp;=20
check2:=3Dcheck2 or (1 shl=20
=
(6-x));<BR> &n=
bsp;=20
read(x);<BR> =20
end;<BR> readln;<BR> if n>6 =
then=20
x:=3D6 else x:=3Dn;<BR> check2:=3Dcheck2 xor (1 =
shl 6=20
-1);{=B9=D8=B5=C6=CF=DE=D6=C6}<BR> queue[1]:=3D1 =
shl 6=20
-1;<BR> count[1]:=3D0;<BR> =20
h:=3D1;t:=3D1;<BR> =
close(input);<BR>end;<BR>procedure=20
=
bfs;{bfs=C7=F3=CB=F9=D3=D0=C7=E9=BF=F6}<BR>var<BR> =20
temp,i:integer;<BR> =20
haven:boolean;<BR>begin<BR> while t>=3Dh=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
temp:=3Dqueue[h];<BR> &nbs=
p; =20
temp:=3Dtemp xor=20
=
42;<BR> =
=20
=
haven:=3Dfalse;<BR> =
=20
for i:=3D1 to t=20
=
do<BR> &=
nbsp; =20
if temp=3Dqueue[i]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
haven:=3Dtrue;<BR> &=
nbsp; &n=
bsp; =20
=
break;<BR> &nb=
sp; =20
=
end;<BR>  =
;=20
if not haven=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(t);<BR> &n=
bsp; =20
=
queue[t]:=3Dtemp;<BR> &nbs=
p; =20
=
count[t]:=3Dcount[h]+1;<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
=
temp:=3Dqueue[h];<BR> &nbs=
p; =20
temp:=3Dtemp xor=20
=
21;<BR> =
=20
=
haven:=3Dfalse;<BR> =
=20
for i:=3D1 to t=20
=
do<BR> &=
nbsp; =20
if temp=3Dqueue[i]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
haven:=3Dtrue;<BR> &=
nbsp; &n=
bsp; =20
=
break;<BR> &nb=
sp; =20
=
end;<BR>  =
;=20
if not haven=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(t);<BR> &n=
bsp; =20
=
queue[t]:=3Dtemp;<BR> &nbs=
p; =20
=
count[t]:=3Dcount[h]+1;<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
=
temp:=3Dqueue[h];<BR> &nbs=
p; =20
temp:=3Dtemp xor=20
=
36;<BR> =
=20
=
haven:=3Dfalse;<BR> =
=20
for i:=3D1 to t=20
=
do<BR> &=
nbsp; =20
if temp=3Dqueue[i]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
haven:=3Dtrue;<BR> &=
nbsp; &n=
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -