📄 usaco 1_5_3 superprime rib 题解_leokan的blog.mht
字号:
<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 1.5.3 Superprime Rib =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C226=C8=D5 =D0=C7=C6=DA=C1=F9 =
17:58</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.5.3 Superprime Rib</H2>
<DIV class=3Dt_msgfont>Superprime Rib<BR>Butchering Farmer John's =
cows=20
always yields the best prime rib. You can tell prime ribs by =
looking at=20
the digits lovingly stamped across them, one by one, by FJ and the =
USDA.=20
Farmer John ensures that a purchaser of his prime ribs gets really =
prime=20
ribs because when sliced from the right, the numbers on the ribs =
continue=20
to stay prime right down to the last rib, e.g.: =
<BR><BR> =20
7 3 3 1<BR><BR>The set of ribs =
denoted=20
by 7331 is prime; the three ribs 733 are prime; the two ribs 73 =
are prime,=20
and, of course, the last rib, 7, is prime. The number 7331 is =
called a=20
superprime of length 4. <BR><BR>Write a program that accepts a =
number N 1=20
<=3DN<=3D8 of ribs and prints all the superprimes of that =
length.=20
<BR><BR>The number 1 (by itself) is not a prime number. =
<BR><BR>PROGRAM=20
NAME: sprime<BR>INPUT FORMAT<BR>A single line with the number N.=20
<BR>SAMPLE INPUT (file sprime.in) <BR>4<BR><BR>OUTPUT =
FORMAT<BR>The=20
superprime ribs of length N, printed in ascending order one per =
line.=20
<BR>SAMPLE OUTPUT (file=20
=
sprime.out)<BR>2333<BR>2339<BR>2393<BR>2399<BR>2939<BR>3119<BR>3137<BR>37=
33<BR>3739<BR>3793<BR>3797<BR>5939<BR>7193<BR>7331<BR>7333<BR>7393<BR><BR=
><BR><BR>Superprime=20
=
Rib<BR><BR>=CC=D8=CA=E2=B5=C4=D6=CA=CA=FD=C0=DF=B9=C7<BR><BR>=D2=EB by =
tim=20
=
green<BR>=A1=A1<BR><BR><BR>=C5=A9=C3=F1=D4=BC=BA=B2=C4=B8=C5=A3=D7=DC=CA=C7=
=B2=FA=C9=FA=D7=EE=BA=C3=B5=C4=C0=DF=B9=C7=A1=A3<BR>=C4=E3=C4=DC=CD=A8=B9=
=FD=C5=A9=C3=F1=D4=BC=BA=B2=BA=CD=C3=C0=B9=FA=C5=A9=D2=B5=B2=BF=B1=EA=BC=C7=
=D4=DA=C3=BF=B8=F9=C0=DF=B9=C7=C9=CF=B5=C4=CA=FD=D7=D6=C8=CF=B3=F6=CB=FC=C3=
=C7=A1=A3<BR>=C5=A9=C3=F1=D4=BC=BA=B2=C8=B7=B6=A8=CB=FB=C2=F4=B8=F8=C2=F2=
=B7=BD=B5=C4=CA=C7=D5=E6=D5=FD=B5=C4=D6=CA=CA=FD=C0=DF=B9=C7,=CA=C7=D2=F2=
=CE=AA=B4=D3=D3=D2=B1=DF=BF=AA=CA=BC=C7=D0=CF=C2=C0=DF=B9=C7,=C3=BF=B4=CE=
=BB=B9=CA=A3=CF=C2=B5=C4=C0=DF=B9=C7=C9=CF=B5=C4=CA=FD=D7=D6=B6=BC=D7=E9=B3=
=C9=D2=BB=B8=F6=D6=CA=CA=FD,=BE=D9=C0=FD=C0=B4=CB=B5:<BR>7=20
3 3 1<BR>=C8=AB=B2=BF=C0=DF=B9=C7=C9=CF=B5=C4=CA=FD=D7=D6 =
7331=CA=C7=D6=CA=CA=FD;=C8=FD=B8=F9=C0=DF=B9=C7 =
733=CA=C7=D6=CA=CA=FD;=B6=FE=B8=F9=C0=DF=B9=C7 73 =
=CA=C7=D6=CA=CA=FD;=B5=B1=C8=BB,=D7=EE=BA=F3=D2=BB=B8=F9=C0=DF=B9=C7 7=20
=D2=B2=CA=C7=D6=CA=CA=FD=A1=A3<BR>7331 =
=B1=BB=BD=D0=D7=F6=B3=A4=B6=C8 4 =
=B5=C4=CC=D8=CA=E2=D6=CA=CA=FD=A1=A3<BR>=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=B6=
=D4=B8=F8=B6=A8=B5=C4=C0=DF=B9=C7=B5=C4=CA=FD=C4=BF N=20
=
(1<=3DN<=3D8),=C7=F3=B3=F6=CB=F9=D3=D0=B5=C4=CC=D8=CA=E2=D6=CA=CA=FD=
=A1=A3<BR>=CA=FD=D7=D61=B2=BB=B1=BB=BF=B4=D7=F7=D2=BB=B8=F6=D6=CA=CA=FD=A1=
=A3<BR><BR>PROGRAM NAME:=20
sprime<BR><BR>INPUT =
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=BA=ACN=A1=A3<BR><BR>SAMPLE=
INPUT (file=20
sprime.in) <BR>4<BR><BR>OUTPUT =
FORMAT<BR>=B0=B4=CB=B3=D0=F2=CA=E4=B3=F6=B3=A4=B6=C8=CE=AA N=20
=
=B5=C4=CC=D8=CA=E2=D6=CA=CA=FD,=C3=BF=D0=D0=D2=BB=B8=F6=A1=A3<BR><BR>SAMP=
LE OUTPUT (file=20
=
sprime.out)<BR>2333<BR>2339<BR>2393<BR>2399<BR>2939<BR>3119<BR>3137<BR>37=
33<BR>3739<BR>3793<BR>3797<BR>5939<BR>7193<BR>7331<BR>7333<BR>7393</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 1.5.3 Superprime Rib =
<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE</STRONG></P>
=
<P><STRONG>=D5=E2=B5=C0=CC=E2=CE=D2=D3=C3=C1=CBbfs=D7=F6=A3=AC=CF=C8=C9=FA=
=B3=C910000=D2=D4=C4=DA=B5=C4=D6=CA=CA=FD(=B7=BD=B1=E3=C5=D0=B6=CF)=A3=AC=
=C8=BB=BA=F3=C8=A1=C7=B04=B8=F6(2=A3=AC3=A3=AC5=A3=AC7=D5=E2=BC=B8=B8=F6)=
=B7=C5=C8=EB=B6=D3=C1=D0=A3=AC=C8=BB=BA=F3bfs(=CC=ED=BC=D3=D2=BB=B8=F6=C6=
=E6=CA=FD=D4=DA=BA=F3=C3=E6=A3=AC=C5=D0=B6=CF=CB=FC=CA=C7=B2=BB=CA=C7=D6=CA=
=CA=FD=CA=C7=D4=F2=C8=EB=B6=D3=A3=AC=CE=BB=CA=FD=CE=AAn=D4=F2=CA=E4=B3=F6=
)=A1=A3</STRONG></P>
<P></P>
<P><STRONG>{<BR>TASK:sprime<BR>LANG:PASCAL<BR>}<BR>program=20
sprime;<BR>const<BR> =
maxn=3D10000;<BR> =20
oddnum:array[1..5] of byte =
=3D(1,3,5,7,9);<BR>var<BR> =20
isprime:array[2..maxn] of boolean;<BR> =20
prime:array[0..1500] of integer;<BR> =20
queue:array[1..2000] of longint;<BR> =20
count:array[1..2000] of byte;<BR> =20
n,h,t:integer;<BR>procedure init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
fillchar(queue,sizeof(queue),0);<BR> =20
fillchar(count,sizeof(count),0);<BR> =20
assign(input,'sprime.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR> for=20
i:=3D1 to 4 do<BR> =20
=
begin<BR> &nbs=
p;=20
=
queue[i]:=3Dprime[i];<BR> =
=20
count[i]:=3D1;<BR> =20
end;<BR> h:=3D1;<BR> =20
t:=3D4;<BR>end;<BR>procedure =
initprime;<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
fillchar(isprime,sizeof(isprime),true);<BR> for =
i:=3D2 to=20
100 do<BR> if isprime[i] =
=
then<BR>  =
;=20
for j:=3D2 to (maxn div i)=20
=
do<BR> &=
nbsp; =20
isprime[j*i]:=3Dfalse;<BR> =20
fillchar(prime,sizeof(prime),0);<BR> for i:=3D2 =
to maxn=20
do<BR> if isprime[i]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
inc(prime[0]);<BR> &=
nbsp; =20
=
prime[prime[0]]:=3Di;<BR> =
=20
end;<BR>end;<BR>function=20
check(x:longint):boolean;<BR>var<BR> =20
i:integer;<BR>begin<BR> for i:=3D1 to prime[0]=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if prime[i]>trunc(sqrt(x))+1 then=20
=
break;<BR> &nb=
sp;=20
if x mod prime[i]=3D0=20
=
then<BR>  =
; =20
exit(false);<BR> =20
end;<BR> exit(true);<BR>end;<BR>procedure=20
bfs;<BR>var<BR> i:integer;<BR> =
temp:longint;<BR>begin<BR> =20
assign(output,'sprime.out');rewrite(output);<BR> =
while=20
t>=3Dh do<BR> =20
=
begin<BR> &nbs=
p;=20
for i:=3D1 to 5=20
=
do<BR> &=
nbsp; =20
=
begin<BR> &nbs=
p; =20
=
temp:=3Dqueue[h];<BR> &nbs=
p; =20
=
temp:=3Dtemp*10;<BR>  =
; =20
=
inc(temp,oddnum[i]);<BR> &=
nbsp; =20
if check(temp)=20
=
then<BR>  =
; =
=20
if count[h]+1=3Dn=20
=
then<BR>  =
; =
=20
=
writeln(temp)<BR> &n=
bsp; &nb=
sp; =20
else=20
=
begin<BR> &nbs=
p;  =
; =20
=
inc(t);<BR> &n=
bsp; &nb=
sp; =20
=
queue[t]:=3Dtemp;<BR> &nbs=
p;  =
; =20
=
count[t]:=3Dcount[h]+1;<BR> &nbs=
p;  =
; =20
=
end;<BR>  =
; =20
=
end;<BR>  =
;=20
inc(h);<BR> =20
end;<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
initprime;<BR> init;<BR> =20
bfs;<BR>end.</STRONG></P><STRONG>
<HR>
</STRONG>
=
<P><STRONG>usaco=B5=C4=B7=D6=CE=F6=A3=AC=B5=B9=D7=C5=B5=DD=B9=E9=A1=A3</S=
TRONG></P>
<P><STRONG>We use a recursive search to build superprimes of =
length n from=20
superprimes of length n-1 by adding a 1, 3, 7, or 9. (Numbers =
ending in=20
any other digit are divisible by 2 or 5.) Since there are so few =
numbers=20
being tested, a simple primality test suffices. =
</STRONG></P><PRE><STRONG>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
FILE *fout;
int
isprime(int n)
{
int i;
if(n =3D=3D 2)
return 1;
if(n%2 =3D=3D 0)
return 0;
for(i=3D3; i*i <=3D n; i+=3D2)
if(n%i =3D=3D 0)
return 0;
return 1;
}
/* print all sprimes possible by adding ndigit digits to the number n */
void
sprime(int n, int ndigit)
{
if(ndigit =3D=3D 0) {
fprintf(fout, "%d\n", n);
return;
}
n *=3D 10;
if(isprime(n+1))
sprime(n+1, ndigit-1);
if(isprime(n+3))
sprime(n+3, ndigit-1);
if(isprime(n+7))
sprime(n+7, ndigit-1);
if(isprime(n+9))
sprime(n+9, ndigit-1);
}
void
main(void)
{
int n;
FILE *fin;
fin =3D fopen("sprime.in", "r");
assert(fin !=3D NULL);
fout =3D fopen("sprime.out", "w");
assert(fout !=3D NULL);
fscanf(fin, "%d", &n);
sprime(2, n-1);
sprime(3, n-1);
sprime(5, n-1);
sprime(7, n-1);
exit (0);
}</STRONG></PRE></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
href=3D"http://hi.baidu.com/leokan/modify/blog/30aabe1b1412a21d8718bf64">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/30aabe1b1412a21d8718bf64.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3D30aabe1b1412a21d8718bf64=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
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/30aabe1b1412a21d8718bf64.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.5.2 Prime Palindromes =CC=E2=BD=E2', 'USACO =
1.5.2 Prime Palindromes =
...','/leokan/blog/item/58852b9794fd676955fb96b4.html'];
var post =3D [true,'Windows Vista no longer starts after you install an =
earlier version of the Windows operating...','Windows Vista no longer =
starts...', '/leokan/blog/item/baa48a010f68ddd2267fb5c4.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>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -