?? usaco 1_5_4 checker challenge 題解_leokan的blog.mht
字號:
<DIV class=3Dtit>USACO 1.5.4 Checker Challenge =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C227=C8=D5 =D0=C7=C6=DA=C8=D5 =
01:07</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<DIV align=3Dleft>
<H2>USACO 1.5.4 Checker Challenge</H2>
<DIV class=3Dt_msgfont>
<P>Checker Challenge<BR>Examine the 6x6 <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dcheck">check</SPAN>erboard below and note =
that the six=20
<SPAN class=3Dt_tag href=3D"tag.php?name=3Dcheck">check</SPAN>ers =
are arranged=20
on the board so that one and only one is placed in each row and =
each=20
column, and there is never more than one in any diagonal. =
(Diagonals run=20
from southeast to northwest and southwest to northeast and include =
all=20
diagonals, not just the major two.) <BR><BR><BR> =
=20
Column<BR>1 2 3 4 5 6<BR> =
-------------------------<BR>1 | | O=20
| | | | |<BR> -------------------------<BR>2 | | | | O =
| |=20
|<BR> -------------------------<BR>3 | | | | | | O=20
|<BR> -------------------------<BR>4 | O | | | | |=20
|<BR> -------------------------<BR>5 | | | O | | |=20
|<BR> -------------------------<BR>6 | | | | | O |=20
|<BR> -------------------------<BR><BR>The solution =
shown=20
above is described by the sequence 2 4 6 1 3 5, which gives the =
column=20
positions of the checkers for each row from 1 to 6: <BR><BR>ROW 1 =
2 3 4 5=20
6 <BR>COLUMN 2 4 6 1 3 5 <BR><BR>This is one solution to the =
checker=20
challenge. Write a program that finds all unique solution =
sequences to the=20
Checker Challenge. Print the solutions using the column notation =
described=20
above. Print the the first three solutions in numerical order, as =
if the=20
queen positions form the digits of a large number, and then a line =
with=20
the total number of solutions. <BR><BR>Special note: the larger =
values of=20
N require your program to be especially efficient. Do not =
precalculate the=20
value and print it (or even find a formula for it); that's =
cheating. Work=20
on your program until it can solve the problem properly. If you =
insist on=20
cheating, your login to the <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3DUSACO">USACO</SPAN> training pages will be =
removed and=20
you will be disqualified from all <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3DUSACO">USACO</SPAN> competitions. YOU HAVE =
BEEN WARNED.=20
<BR><BR>TIME LIMIT: 1 CPU second<BR>PROGRAM NAME: checker<BR>INPUT =
FORMAT<BR>A single line that contains a single integer N (6 =
<=3D N <=3D=20
13) that is the dimension of the N x N checkerboard. <BR>SAMPLE =
INPUT=20
(file checker.in) <BR>6<BR><BR>OUTPUT FORMAT<BR>The first three =
lines show=20
the first three solutions found, presented as N numbers with a =
single=20
space between them. The fourth line shows the total number of =
solutions=20
found. <BR>SAMPLE OUTPUT (file checker.out)<BR>2 4 6 1 3 5<BR>3 6 =
2 5 1=20
4<BR>4 1 5 2 6 3<BR>4<BR><BR><BR><BR>Checker=20
Challenge<BR><BR>=CC=F8=C6=E5=B5=C4=CC=F4=D5=BD<BR><BR>=D2=EB =
by =20
Jeru<BR><BR><BR><BR>=BC=EC=B2=E9=D2=BB=B8=F6=C8=E7=CF=C2=B5=C46 x=20
=
6=B5=C4=CC=F8=C6=E5=C6=E5=C5=CC=A3=AC=D3=D0=C1=F9=B8=F6=C6=E5=D7=D3=B1=BB=
=B7=C5=D6=C3=D4=DA=C6=E5=C5=CC=C9=CF=A3=AC=CA=B9=B5=C3=C3=BF=D0=D0=A3=AC=C3=
=BF=C1=D0=A3=AC=C3=BF=CC=F5=B6=D4=BD=C7=CF=DF(=B0=FC=C0=A8=C1=BD=CC=F5=D6=
=F7=B6=D4=BD=C7=CF=DF=B5=C4=CB=F9=D3=D0=B6=D4=BD=C7=CF=DF)=C9=CF=B6=BC=D6=
=C1=B6=E0=D3=D0=D2=BB=B8=F6=C6=E5=D7=D3=A1=A3=20
<BR><BR><BR>=C1=D0=BA=C5<BR>1 2 3 4 5 =
6<BR>-------------------------<BR>1 | | O | |=20
| | |<BR>-------------------------<BR>2 | | | | O | |=20
|<BR>-------------------------<BR>3 | | | | | | O=20
|<BR>-------------------------<BR>4 | O | | | | |=20
|<BR>-------------------------<BR>5 | | | O | | |=20
|<BR>-------------------------<BR>6 | | | | | O |=20
=
|<BR>-------------------------<BR><BR>=C9=CF=C3=E6=B5=C4=B2=BC=BE=D6=BF=C9=
=D2=D4=D3=C3=D0=F2=C1=D02 4 6 1 3=20
=
5=C0=B4=C3=E8=CA=F6=A3=AC=B5=DAi=B8=F6=CA=FD=D7=D6=B1=ED=CA=BE=D4=DA=B5=DA=
i=D0=D0=B5=C4=CF=E0=D3=A6=CE=BB=D6=C3=D3=D0=D2=BB=B8=F6=C6=E5=D7=D3=A3=AC=
=C8=E7=CF=C2=A3=BA <BR><BR>=D0=D0=BA=C5 1 2 3 4 5 6 <BR>=C1=D0=BA=C5 2 4 =
6 1 3 5=20
=
<BR><BR>=D5=E2=D6=BB=CA=C7=CC=F8=C6=E5=B7=C5=D6=C3=B5=C4=D2=BB=B8=F6=BD=E2=
=A1=A3=C7=EB=B1=E9=D2=BB=B8=F6=B3=CC=D0=F2=D5=D2=B3=F6=CB=F9=D3=D0=CC=F8=C6=
=E5=B7=C5=D6=C3=B5=C4=BD=E2=A1=A3=B2=A2=B0=D1=CB=FC=C3=C7=D2=D4=C9=CF=C3=E6=
=B5=C4=D0=F2=C1=D0=B7=BD=B7=A8=CA=E4=B3=F6=A1=A3=BD=E2=B0=B4=D7=D6=B5=E4=CB=
=B3=D0=F2=C5=C5=C1=D0=A1=A3=C7=EB=CA=E4=B3=F6=C7=B03=B8=F6=BD=E2=A1=A3=D7=
=EE=BA=F3=D2=BB=D0=D0=CA=C7=BD=E2=B5=C4=D7=DC=B8=F6=CA=FD=A1=A3=20
<BR><BR>=CC=D8=B1=F0=D7=A2=D2=E2: =
=B6=D4=D3=DA=B8=FC=B4=F3=B5=C4N(=C6=E5=C5=CC=B4=F3=D0=A1N x=20
=
N)=C4=E3=B5=C4=B3=CC=D0=F2=D3=A6=B5=B1=B8=C4=BD=F8=B5=C3=B8=FC=D3=D0=D0=A7=
=A1=A3=B2=BB=D2=AA=CA=C2=CF=C8=BC=C6=CB=E3=B3=F6=CB=F9=D3=D0=BD=E2=C8=BB=BA=
=F3=D6=BB=CA=E4=B3=F6=A3=AC=D5=E2=CA=C7=D7=F7=B1=D7=A1=A3=C8=E7=B9=FB=C4=E3=
=BC=E1=B3=D6=D7=F7=B1=D7=A3=AC=C4=C7=C3=B4=C4=E3=B5=C7=C2=BDUSACO =
Training=B5=C4=D5=CA=BA=C5=BD=AB=B1=BB=CE=DE=BE=AF=B8=E6=C9=BE=B3=FD=20
<BR><BR>PROGRAM NAME: checker<BR><BR>INPUT =
FORMAT<BR>=D2=BB=B8=F6=CA=FD=D7=D6N (6 <=3D N=20
<=3D 13) =B1=ED=CA=BE=C6=E5=C5=CC=CA=C7N x =
N=B4=F3=D0=A1=B5=C4=A1=A3 <BR><BR>SAMPLE INPUT(checker.in)=20
<BR>6<BR><BR>OUTPUT =
FORMAT<BR>=C7=B0=C8=FD=D0=D0=CE=AA=C7=B0=C8=FD=B8=F6=BD=E2=A3=AC=C3=BF=B8=
=F6=BD=E2=B5=C4=C1=BD=B8=F6=CA=FD=D7=D6=D6=AE=BC=E4=D3=C3=D2=BB=B8=F6=BF=D5=
=B8=F1=B8=F4=BF=AA=A1=A3=B5=DA=CB=C4=D0=D0=D6=BB=D3=D0=D2=BB=B8=F6=CA=FD=D7=
=D6=A3=AC=B1=ED=CA=BE=BD=E2=B5=C4=D7=DC=CA=FD=A1=A3=20
<BR><BR>SAMPLE OUTPUT(checker.out)<BR>2 4 6 1 3 5 <BR>3 6 2 5 1 4 =
<BR>4 1=20
5 2 6 3 <BR>4</P>
<HR>
<P></P></DIV>
<P><STRONG>USACO 1.5.4 Checker=20
=
Challenge<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE=A3=A8=BA=CD=D6=AE=C7=B0=
=B5=C4=B5=CD=D0=A7=C2=CA=B3=CC=D0=F2=B6=D4=B1=C8=D5=FD=C8=B7=B2=C5=CC=E1=BD=
=BB=B5=C4=A3=A9<BR><BR>=C1=E8=B3=BF1=B5=E3......<BR>=D5=E2=CC=E2=D3=C3=CE=
=BB=D4=CB=CB=E3=D7=F6=A3=AC=D6=AE=C7=B0=CA=C7=C0=ED=C2=DB=A3=AC=B4=D3=C0=ED=
=C2=DB=B5=BD=CA=B5=BC=F9=BB=A8=C1=CB=B2=BB=C9=D9=CA=B1=BC=E4=A3=AC=B5=AB=D6=
=C1=C9=D9=B2=BB=BF=B4=A1=B0m67=A1=B1=B5=C4=CE=BB=D4=CB=CB=E3=CB=B5=C3=F7=CF=
=C2=D7=F6=B5=BD=C1=CB=A1=A3<BR><BR>=D3=C3=C8=FD=B8=F6=CA=FD=C0=B4=B1=ED=CA=
=BE3=D6=D6=B9=A5=BB=F7=B7=BD=CA=BD=B5=C4=B1=BB=B9=A5=BB=F7=B5=BD=B5=C4=CE=
=BB=D6=C3=A3=AC=C1=ED=CD=E2=BA=E1=B5=C4=C4=C7=D2=BB=D6=D6=B9=A5=BB=F7=B7=BD=
=CA=BD=D3=C9=D3=DA=CA=C7dfs=A3=AC=C3=BF=B4=CE=B5=DD=B9=E9=CF=C2=D2=BB=B2=E3=
=A3=AC=D6=B1=BD=D3=BA=F6=C2=D4=A1=A3=CA=FA=D7=C5=B5=C4=B9=A5=BB=F7=B7=BD=CA=
=BD=B5=C4=C4=C4=B8=F6=CA=FD=BF=C9=D2=D4=D6=B1=BD=D3=B1=A3=C1=F4=B5=BD=CF=C2=
=D2=BB=B2=E3=A3=AC=B6=F8=B4=F2=D0=B1=B5=C4=B7=D6=B1=F0=D2=AA=CF=F2=D7=F3=CF=
=F2=D3=D2=D2=C6=D2=BB=CE=BB=A1=A3=20
</STRONG></P>
=
<P><STRONG>=D4=F5=D1=F9=BC=D3=C8=EB=D2=BB=B8=F6=C6=E5=D7=D3=C4=D8=A3=BF=BF=
=C9=D2=D4=D3=C3=D2=BB=B8=F6for=D1=AD=BB=B7=A3=ACp=3D1 shl =
(i-1)=A3=BB=D4=DD=CA=B1=C8=A1=B5=C3=D2=BB=B8=F6=CE=BB=D6=C3=C8=BB=BA=F3=C5=
=D0=B6=CF p and=20
=
pos=CA=C7=B7=F1=B5=C8=D3=DA0.(pos=CA=C7=C4=DC=B7=C5=B5=C4=CE=BB=D6=C3)=B5=
=AB=CA=C7=D5=E2=D1=F9=D7=F6=BB=E1=B3=AC=CA=B1=A1=A3<BR>=C6=E4=CA=B5=BE=CD=
=CA=C7=D0=E8=D2=AA=C8=A1=B5=C3=D7=EE=D3=D2=B1=DF=B5=C4=C4=C7=D2=BB=B8=F61=
=A3=AC=D3=C3=CD=EA=BE=CDpos-p=BE=CD=D0=D0=C1=CB=A1=A3=BF=C9=D2=D4=D3=C3po=
s and=20
(pos xor (pos-1))=A1=A3</STRONG></P>
<P><STRONG>pos and (pos xor=20
=
(pos-1))=B5=C4=D7=F7=D3=C3=BE=CD=CA=C7=C8=A1=B3=F6=D7=EE=D3=D2=B1=DF=B5=C4=
=C4=C7=B8=F61=C0=B4=A1=A3=D2=F2=CE=AApos-1=BD=AB=D7=EE=D3=D2=B1=DF=C4=C7=B8=
=F61=B1=E4=CE=AA0=A3=AC=D3=D2=B1=DF=B5=C40=B1=E4=CE=AA1=A3=AC=D5=E2=D1=F9=
=C0=B4=D2=BB=B4=CExor=D4=CB=CB=E3=B5=C4=BD=E1=B9=FB=BE=CD=CA=C7=D7=EE=D3=D2=
=B1=DF=C4=C7=B8=F61=BB=B9=CA=C71=A3=AC=BA=F3=B1=DF=B5=C40=B1=E4=B3=C9=C1=CB=
1.=B4=CB=CA=B1=C4=C3=CB=FC=BA=CD=D4=AD=CA=FDand=D2=BB=CF=C2=A3=AC=D4=AD=CF=
=C8=D7=EE=D3=D2=B1=DF=B5=C41=BB=B9=CA=C71=A3=AC=BA=F3=B1=DF=B5=C41=D3=C9=D3=
=DA=D4=AD=CA=FD=C4=C7=B8=F6=CE=BB=D6=C3=CA=C70=A3=AC=CB=F9=D2=D4=B1=E4=B3=
=C9=C1=CB0=A1=A3</STRONG></P>
<P><STRONG>pos:100110<BR>pos-1:100101<BR>pos xor =
pso-1:000011<BR>pos and=20
(pos xor (pos-1)):000010</STRONG></P>
=
<P><STRONG>{<BR>TASK:checker<BR>LANG:PASCAL<BR>}<BR>{$D-,L-,Y-,R-,S-,I-,Q=
-}<BR>program=20
checker;<BR>var<BR> =20
n,total,upright,biasl,biasr,finish:longint;<BR>a:array[1..14] of=20
integer;<BR>b,c,d:array[-13..26] of boolean;<BR>procedure=20
init;<BR>begin<BR> =20
assign(input,'checker.in');reset(input);<BR> =20
readln(n);<BR> finish:=3D(1 shl n)=20
-1;<BR> =20
fillchar(b,sizeof(a),true);<BR> =20
fillchar(c,sizeof(b),true);<BR> =20
fillchar(d,sizeof(b),true);<BR> =20
total:=3D0;<BR> =
close(input);<BR>end;</STRONG></P>
<P><STRONG>procedure dfs(t:integer);<BR>var<BR> =20
j,i:integer;<BR>begin<BR>for j:=3D1 to n do<BR> if =
b[j]and=20
c[t+j] and d[t-j] then<BR> =20
begin<BR> =20
a[t]:=3Dj;<BR> =20
b[j]:=3Dfalse;<BR> =20
c[t+j]:=3Dfalse;<BR> =20
d[t-j]:=3Dfalse;<BR> if t=3Dn=20
then<BR> =20
=
begin<BR> &nbs=
p;  =
;=20
=20
=
inc(total);<BR> &nbs=
p; =20
for i:=3D1 to n-1=20
=
do<BR> =
write(a[i],'=20
=
');<BR> =
=
=20
=
writeln(a[n]);<BR> &=
nbsp; &n=
bsp;=20
if total=3D3 then=20
exit;<BR> =20
end<BR> else=20
dfs(t+1);<BR> =20
b[j]:=3Dtrue;<BR> =20
c[t+j]:=3Dtrue;<BR> =20
d[t-j]:=3Dtrue;<BR> =
end;<BR>end;<BR>procedure=20
dfsn(upright,biasl,biasr:longint);<BR>var<BR> =20
pos,p,i:longint;<BR>begin<BR> pos:=3Dfinish and=20
not(upright or biasl or biasr);<BR> while pos =
<>0=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
p:=3Dpos and (pos xor=20
=
(pos-1));<BR> =
=20
=
dec(pos,p);<BR> &nbs=
p; =20
if upright+p=3Dfinish then=20
=
inc(total)<BR>  =
; =20
else dfsn(upright+p,(biasl+p)shl 1,(biasr+p)shr=20
1);<BR> =20
end;<BR>end;</STRONG></P>
<P><STRONG>begin<BR> init;<BR> =
=
assign(output,'checker.out');rewrite(output);<BR> =20
dfs(1);<BR> total:=3D0;<BR> =20
dfsn(0,0,0);<BR> =
writeln(total);<BR> =20
close(output);<BR>end.</STRONG></P>
<P></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6=A3=AC=C7=B0=C3=E6=C6=D5=CD=A8=CB=D1=CB=
=F7=B5=C4=BA=DC=C5=A3</STRONG></P>
<P><STRONG>We use a recursive complete search to simply test all =
boards.=20
The search proceeds by trying to put one checker in each row. We =
keep=20
track of which columns and diagonals already have checkers on them =
in the=20
"col", "updiag", and "downdiag" arrays. </STRONG></P>
<P><STRONG>Since we generate solutions in increasing order, we =
record the=20
first 3 in the "sol" array. </STRONG></P>
<P><STRONG>Symmetry enables us to count the first half of the =
solutions=20
double and avoid calculating the second half. An exception happens =
when N=20
is odd; the odd row needs to be counted once. </STRONG></P>
<P><STRONG>The N>6 lines get the program out of trouble when =
N=3D=3D6,=20
because at that point, the first 3 solutions include one of the =
symmetric=20
answers. </STRONG></P>
<P><STRONG>Since we number rows from 0 to N-1 rather than 1 to N, =
we need=20
to add 1 to each digit as we print (in "printsol"). =
</STRONG></P><PRE><STRONG>/*
TASK: checker
LANG: C
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN 16
int n;
int nsol, nprinted;
char row[MAXN];
FILE *fout;
void
solution() {
int i;
for(i=3D0; i<n; i++) {
if(i !=3D 0) fprintf(fout, " ");
fprintf(fout, "%d", row[i]+1);
}
fprintf(fout, "\n");
}
/* Keep track of whether there is a checker on each column, and =
diagonal. */
char col[MAXN]; /* (i, j) -> j */
char updiag[2*MAXN]; /* (i, j) -> i+j */
char downdiag[2*MAXN]; /* (i, j) -> i-j + N */
/*
* Calculate number of ways to place checkers
* on each row of the board starting at row i and going to row n.
*/
void
nway(i, lim) {
int j;
if(i =3D=3D n) {
nsol++;
if (n > 6 && row[0] < n/2) nsol++;
if (nprinted++ < 3) solution();
return;
}
for(j=3D0; j<lim; j++){
if(!col[j] && !updiag[i+j] && !downdiag[i-j+MAXN]){
row[i] =3D j;
col[j]++;
updiag[i+j]++;
downdiag[i-j+MAXN]++;
nway(i+1,n);
col[j]--;
updiag[i+j]--;
downdiag[i-j+MAXN]--;
}
}
}
main(void) {
FILE *fin =3D fopen("checker.in", "r");
fout =3D fopen("checker.out", "w");
fscanf(fin, "%d", &n);
nway(0, n>6?(n+1)/2:n);
fprintf(fout, "%d\n", nsol);
exit (0);
}
</STRONG></PRE>
<H3>Clever Michael Rybak's Solution</H3>
<P><STRONG>The Ukraine's Michael Rybak removed the 'this row is =
used'=20
search (which obviously at the end of the recursion is a lot of =
wasted=20
iterating) and replaced it with a list of valid rows to use (which =
presumably has but a single element at the end of the recursion). =
His=20
program runs almost 4x faster then N=3D=3D13. =
</STRONG></P><PRE><STRONG>Program Checker;
Var diagPLUS: Array[2..30] Of Boolean;
diagMINUS: Array[-15..15] Of Boolean;
sol: Array[1..15] Of ShortInt;
i,n,found: Longint;
stop: Boolean;
next,prev: Array[0..16] Of ShortInt;
sy: ShortInt;
Procedure Search0(y:ShortInt);
Var x,i:ShortInt;
Begin
If stop Then Exit;
If y=3Dn+1 Then Begin
Inc(found);
If found<4 Then Begin
For i:=3D1 To n-1 Do
Write(sol[i],' ');
Writeln(sol[n]);
End Else
stop:=3DTrue;
Exit;
End;
If sol[y]<>0 Then Begin
Search0(y+1);
Exit;
End;
x:=3Dnext[0];
While x<=3Dn Do Begin
If Not ((diagPLUS[x+y]) Or (diagMINUS[x-y])) Then Begin
sol[y]:=3Dx;
diagPLUS[x+y]:=3DTrue;
diagMINUS[x-y]:=3DTrue;
next[prev[x]]:=3Dnext[x];
prev[next[x]]:=3Dprev[x];
Search0(y+1);
diagPLUS[x+y]:=3DFalse;
diagMINUS[x-y]:=3DFalse;
next[prev[x]]:=3Dx; prev[next[x]]:=3Dx;
End;
x:=3Dnext[x];
End;
sol[y]:=3D0;=20
End;
Procedure Search;
Var x:ShortInt;
Begin
If sy=3Dn+1 Then Begin
Inc(found);
Exit;
End;
If sol[sy]<>0 Then Begin
Inc(sy);
Search;
Dec(sy);
Exit;
End;=20
x:=3Dnext[0];
While x<=3Dn Do Begin
If Not ((diagPLUS[x+sy]) Or (diagMINUS[x-sy])) Then Begin
sol[sy]:=3Dx;
diagPLUS[x+sy]:=3DTrue;
diagMINUS[x-sy]:=3DTrue;
next[prev[x]]:=3Dnext[x];
prev[next[x]]:=3Dprev[x];
Inc(sy);
Search;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -