📄 usaco 1_4_3 arithmetic progressions 题解_leokan的blog.mht
字号:
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 1.4.3 Arithmetic Progressions =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C225=C8=D5 =D0=C7=C6=DA=CE=E5 =
18:40</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.4.3 Arithmetic Progressions</H2>
<DIV class=3Dt_msgfont>
<P>Arithmetic Progressions<BR><BR>An arithmetic progression is a =
sequence=20
of the form a, a+b, a+2b, ..., a+nb where n=3D0,1,2,3,... . For =
this=20
problem, a is a non-negative integer and b is a positive integer.=20
<BR><BR>Write a program that finds all arithmetic progressions of =
length n=20
in the set S of bisquares. The set of bisquares is defined as the =
set of=20
all integers of the form p2 + q2 (where p and q are non-negative=20
integers). <BR><BR>PROGRAM NAME: ariprog<BR>INPUT FORMAT<BR>Line=20
1: N (3 <=3D N <=3D 25), the length of =
progressions for=20
which to search <BR>Line 2: M (1 <=3D M =
<=3D=20
250), an upper bound to limit the search to the bisquares with 0 =
<=3D p,q=20
<=3D M. <BR><BR>SAMPLE INPUT (file ariprog.in)=20
<BR>5<BR>7<BR><BR>OUTPUT FORMAT<BR>If no sequence is found, a =
singe line=20
reading `NONE'. Otherwise, output one or more lines, each with two =
integers: the first element in a found sequence and the difference =
between=20
consecutive elements in the same sequence. The lines should be =
ordered=20
with smallest-difference sequences first and smallest starting =
number=20
within those sequences first. <BR><BR>There will be no more than =
10,000=20
sequences. <BR><BR>SAMPLE OUTPUT (file ariprog.out)<BR>1 4<BR>37 =
4<BR>2=20
8<BR>29 8<BR>1 12<BR>5 12<BR>13 12<BR>17 12<BR>5 20<BR>2=20
24<BR><BR><BR><BR>Arithmetic =
Progressions<BR><BR>=B5=C8=B2=EE=CA=FD=C1=D0<BR><BR>=D2=EB by tim=20
=
green<BR><BR>=D2=BB=B8=F6=B5=C8=B2=EE=CA=FD=C1=D0=CA=C7=D2=BB=B8=F6=C4=DC=
=B1=ED=CA=BE=B3=C9a, a+b, a+2b,..., a+nb=20
=
(n=3D0,1,2,3,...)<BR>=D4=DA=D5=E2=B8=F6=CE=CA=CC=E2=D6=D0a=CA=C7=D2=BB=B8=
=F6=B7=C7=B8=BA=B5=C4=D5=FB=CA=FD=A3=ACb=CA=C7=D5=FD=D5=FB=CA=FD=A1=A3<BR=
>=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=C0=B4=D5=D2=B3=F6=D4=DA=CB=AB=C6=BD=B7=BD=
=CA=FD=BC=AF=BA=CFS=D6=D0=B3=A4=B6=C8=CE=AAn=B5=C4=B5=C8=B2=EE=CA=FD=C1=D0=
=A1=A3<BR>=CB=AB=C6=BD=B7=BD=CA=FD=BC=AF=BA=CF=CA=C7=CB=F9=D3=D0=C4=DC=B1=
=ED=CA=BE=B3=C9p2=A3=ABq2=B5=C4=CA=FD=B5=C4=BC=AF=BA=CF=A1=A3<BR><BR>PROG=
RAM=20
NAME: ariprog<BR><BR>INPUT =
FORMAT<BR><BR>=B5=DA=D2=BB=D0=D0: N(3<=3D=20
=
N<=3D25),=D2=AA=D5=D2=B5=C4=B5=C8=B2=EE=CA=FD=C1=D0=B5=C4=B3=A4=B6=C8=A1=
=A3 <BR>=B5=DA=B6=FE=D0=D0: M(1<=3D=20
M<=3D250),<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CB%D1%CB%F7">=CB=D1=CB=F7</SPAN>=CB=AB=C6=BD=B7=BD=
=CA=FD=B5=C4=C9=CF=BD=E70 <=3D p,q <=3D M=A1=A3=20
<BR><BR>SAMPLE INPUT (file ariprog.in) <BR>5<BR>7<BR><BR>OUTPUT=20
=
FORMAT<BR>=C8=E7=B9=FB=C3=BB=D3=D0=D5=D2=B5=BD=CA=FD=C1=D0,=CA=E4=B3=F6`N=
ONE'=A1=A3<BR>=C8=E7=B9=FB=D5=D2=B5=BD=C1=CB=A3=AC=CA=E4=B3=F6=D2=BB=D0=D0=
=BB=F2=B6=E0=D0=D0,=20
=
=C3=BF=D0=D0=D3=C9=D3=DA=B6=FE=B8=F6=D5=FB=CA=FD=D7=E9=B3=C9:a,b<BR>=D5=E2=
=D0=A9=D0=D0=D3=A6=B8=C3=CF=C8=B0=B4b<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%C5%C5%D0%F2">=C5=C5=D0=F2</SPAN>=D4=D9=B0=B4a<SPA=
N class=3Dt_tag=20
=
href=3D"tag.php?name=3D%C5%C5%D0%F2">=C5=C5=D0=F2</SPAN>=A1=A3<BR>=BD=AB=B2=
=BB=BB=E1=D3=D0=D6=BB=B6=E0=D3=DA10,000=B8=F6=B5=C8=B2=EE=CA=FD=C1=D0=A1=A3=
<BR><BR>SAMPLE=20
OUTPUT (file ariprog.out)<BR>1 4<BR>37 4<BR>2 8<BR>29 8<BR>1 =
12<BR>5=20
12<BR>13 12<BR>17 12<BR>5 20<BR>2 24</P>
<P></P>
<HR>
</DIV>
<P></P>
<P><STRONG>USACO 1.4.3 Arithmetic Progressions<BR></STRONG></P>
=
<P><STRONG>=D5=E2=B5=C0=CC=E2=BE=CD=B0=B4=CC=E2=C4=BF=D2=AA=C7=F3=C4=A3=C4=
=E2=D7=F6=BA=C3=C1=CB=A3=AC=B2=BB=BC=F4=D6=A6=B5=C4=BB=B0=BB=E1=B3=AC=B5=C4=
=BA=DC=B2=D2=A3=AC=C3=BB=BC=F4=D6=A6=B5=DA=B1=C8=BD=CF=BC=AB=CF=DE=B5=C4=CA=
=FD=BE=DD=CE=D2=D7=D4=BC=BA=D5=E2=C0=EF=CA=C71=C3=EB=B6=E0=B3=F6=BD=E2=A3=
=AC=B6=F8=B5=BD=C1=CBusaco=C4=C7=C0=EF=CA=B1=BC=E4=D3=A6=B8=C3=BB=E1=B8=FC=
=B6=E0=A3=AC=CB=F9=D2=D4=BC=F4=D6=A6=CA=C7=B1=D8=C8=BB=B5=C4=A1=A3=D7=A2=D2=
=E2=B5=BD=CC=E2=C4=BF=D2=AA=C7=F3=CF=C8=B0=B4b=C5=C5=D0=F2=D4=D9=B0=B4a=C5=
=C5=D0=F2=A3=AC=D5=E2=D1=F9=C8=E7=B9=FB=CF=C8=D1=AD=BB=B7b=D4=D9=D1=AD=BB=
=B7a=B5=C4=BB=B0=D2=AA=BC=F4=D6=A6=B1=C8=BD=CF=C2=E9=B7=B3=A3=AC=CB=F9=D2=
=D4=CE=D2=BB=B9=CA=C7=CF=C8=D1=AD=BB=B7a=D4=D9=D1=AD=BB=B7b=B3=F6=BD=E2=D7=
=EE=BA=F3=D4=D9=C5=C5=D0=F2=A1=A3=BC=F4=D6=A6=A3=BAa=D5=E2=B8=F6=CA=FD=B1=
=BE=C9=ED=D0=E8=D2=AA=B7=FB=BA=CF=CC=F5=BC=FE=A3=AC=D5=E2=D1=F9=D3=C9=D3=DA=
=CA=C7=CD=E2=D1=AD=BB=B7=A3=AC=CB=F9=D2=D4=BB=E1=BC=F5=B5=C4=B1=C8=BD=CF=B6=
=E0=A3=AC=B5=DA=B6=FE=A3=ACa+b*(n-1){=CA=FD=C1=D0=D7=EE=BA=F3=D2=BB=B8=F6=
=CA=FD}=D2=AA=B7=FB=BA=CF=CC=F5=BC=FE=A3=AC=D5=E2=C0=EF=CA=C7=C4=DA=D1=AD=
=BB=B7=A3=AC=B5=AB=CA=C7=D2=B2=C4=DC=BC=F4=B2=BB=C9=D9=A1=A3=BC=F5=CD=EA=BA=
=F3=A3=AC=D7=EE=B4=F3=CA=FD=BE=DD2.8s=B3=F6=A1=A3</STRONG></P>
=
<P><STRONG>=C1=ED=CD=E2=D5=E2=CC=E2=CE=D2=BB=B9=D7=A2=D2=E2=B5=BD=D2=BB=B5=
=E3=A3=AC=BF=EC=C5=C5=CA=C7=B2=BB=CE=C8=B6=A8=B5=C4=A3=AC=CB=F9=D2=D4=D3=C3=
=BF=EC=C5=C5=C5=C5b=B5=C4=BB=B0=D4=AD=B1=BE=D5=FD=D0=F2=B5=C4a=BB=E1=B1=E4=
=C2=D2=D0=F2=A1=A3</STRONG></P>
<P><STRONG>USER: Leo Kan [gba19911]<BR>TASK: ariprog<BR>LANG:=20
PASCAL</STRONG></P>
<P><STRONG>Compiling...<BR>Compile: OK</STRONG></P>
<P><STRONG>Executing...<BR> Test 1: =
TEST OK=20
[0.004 secs]<BR> Test 2: TEST OK [0=20
secs]<BR> Test 3: TEST OK [0=20
secs]<BR> Test 4: TEST OK [0.004=20
secs]<BR> Test 5: TEST OK [0.012=20
secs]<BR> Test 6: TEST OK [0.088=20
secs]<BR> Test 7: TEST OK [1.22=20
secs]<BR> Test 8: TEST OK [2.724=20
secs]<BR> Test 9: TEST OK [2.824=20
secs]</STRONG></P>
<P><STRONG>All tests OK.<BR>Your program ('ariprog') produced all =
correct=20
answers! This is your<BR>submission #3 for this problem.=20
Congratulations!</STRONG></P>
<P><STRONG>Here are the test data inputs:</STRONG></P>
<P><STRONG>------- test 1 -------<BR>3<BR>2<BR>------- test 2=20
-------<BR>5<BR>7<BR>------- test 3 -------<BR>14<BR>10<BR>------- =
test 4=20
-------<BR>10<BR>13<BR>------- test 5 =
-------<BR>12<BR>50<BR>------- test=20
6 -------<BR>18<BR>100<BR>------- test 7 =
-------<BR>21<BR>200<BR>-------=20
test 8 -------<BR>22<BR>250<BR>------- test 9=20
-------<BR>25<BR>250</STRONG></P><STRONG>
=
<P><BR>{$D-,L-,Y-,R-,S-,I-,Q-}<BR>{<BR>TASK:ariprog<BR>LANG:PASCAL<BR>}<B=
R>program=20
ariprog;<BR>type<BR> arr=3Darray[1..2] of=20
word;<BR>var<BR> bissquare:array[0..126000] of=20
boolean;<BR> a:array[1..500000] of=20
char;<BR> ans:array[1..100000] of=20
arr;<BR> n,m:integer;<BR>procedure=20
init;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(input,'ariprog.in');reset(input);<BR> =20
readln(n);<BR> readln(m);<BR> =20
close(input);<BR> =20
fillchar(bissquare,sizeof(bissquare),false);<BR> =
for=20
i:=3D0 to m do<BR> for =
j:=3D0 to m=20
=
do<BR> =
bissquare[i*i+j*j]:=3Dtrue;<BR>end;<BR>procedure swap(var=20
a,b:arr);<BR>var<BR> =20
c:arr;<BR>begin<BR> =
c:=3Da;<BR> =20
a:=3Db;<BR> b:=3Dc;<BR>end;<BR>procedure=20
work;<BR>var<BR> =
i,j,k,p:longint;<BR> =20
t:boolean;<BR>begin<BR> =
p:=3D0;<BR> for=20
i:=3D0 to m*m =
do{=C3=B6=BE=D9a}<BR> if=20
bissquare[i] =
then{=BC=F4=D6=A6=D2=BB}<BR> =
for=20
j:=3D1 to (m*m*2-i) div (n-1)=20
=
do{=C3=B6=BE=D9b}<BR> &nbs=
p; =20
=
begin<BR> &nbs=
p; =20
if not bissquare[i+j*(n-1)] then=20
=
continue;{=BC=F4=D6=A6=B6=FE}<BR> &nbs=
p; =20
=
t:=3Dtrue;<BR>  =
; =20
for k:=3D0 to n-1=20
=
do<BR> &=
nbsp; =20
if not bissquare[i+j*k]=20
=
then<BR>  =
; =
=20
=
begin<BR> &nbs=
p;  =
; =20
=
t:=3Dfalse;<BR> &nbs=
p;  =
; =20
=
break;<BR> &nb=
sp; &nbs=
p;=20
=
end;<BR>  =
; =20
if t=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
inc(p);<BR> &n=
bsp; &nb=
sp;=20
=
ans[p,1]:=3Dj;<BR> &=
nbsp; &n=
bsp; =20
=
ans[p,2]:=3Di;<BR> &=
nbsp; =20
=
end;<BR>  =
;=20
end;<BR> =20
=
assign(output,'ariprog.out');rewrite(output);<BR> =20
settextbuf(output,a,sizeof(a));<BR> if p=3D0 =
then begin=20
writeln('NONE');exit;end;<BR> =20
{qs(1,p);}<BR> =
{sort(1,p);}<BR> =20
t:=3Dtrue;<BR> while t=20
=
do{=C3=B0=C5=DD=C5=C5=D0=F2}<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
t:=3Dfalse;<BR> &nbs=
p; =20
for i:=3D1 to p-1=20
=
do<BR> &=
nbsp; =20
if ans[i,1]>ans[i+1,1]=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
swap(ans[i],ans[i+1]);<BR>  =
; =
=20
=
t:=3Dtrue;<BR>  =
; =20
end;<BR> =20
end;<BR> for i:=3D1 to p=20
do<BR> =
writeln(ans[i,2],'=20
',ans[i,1]);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.</P>
<P>
<P></P>
=
<P>Usaco=B5=C4=B7=D6=CE=F6=A3=AC=CB=FB=B5=DA=D2=BB=D6=D6=B7=BD=B7=A8=B2=EE=
=A3=AC=B5=AB=CB=FB=BC=F5=B5=C4=C7=BF=A3=A1=B5=DA=B6=FE=D6=D6even faster=20
=B5=C4=BA=CD=CE=D2=B5=C4=B2=EE=B2=BB=B6=E0=A3=AC=B2=BB=B9=FD=D2=AA=D1=A7=CF=
=B0=D2=BB=CF=C2=CB=FC=B5=C4=BF=EC=C5=C5=A3=A8=CB=FB=D4=F5=C3=B4=D7=F6=B5=BD=
=CE=C8=B6=A8=B5=C4=A3=A9=A1=A3</P>
<P>This can be done by brute force, enumerating over all possible=20
sequences. It has to be done a little carefully in order to get it =
to run=20
in time, however.</P>
<P>Precalculate the bisquares, first of all. Calculate both a =
sorted list=20
of the bisquares, along with a boolean array saying whether each =
number=20
between 1 and 125000 (the maximum bisquare possible, for p,q < =
250) is=20
a bisquare.</P>
<P>Go through the skips in increasing order, starting at 1, and =
continuing=20
along as the sequence starting at 1 with that skip doesn't exceed =
the=20
maximum bisquare. For each bisquare, determine if the sequence =
starting at=20
that location and with the current skip value consists of all of=20
bisquares. If so, output it.</P>
<P>Here is the solution of Felix Arends from Germany (modified by =
Iran's=20
Saber Fadaee):</P><PRE>#include <stdio.h>
#include <assert.h>
#include <string>
using namespace std;
// open files
FILE *fin =3D fopen ("ariprog.in", "r");
FILE *fout =3D fopen ("ariprog.out", "w");
// global variables
unsigned int N, M, maxMM;
unsigned int numbers [65000];
unsigned int number_size =3D 0;
unsigned char num_available [125001];
unsigned char dist_available [125001];
int have_res =3D 0;
int skipstep =3D 1;
// read the input
int read_input () {
fscanf (fin, "%d %d", &N, &M);
return 0;
}
int cmp_int (const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
void asm_num (int a, int b) {
for (unsigned int n =3D 1; n < N; n++)
if (num_available [a + n * b] =3D=3D 0) return;
fprintf (fout, "%d %d\n", a, b);
have_res ++;
if (have_res=3D=3D1)
skipstep =3D b;
}
void asm_num () {
for (unsigned int b =3D 1; b < maxMM; b+=3Dskipstep) {
if (dist_available [b]) {
for (unsigned int p =3D 0; p < number_size && =
numbers [p] + (N -
1) * b <=3D maxMM; p++)
asm_num (numbers [p], b);
}
}
}
int process () {
memset (num_available, 0, sizeof (unsigned char) * 125001);
memset (dist_available, 0, sizeof (unsigned char) * 125001);
for (unsigned int m1 =3D 0; m1 <=3D M; m1++) {
for (unsigned int m2 =3D m1; m2 <=3D M; m2++) {
int n =3D m1 * m1 + m2 * m2;
if (!num_available [n]) {
num_available [n] =3D 1;
numbers [number_size++] =3D n;
}
}
}
qsort (numbers, number_size, sizeof (unsigned int), cmp_int);
maxMM =3D M * M + M * M;
for (unsigned int n1 =3D 0; n1 < number_size; n1++) {
unsigned int _n1 =3D numbers [n1];
for (unsigned int n2 =3D n1 + 1; n2 < number_size && =
_n1 + (numbers
[n2] - _n1) * (N - 1) <=3D maxMM; n2++) {
assert (numbers [n2] - _n1 >=3D 0 && numbers [n2] =
- _n1 < 125001);
if (num_available [_n1 + (numbers [n2] - _n1) * (N - 1)] =
&&
num_available [_n1 + (numbers [n2] - _n1) * (N - 2)])
dist_available [numbers [n2] - _n1] =3D true;
}
}
asm_num ();
if (!have_res) fprintf (fout, "NONE\n");
return 0;
}
int main () {
read_input ();
process ();
fclose (fin);
fclose (fout);
return 0;
}</PRE>
<P>Here is an even faster solution of "UaE =
ProGrammeR":</P><PRE>#include <fstream>
#include <iostream>
using namespace std;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -