📄 usaco 1_2_5 dual palindromes 题解_leokan的blog.mht
字号:
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.2.5 Dual Palindromes</H2>
<DIV class=3Dt_msgfont>
<P>Dual Palindromes<BR>Mario Cruz (Colombia) & Hugo Rickeboer=20
(Argentina) <BR>A number that reads the same from right to left as =
when=20
read from left to right is called a palindrome. The number 12321 =
is a=20
palindrome; the number 77778 is not. Of course, palindromes have =
neither=20
leading nor trailing zeroes, so 0220 is not a palindrome. =
<BR><BR>The=20
number 21 (base 10) is not palindrome in base 10, but the number =
21 (base=20
10) is, in fact, a palindrome in base 2 (10101). <BR><BR>Write a =
program=20
that reads two numbers (expressed in base 10): <BR><BR>N (1 =
<=3D N <=3D=20
15) <BR>S (0 < S < 10000) <BR>and then finds and prints (in =
base 10)=20
the first N numbers strictly greater than S that are palindromic =
when=20
written in two or more number bases (2 <=3D base <=3D 10). =
<BR>Solutions=20
to this problem do not require manipulating integers larger than =
the=20
standard 32 bits. <BR><BR>PROGRAM NAME: dualpal<BR>INPUT =
FORMAT<BR>A=20
single line with space separated integers N and S. <BR><BR>SAMPLE =
INPUT=20
(file dualpal.in) <BR>3 25<BR><BR>OUTPUT FORMAT<BR>N lines, each =
with a=20
base 10 number that is palindromic when expressed in at least two =
of the=20
bases 2..10. The numbers should be <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>ted in order from smallest =
to largest.=20
<BR>SAMPLE OUTPUT (file =
dualpal.out)<BR>26<BR>27<BR>28<BR><BR><BR><BR>Dual=20
Palindromes<BR><BR>=CB=AB=D6=D8=BB=D8=CE=C4=CA=FD<BR><BR>Mario =
Cruz (Colombia) & Hugo Rickeboer=20
(Argentina)<BR><BR>=D2=EB by=20
=
=E5=D0=D2=A3<BR><BR>=C8=E7=B9=FB=D2=BB=B8=F6=CA=FD=B4=D3=D7=F3=CD=F9=D3=D2=
=B6=C1=BA=CD=B4=D3=D3=D2=CD=F9=D7=F3=B6=C1=B6=BC=CA=C7=D2=BB=D1=F9=A3=AC=C4=
=C7=C3=B4=D5=E2=B8=F6=CA=FD=BE=CD=BD=D0=D7=F6=A1=B0=BB=D8=CE=C4=CA=FD=A1=B1=
=A1=A3=C0=FD=C8=E7=A3=AC12321=BE=CD=CA=C7=D2=BB=B8=F6=BB=D8=CE=C4=CA=FD=A3=
=AC=B6=F877778=BE=CD=B2=BB=CA=C7=A1=A3=B5=B1=C8=BB=A3=AC=BB=D8=CE=C4=CA=FD=
=B5=C4=CA=D7=BA=CD=CE=B2=B6=BC=D3=A6=CA=C7=B7=C7=C1=E3=B5=C4=A3=AC=D2=F2=B4=
=CB0220=BE=CD=B2=BB=CA=C7=BB=D8=CE=C4=CA=FD=A1=A3<BR>=CA=C2=CA=B5=C9=CF=A3=
=AC=D3=D0=D2=BB=D0=A9=CA=FD=A3=A8=C8=E721=A3=A9=A3=AC=D4=DA=CA=AE=BD=F8=D6=
=C6=CA=B1=B2=BB=CA=C7=BB=D8=CE=C4=CA=FD=A3=AC=B5=AB=D4=DA=C6=E4=CB=FC=BD=F8=
=D6=C6=A3=A8=C8=E7=B6=FE=BD=F8=D6=C6=CA=B1=CE=AA10101=A3=A9=CA=B1=BE=CD=CA=
=C7=BB=D8=CE=C4=CA=FD=A1=A3=20
=
<BR>=B1=E0=D2=BB=B8=F6=B3=CC=D0=F2=A3=AC=B4=D3=CE=C4=BC=FE=B6=C1=C8=EB=C1=
=BD=B8=F6=CA=AE=BD=F8=D6=C6=CA=FD<BR><BR>N (1 <=3D N <=3D 15) =
<BR>S (0 < S <=20
10000) =
<BR>=C8=BB=BA=F3=D5=D2=B3=F6=C7=B0N=B8=F6=C2=FA=D7=E3=B4=F3=D3=DAS=C7=D2=D4=
=DA=C1=BD=D6=D6=D2=D4=C9=CF=BD=F8=D6=C6=A3=A8=B6=FE=BD=F8=D6=C6=D6=C1=CA=AE=
=BD=F8=D6=C6=A3=A9=C9=CF=CA=C7=BB=D8=CE=C4=CA=FD=B5=C4=CA=AE=BD=F8=D6=C6=CA=
=FD=A3=AC=CA=E4=B3=F6=B5=BD=CE=C4=BC=FE=C9=CF=A1=A3=20
=
<BR>=B1=BE=CE=CA=CC=E2=B5=C4=BD=E2=BE=F6=B7=BD=B0=B8=B2=BB=D0=E8=D2=AA=CA=
=B9=D3=C3=B4=F3=D3=DA4=D7=D6=BD=DA=B5=C4=D5=FB=D0=CD=B1=E4=C1=BF=A1=A3<BR=
><BR>PROGRAM NAME: dualpal<BR><BR>INPUT=20
=
FORMAT<BR><BR>=D6=BB=D3=D0=D2=BB=D0=D0=A3=AC=D3=C3=BF=D5=B8=F1=B8=F4=BF=AA=
=B5=C4=C1=BD=B8=F6=CA=FDN=BA=CDS=A1=A3<BR><BR>SAMPLE INPUT (file =
dualpal.in)=20
<BR><BR>3 25 <BR><BR>OUTPUT FORMAT<BR><BR>N=D0=D0,=20
=
=C3=BF=D0=D0=D2=BB=B8=F6=C2=FA=D7=E3=C9=CF=CA=F6=D2=AA=C7=F3=B5=C4=CA=FD=A3=
=AC=B2=A2=B0=B4=B4=D3=D0=A1=B5=BD=B4=F3=B5=C4=CB=B3=D0=F2=CA=E4=B3=F6=A1=A3=
<BR><BR>SAMPLE OUTPUT (file=20
dualpal.out)<BR><BR>26<BR>27<BR>28</P>
=
<P><STRONG>=CC=AB=C9=F1=C6=E6=C1=CB=A3=AC=BD=F1=C9=FA=B5=DA=D2=BB=B4=CE=D3=
=F6=B5=BD=A3=A1=A3=A1=D2=BB=B4=CE=B1=E0=D2=EB=CD=A8=B9=FD=A3=AC=D2=BB=B4=CE=
=D7=D4=BC=BA=B5=F7=CA=D4=CD=A8=B9=FD=A3=AC=D2=BB=B4=CEac=A3=A1<BR><BR>=BD=
=F8=D6=C6=D7=AA=BB=BB=CC=E2=A3=AC=BA=CDPalindromic=20
=
Squares=B2=EE=B2=BB=B6=E0=A3=AC=C3=BB=CA=B2=C3=B4=BC=BC=C7=C9=A3=AC=BF=BC=
=BB=F9=B4=A1=A1=A3 </STRONG></P>
<P><STRONG>{<BR>TASK:dualpal<BR>LANG:PASCAL<BR>}<BR>program=20
dualpal;<BR>var<BR> =
n,s,num:integer;<BR>procedure=20
init;{=CA=E4=C8=EBn,s}<BR>begin<BR> =20
assign(input,'dualpal.in');reset(input);<BR> =20
readln(n,s);<BR> =
close(input);<BR>end;</STRONG></P>
<P><STRONG>function=20
=
check(x,r:integer):boolean;{=BC=EC=B2=E9x=D4=DAr=BD=F8=D6=C6=CF=C2=CA=C7=B7=
=F1=BB=D8=CE=C4}<BR>var<BR> =20
a:array[1..50] of integer;<BR> =20
p,i:integer;<BR>begin<BR> =
p:=3D0;<BR> =20
while x>0 do<BR> =20
begin<BR> =20
inc(p);<BR> a[p]:=3Dx =
mod=20
r;<BR> x:=3Dx div=20
r;<BR> =20
end;<BR> check:=3Dtrue;<BR> =
for i:=3D1 to=20
p shr 1 do<BR> if=20
a[i]<>a[p-i+1]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
check:=3Dfalse;<BR> =
=20
=
exit;<BR> &nbs=
p;=20
end;<BR>end;</STRONG></P>
<P><STRONG>procedure=20
=
wrok(xx:integer);{=BC=EC=B2=E9xx=CA=C7=B7=F1=C2=FA=D7=E3=CC=E2=C4=BF=D2=AA=
=C7=F3}<BR>var<BR> =20
i,count:integer;<BR>begin<BR> =20
count:=3D0;<BR> for i:=3D2 to 10=20
do<BR> =20
begin<BR> if check(xx,i) =
then=20
inc(count);<BR> if =
count>=3D2=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p;=20
=
writeln(xx);<BR> &nb=
sp; =20
=
inc(num);<BR> =
=20
=
exit;<BR> &nbs=
p;=20
end;<BR> =20
end;<BR>end;</STRONG></P>
<P><STRONG>procedure =
main;{=D5=D2=B3=F6n=B8=F6=B4=F3=D3=DAs=A3=AC=C2=FA=D7=E3=CC=E2=C4=BF=D2=AA=
=C7=F3=B5=C4=CA=FD}<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
=
assign(output,'dualpal.out');rewrite(output);<BR> =20
num:=3D0;<BR> i:=3Ds;<BR> =
while num<n=20
do<BR> =20
begin<BR> =20
inc(i);<BR> =20
wrok(i);<BR> =20
end;<BR> =20
=
close(output);<BR>end;<BR>begin<BR>init;<BR>main;<BR>end.</STRONG></P>
=
<P><STRONG>=CF=C2=C3=E6=CA=C7USACO=B5=C4=B7=D6=CE=F6<BR></STRONG></P>
<P><STRONG>Dual palindromes are actually very common, a fact we =
can test=20
by writing a program such as this one. </STRONG></P>
<P><STRONG>Since they are very common, we can just use a brute =
force=20
search to test all numbers bigger than s until we find enough dual =
palindromes. </STRONG></P>
<P><STRONG>How do we know they are common enough? Write the brute =
force=20
program (which is very simple and thus not much effort) and check. =
</STRONG></P>
<P><STRONG>This reasoning is a little circular, but if we had been =
wrong=20
and ended up needing a more clever and more efficient algorithm, =
we would=20
have this brute force version to test against. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.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 "" */
char*
numbconv(char *s, int n, int b)
{
int len;
if(n =3D=3D 0) {
strcpy(s, "");
return s;
}
/* 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';
return s;
}
/* is number n a dual palindrome? */
int
isdualpal(int n)
{
int i, j, npal;
char s[40];
npal =3D 0;
for(i=3D2; i<=3D10; i++)
if(ispal(numbconv(s, n, i)))
npal++;
return npal >=3D 2;
}
void
main(void)
{
FILE *fin, *fout;
int n, s;
fin =3D fopen("dualpal.in", "r");
fout =3D fopen("dualpal.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d %d", &n, &s);
for(s++; n>0; s++) {
if(isdualpal(s)) {
fprintf(fout, "%d\n", s);
n--;
}
}
exit(0);
}</STRONG></PRE></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/03c30f0883fa15d562d986af.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'=D0=C2=C4=EA=B5=BD=A3=A1', =
'=D0=C2=C4=EA=B5=BD=A3=A1','/leokan/blog/item/467ad862d933fad9e7113aa6.ht=
ml'];
var post =3D [true,'USACO 1.3.1 Mixing Milk =CC=E2=BD=E2','USACO 1.3.1 =
Mixing Milk =CC=E2=BD=E2', =
'/leokan/blog/item/334b3787da7c2a2ec65cc38c.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%2E5=
%20Dual%20Palindromes%20%CC%E2%BD%E2&item=3D03c30f0883fa15d562d986af">=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%2E5%20Dual%20Palindromes%20%CC=
%E2%BD%E2&item=3D03c30f0883fa15d562d986af&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[
{}
];
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_03c30f0883fa15d562d986af_";
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -