📄 usaco 1_2_4 palindromic squares 题解_leokan的blog.mht
字号:
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.2.4 Palindromic Squares</H2>
<DIV class=3Dt_msgfont>
<P>Palindromic Squares<BR>Rob Kolstad <BR>Palindromes are numbers =
that=20
read the same forwards as backwards. The number 12321 is a typical =
palindrome. <BR><BR>Given a number base B (2 <=3D B <=3D 20 =
base 10),=20
print all the integers N (1 <=3D N <=3D 300 base 10) such =
that the=20
square of N is palindromic when expressed in base B; also print =
the value=20
of that palindromic square. Use the letters 'A', 'B', and so on to =
represent the digits 10, 11, and so on. <BR><BR>Print both the =
number and=20
its square in base B. <BR><BR>PROGRAM NAME: palsquare<BR>INPUT =
FORMAT<BR>A=20
single line with B, the base (specified in base 10). <BR>SAMPLE =
INPUT=20
(file palsquare.in) <BR>10<BR><BR>OUTPUT FORMAT<BR>Lines with two =
integers=20
represented in base B. The first integer is the number whose =
square is=20
palindromic; the second integer is the square itself. <BR>SAMPLE =
OUTPUT=20
(file palsquare.out)<BR>1 1<BR>2 4<BR>3 9<BR>11 121<BR>22 =
484<BR>26=20
676<BR>101 10201<BR>111 12321<BR>121 14641<BR>202 40804<BR>212=20
44944<BR>264 69696<BR><BR><BR><BR>Palindromic =
Squares<BR><BR>=BB=D8=CE=C4=C6=BD=B7=BD=CA=FD<BR>Rob=20
Kolstad <BR><BR>=D2=EB by=20
=
!Starliu<BR><BR>=BB=D8=CE=C4=CA=FD=CA=C7=D6=B8=B4=D3=D7=F3=CF=F2=D3=D2=C4=
=EE=BA=CD=B4=D3=D3=D2=CF=F1=D7=F6=C4=EE=B6=BC=D2=BB=D1=F9=B5=C4=CA=FD=A1=A3=
=C8=E712321=BE=CD=CA=C7=D2=BB=B8=F6=B5=E4=D0=CD=B5=C4=BB=D8=CE=C4=CA=FD=A1=
=A3<BR><BR>=B8=F8=B6=A8=D2=BB=B8=F6=BD=F8=D6=C6B(2<=3DB<=3D20=CA=AE=
=BD=F8=D6=C6)=A3=AC=CA=E4=B3=F6=CB=F9=D3=D0=B5=C4=B4=F3=D3=DA=B5=C8=D3=DA=
1=D0=A1=D3=DA=B5=C8=D3=DA300=C7=D2=CB=FC=B5=C4=C6=BD=B7=BD=D3=C3B=BD=F8=D6=
=C6=B1=ED=CA=BE=CA=B1=CA=C7=BB=D8=CE=C4=CA=FD=B5=C4=CA=FD=A1=A3=D3=C3=A1=AF=
A=A1=AF,=A1=AFB=A1=AF=A1=AD=A1=AD=B1=ED=CA=BE10=A3=AC11=B5=C8=B5=C8=A1=A3=
<BR><BR>PROGRAM=20
NAME: palsquare<BR>INPUT =
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=D2=BB=B8=F6=B5=A5=B6=C0=B5=C4=D5=FB=CA=
=FDB(B=D3=C3=CA=AE=BD=F8=D6=C6=B1=ED=CA=BE)=A1=A3<BR><BR>SAMPLE=20
INPUT (file palsquare.in) <BR>10<BR>OUTPUT =
FORMAT<BR>=C3=BF=D0=D0=C1=BD=B8=F6<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%D7%D6">=CA=FD=D7=D6</SPAN>=A3=AC=B5=DA=B6=FE=
=B8=F6=CA=FD=CA=C7=B5=DA=D2=BB=B8=F6=CA=FD=B5=C4=C6=BD=B7=BD=A3=AC=C7=D2=B5=
=DA=B6=FE=B8=F6=CA=FD=CA=C7=BB=D8=CE=C4=CA=FD=A1=A3(=D7=A2=D2=E2:=D5=E2=C1=
=BD=B8=F6=CA=FD=B6=BC=D3=A6=B8=C3=D4=DAB=C4=C7=B8=F6=BD=F8=D6=C6=CF=C2)<B=
R><BR>SAMPLE=20
OUTPUT (file palsquare.out)<BR>1 1<BR>2 4<BR>3 9<BR>11 121<BR>22 =
484<BR>26=20
676<BR>101 10201<BR>111 12321<BR>121 14641<BR>202 40804<BR>212=20
44944<BR>264 69696</P>
=
<P><STRONG>2008=C4=EA=B5=DA=D2=BB=B4=CE=B7=A2=CE=C4=D5=C2=A3=AC0:31=A3=AC=
=CE=D2=D3=AD=C0=B4=C1=CB2008=C4=EA=B5=C4=B5=DA=D2=BB=B4=CE1=B4=CEAC=A3=A1=
=CF=A3=CD=FB=C4=DC=B8=F8=CE=D2=D5=FB1=B8=F62008=C4=EA=B4=F8=C0=B4=BA=C3=D4=
=CB=A3=A1=A3=A1</STRONG></P>
=
<P><STRONG>=D5=E2=CC=E2=CE=D2=CF=C8=B4=E6=B4=A2=C1=CB1-300=C3=BF=B8=F6=CA=
=FD=B5=C4=C6=BD=B7=BD=A3=AC=C8=BB=BA=F3=B4=D31=B5=BD300=D6=F0=B8=F6=CA=FD=
check=D2=BB=B4=CE=CB=FC=CA=C7=B7=F1=BB=D8=CE=C4=A3=AC=CA=C7=D4=F2=CA=E4=B3=
=F6=A1=A3</STRONG></P><PRE><STRONG>TASK: palsquare
LANG: PASCAL
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0 secs]
Test 2: TEST OK [0.004 secs]
Test 3: TEST OK [0.004 secs]
Test 4: TEST OK [0.004 secs]
Test 5: TEST OK [0 secs]
Test 6: TEST OK [0.004 secs]
Test 7: TEST OK [0 secs]
Test 8: TEST OK [0.004 secs]
All tests OK.
</STRONG><P><STRONG>YOUR PROGRAM ('palsquare') WORKED FIRST TIME! =
That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.
</STRONG></P></PRE>
<P><STRONG>Here are the test data =
inputs:<BR></STRONG></P><PRE><STRONG>------- test 1 -------
10
------- test 2 -------
2
------- test 3 -------
5
------- test 4 -------
11
------- test 5 -------
15
------- test 6 -------
18
------- test 7 -------
20
------- test 8 -------
3
----------------------
</STRONG></PRE>
<P><STRONG>Keep up the good work! <BR></STRONG></P><PRE> </PRE>
<P><STRONG>Thanks for your submission!</STRONG></P>
<P></P>
<P><STRONG>=D4=B4=C2=EB=A3=BA</STRONG></P><STRONG>
<P><BR>{<BR>TASK:palsquare<BR>LANG:PASCAL<BR>}<BR>program=20
palsquare;<BR>var<BR> =
r:integer;<BR> =20
sq:array[1..300]of longint;<BR> ch:array[0..20] =
of=20
char;</P>
<P>procedure initsquare;<BR>var<BR> =20
i:integer;<BR>begin<BR> for i:=3D1 to 300=20
do<BR> =
sq[i]:=3Di*i;<BR>end;</P>
<P>procedure init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'palsquare.in');reset(input);<BR> =20
readln(r);<BR> for i:=3D0 to 9 do=20
ch[i]:=3Dchr(48+i);<BR> for i:=3D10 to 20 do=20
ch[i]:=3Dchr(55+i);<BR> close(input);</P>
<P>end;</P>
<P>procedure check(x:longint);<BR>var<BR> =20
i,p,pp:integer;<BR> =
n:longint;<BR> =20
a,b:array[1..20] of integer;<BR> =20
t:boolean;<BR>begin<BR> =
n:=3Dsq[x];<BR> =20
p:=3D0;<BR> while n>0=20
do<BR> =20
begin<BR> =20
inc(p);<BR> a[p]:=3Dn =
mod=20
r;<BR> n:=3Dn div=20
r;<BR> =20
end;<BR> {for i:=3Dp downto 1 do=20
write(a[i]);}<BR> =
t:=3Dtrue;<BR> for=20
i:=3D1 to p shr 1 do<BR> =
if=20
a[i]<>a[p-i+1] then begin =
t:=3Dfalse;break;end;<BR> =20
if t then<BR> =20
begin<BR> =20
pp:=3D0;<BR> while =
x>0=20
=
do<BR> =
=
begin<BR> &nbs=
p;=20
=
inc(pp);<BR> &=
nbsp;=20
b[pp]:=3Dx mod=20
=
r;<BR> =
x:=3Dx div=20
=
r;<BR> =
end;<BR> for i:=3Dpp =
downto 1 do=20
write(ch[b[i]]);<BR> =
write('=20
');<BR> for i:=3Dp =
downto 1 do=20
write(ch[a[i]]);<BR> =20
writeln;<BR> end;</P>
<P>end;</P>
<P>procedure main;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
=
assign(output,'palsquare.out');rewrite(output);<BR> =
for=20
i:=3D1 to 300 do<BR> =20
check(i);<BR> =20
=
close(output);<BR>end;<BR>begin<BR>initsquare;<BR>init;<BR>main;<BR>end.<=
/P>
=
<P>=BF=B4=CF=C2USACO=B5=C4=B7=D6=CE=F6=B0=C9(c=D3=EF=D1=D4=A3=A9=A3=AC=BA=
=CD=CE=D2=B5=C4=D7=F6=B7=A8=B2=EE=B2=BB=B6=E0=A1=A3</P>
<P>We generate all the squares from 1 to 300 and check to see =
which are=20
palindromes.</P><PRE>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>
#include <math.h>
/* is string s a palindrome? */
int
ispal(char *s)
{
char *t;
t =3D s+strlen(s)-1;
for(t=3Ds+strlen(s)-1; s<t; s++, t--)
if(*s !=3D *t)
return 0;
return 1;
}
/* put the base b representation of n into s: 0 is represented by "" */
void
numbconv(char *s, int n, int b)
{
int len;
if(n =3D=3D 0) {
strcpy(s, "");
return;
}
/* figure out first n-1 digits */
numbconv(s, n/b, b);
/* add last digit */
len =3D strlen(s);
s[len] =3D "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[n%b];
s[len+1] =3D '\0';
}
void
main(void)
{
char s[20];
char t[20];
int i, base;
FILE *fin, *fout;
fin =3D fopen("palsquare.in", "r");
fout =3D fopen("palsquare.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &base);
for(i=3D1; i <=3D 300; i++) {
numbconv(s, i*i, base);
if(ispal(s)) {
numbconv(t, i, base);
fprintf(fout, "%s %s\n", t, s);
}
}
exit(0);</PRE></STRONG></DIV></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/9be0dc09cf6f8286d0581b09.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.2.3 Name That Number =CC=E2=BD=E2', 'USACO =
1.2.3 Name That Number =
...','/leokan/blog/item/060b0224fcf8c737c995597f.html'];
var post =3D =
[true,'=D0=C2=C4=EA=B5=BD=A3=A1','=D0=C2=C4=EA=B5=BD=A3=A1', =
'/leokan/blog/item/467ad862d933fad9e7113aa6.html'];
if(pre[0] || post[0]){
document.write('<div =
style=3D"height:5px;line-height:5px;"> </div><div id=3D"in_nav">');
if(pre[0]){
document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' + pre[2] + '</a> ');
}
if(post[0]){
document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' + post[2] + '</a>');
}
document.write('</div>');
}
/*]]>*/
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
TEXT-DECORATION: none
}
</STYLE>
<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
if(arg.length <=3D 1) return false;
var hasMore =3D arg[0];
var D=3Dfunction(A,B){A[A.length]=3DB;}
if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);
var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
D(html, '<tr>');
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
D(html, new Array(10).join('\u3000'));
D(html, '</td>');
if(arg[i + 1][0] !=3D "")
D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>•</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
else
D(html, '<td> </td><td> </td>');
D(html, '</tr>');
}
if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%201%2E2%2E4=
%20Palindromic%20Squares%20%CC%E2%BD%E2&item=3D9be0dc09cf6f8286d0581b09">=
=B8=FC=B6=E0>></a></td></tr>');
D(html, '</table></div><div class=3D"line"> </div>');
var div =3D document.getElementById('in_related_tmp');
if(div){
div.innerHTML =3D html.join('');
while(div.firstChild){
div.parentNode.insertBefore(div.firstChild, div);
}
div.parentNode.removeChild(div);
}
}
if(RelatedDocData =3D=3D -1){ // not supported xhr
var script =3D document.createElement('script');
script.type =3D 'text/javascript';
script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%201%2E2%2E4%20Palindromic%20Squares%20=
%CC%E2%BD%E2&item=3D9be0dc09cf6f8286d0581b09&t=3D' + new =
Date().getTime();
document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
GetAndEval =3D true;
}else{
eval(RelatedDocData);
}
/*]]>*/
</SCRIPT>
<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>
var g_spAnnony=3Dtrue;
var g_read=3D[
=09
["hulucheng","889768756c756368656e675f3331384802","hulucheng_318"],
{}
];
g_read.length=3Dg_read.length-1;
var _rh1=3D"";
var _rh2=3D"";
function wrreader(){
_rh1 +=3D '<table width=3D"100%" ><tr>';
_rh2+=3D'<tr>';
if(g_spAnnony){
_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
_rh2+=3D'<td> </td>';
if(g_read.length>0){
_rh1+=3D'<td align=3D"left" width=3D"12%">';
}else{
_rh1+=3D'<td align=3D"left" width=3D"100%">';
}
_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
_rh2+=3D'<td> </td>'
}
if(g_read.length=3D=3D0){
if(!g_spAnnony){
_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
_rh2+=3D'<td> </td>';
}
}else{
for(i=3D0,len=3Dg_read.length;i<len;i++){
_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
}
}
_rh1+=3D'<td width=3D"100%"></td></tr>';
_rh2+=3D'<td></td></tr></table>';
document.write(_rh1+_rh2);
}
wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_9be0dc09cf6f8286d0581b09_";
</SCRIPT>
<DIV id=3Din_comment><A name=3Dcomment></A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -