📄 usaco 1_3_4 prime cryptarithm 题解_leokan的blog.mht
字号:
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</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></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 1.3.4 Prime Cryptarithm =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C201=C8=D5 =D0=C7=C6=DA=B6=FE =
15:44</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.3.4 Prime Cryptarithm</H2>
<DIV class=3Dt_msgfont>
<P>Prime Cryptarithm<BR><BR>The following cryptarithm is a =
multiplication=20
problem that can be solved by substituting digits from a specified =
set of=20
N digits into the positions marked with *. If the set of prime =
digits=20
{2,3,5,7} is selected, the cryptarithm is called a PRIME =
CRYPTARITHM.=20
<BR><BR> * * *<BR>x * *<BR>-------<BR> * * =
*<BR>*=20
* *<BR>-------<BR>* * * *<BR><BR>Digits can appear only in places =
marked=20
by `*'. Of course, leading zeroes are not allowed. <BR>Write a =
program=20
that will find all solutions to the cryptarithm above for any =
subset of=20
digits from the set {1,2,3,4,5,6,7,8,9}. <BR><BR>PROGRAM NAME:=20
crypt1<BR>INPUT FORMAT<BR>Line 1: N, the number of =
digits that=20
will be used <BR>Line 2: N space separated digits with =
which=20
to solve the cryptarithm <BR><BR>SAMPLE INPUT (file =
crypt1.in)=20
<BR>5<BR>2 3 4 6 8<BR><BR>OUTPUT FORMAT<BR>A single line with the =
total=20
number of unique solutions. Here is the solution for the sample =
input:=20
<BR><BR> 2 2 2<BR>x 2 2<BR> =20
------<BR> 4 4 4<BR>4 4 4<BR> =
---------<BR>4 8 8=20
4<BR><BR>SAMPLE OUTPUT (file crypt1.out)<BR>1<BR><BR><BR><BR>Prime =
Cryptarithm<BR><BR>=C5=A3=CA=BD<BR><BR>=D2=EB by=20
=
!Starliu<BR>=A1=A1<BR><BR>=CF=C2=C3=E6=CA=C7=D2=BB=B8=F6=B3=CB=B7=A8=CA=FA=
=CA=BD=A3=AC=C8=E7=B9=FB=D3=C3=CE=D2=C3=C7=B8=F8=B6=A8=B5=C4=C4=C7=BC=B8=B8=
=F6<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CA%FD%D7%D6">=CA=FD=D7=D6</SPAN>=C0=B4=C8=A1=B4=FA=
*=A3=AC=BF=C9=D2=D4=CA=B9=CA=BD=D7=D3=B3=C9=C1=A2=B5=C4=BB=B0=A3=AC=CE=D2=
=C3=C7=BE=CD=BD=D0=D5=E2=B8=F6=CA=BD=D7=D3=C5=A3=CA=BD=A1=A3<BR><BR> =
; =20
* * *<BR>x * *<BR>-------<BR> * * *<BR>* * =
*<BR>-------<BR>* *=20
* =
*<BR>=CA=FD=D7=D6=D6=BB=C4=DC=C8=A1=B4=FA*=A3=AC=B5=B1=C8=BB=B5=DA=D2=BB=CE=
=BB=B2=BB=C4=DC=CE=AA0=A1=A3<BR><BR>=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=D5=D2=B3=
=F6=CB=F9=D3=D0=B5=C4=C5=A3=CA=BD=A1=A3<BR><BR>PROGRAM NAME:=20
crypt1<BR>INPUT FORMAT<BR>Line 1: =
<BR>=CA=FD=D7=D6=B5=C4=B8=F6=CA=FD=A1=A3<BR><BR>Line 2:=20
=
<BR>N=B8=F6=D3=C3=BF=D5=B8=F1=B7=D6=BF=AA=B5=C4=CA=FD=D7=D6=A3=A8=C3=BF=B8=
=F6=CA=FD=D7=D6=B6=BC=A1=CA{1,2,3,4,5,6,7,8,9}=A3=A9 =
=A1=A3<BR><BR><BR>SAMPLE INPUT (file=20
crypt1.in) <BR>5<BR>2 3 4 6 8<BR>OUTPUT=20
=
FORMAT<BR>=B9=B2=D2=BB=D0=D0=A3=AC=D2=BB=B8=F6=CA=FD=D7=D6=A1=A3=B1=ED=CA=
=BE=C5=A3=CA=BD=B5=C4=D7=DC=CA=FD=A1=A3=CF=C2=C3=E6=CA=C7=D1=F9=C0=FD=B5=C4=
=C4=C7=B8=F6=C5=A3=CA=BD=A1=A3<BR><BR> 2 2 2<BR>x 2=20
2<BR> ------<BR> 4 4 4<BR>4 4=20
4<BR> ---------<BR>4 8 8 4<BR>SAMPLE OUTPUT (file=20
crypt1.out)<BR>1</P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
=
<P><STRONG>=BF=B4=C0=B4=D5=E6=CA=C7=D3=C9=D3=DA=BD=F1=C4=EA=B5=DA=D2=BB=B4=
=CE=CC=E1=BD=BB1=B4=CEac=B8=F8=CE=D2=B4=F8=C0=B4highRP=A3=AC=D5=E2=B4=CE=CC=
=E1=BD=BB=A3=BA<BR>2=B4=CE=B1=E0=D2=EB=CD=A8=B9=FD=A3=AC1=B4=CE=D7=D4=BC=BA=
=B5=F7=CA=D4=CD=A8=B9=FD=A3=AC1=B4=CEac=A1=A3</STRONG></P>
=
<P><STRONG>=BD=AB=CA=FD=D7=D6=B4=E6=D4=DA=BC=AF=BA=CF=C0=EF=BA=CD=CA=FD=D7=
=E9=C0=EF=A3=AC=C3=B6=BE=D9=CA=FA=CA=BD=C7=B05=B8=F6*=B5=C4=D6=B5=A3=AC=BC=
=C6=CB=E3=A3=AC=C8=BB=BA=F3=BC=EC=B2=E9=CA=C7=B7=F1=C3=BF=D2=BB=B8=F6*=B6=
=BC=D4=DA=BC=AF=BA=CF=D6=D0=A3=AC=CA=C7=D4=F2=C5=A3=CA=BD=B8=F6=CA=FD=BC=D3=
1.</STRONG></P>
<P><STRONG>{<BR>TASK:crypt1<BR>LANG:PASCAL<BR>}<BR>program=20
crypt;<BR>type<BR> settype=3Dset of=20
1..9;<BR>var<BR> =
rset:settype;<BR> =20
a:array[1..9] of integer;<BR> =
date:array[1..15]of=20
integer;<BR> n,num:integer;<BR>procedure=20
init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'crypt1.in');reset(input);<BR> =20
readln(n);<BR> for i:=3D1 to n=20
do<BR> =20
begin<BR> =20
read(a[i]);<BR> =20
rset:=3Drset+[a[i]];<BR> =
end;<BR> close(input);<BR>end;<BR>function=20
check:boolean;<BR>var<BR> =20
i:integer;<BR>begin<BR> for i:=3D1 to 15 do if =
not(date[i]=20
in rset) then exit(false);<BR> =20
exit(true);<BR>end;</STRONG></P>
<P><STRONG>procedure work;<BR>var<BR> =20
i1,i2,i3,i4,i5:integer;<BR>begin<BR> =20
num:=3D0;<BR> for i1:=3D1 to n =
do<BR> for=20
i2:=3D1 to n do<BR> for i3:=3D1 to n=20
do<BR> for i4:=3D1 to n do<BR> =
for i5:=3D1=20
to n do<BR> =20
begin<BR> =20
=
fillchar(date,sizeof(date),0);<BR> &nb=
sp;=20
date[1]:=3Da[i1];<BR> =20
date[2]:=3Da[i2];<BR> =20
date[3]:=3Da[i3];<BR> =20
date[4]:=3Da[i4];<BR> =20
date[5]:=3Da[i5];<BR> =20
=
date[8]:=3Da[i5]*a[i3];<BR> =20
date[7]:=3Ddate[8] div =
10;<BR> =20
date[8]:=3Ddate[8] mod =
10;<BR> =20
=
inc(date[7],a[i5]*a[i2]);<BR> =20
date[6]:=3Ddate[7] div =
10;<BR> =20
date[7]:=3Ddate[7] mod =
10;<BR> =20
=
inc(date[6],a[i5]*a[i1]);<BR> =20
=
date[11]:=3Da[i4]*a[i3];<BR> =20
date[10]:=3Ddate[11] div =
10;<BR> =20
date[11]:=3Ddate[11] mod =
10;<BR> =20
=
inc(date[10],a[i4]*a[i2]);<BR> =
date[9]:=3Ddate[10] div =
10;<BR> =20
date[10]:=3Ddate[10] mod =
10;<BR> =20
=
inc(date[9],a[i4]*a[i1]);<BR> =20
date[15]:=3Ddate[8];<BR> =
=
date[14]:=3Ddate[7]+date[11];<BR> &nbs=
p;=20
date[13]:=3Ddate[14] div =
10;<BR> =20
date[14]:=3Ddate[14] mod =
10;<BR> =20
=
inc(date[13],date[6]+date[10]);<BR> &n=
bsp;=20
date[12]:=3Ddate[13] div =
10;<BR> =20
date[13]:=3Ddate[13] mod =
10;<BR> =20
=
inc(date[12],date[9]);<BR> if=20
check then inc(num);<BR> =
end;<BR> =20
assign(output,'crypt1.out');rewrite(output);<BR> =
writeln(num);<BR> close(output);</STRONG></P>
<P><STRONG>end;<BR>begin<BR>init;<BR>work;<BR>end.</STRONG></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4</FONT></P>
<P><FONT size=3D1>=A1=A4<BR></FONT></P>
=
<P><STRONG>=BF=B4=BF=B4USACO=B5=C4=B7=D6=CE=F6=A3=AC=D2=B2=CA=C7=C3=B6=BE=
=D9=A3=AC=B5=AB=CA=C7=C3=B6=BE=D9=B5=C4=B7=BD=B7=A8=BA=C3=D2=BB=D0=A9=A3=AC=
=B3=CC=D0=F2=B5=C4=B8=B4=D4=D3=B6=C8=B2=BB=D3=C3=D0=B4=D5=E2=C3=B4=B6=E0=A1=
=A3</STRONG></P>
<P><STRONG>The constraints of this problem are small enough that =
we can=20
just try all possible products of 3 digit * 2 digit numbers, and =
look to=20
see if all the correct digits are used. </STRONG></P>
<P><STRONG>The function "isgood" checks that a number is composed =
only of=20
acceptable digits, and "isgoodprod" checks that all the lines of =
the=20
multiplication are composed of acceptable digits. </STRONG></P>
<P><STRONG>#include <stdio.h><BR>#include=20
<stdlib.h><BR>#include <string.h><BR>#include=20
<assert.h></STRONG></P>
<P><STRONG>int isgooddigit[10]; /* isgooddigit[d] is set if d is =
an=20
acceptable digit<BR>*/</STRONG></P>
<P><STRONG>/* check that every decimal digit in "n" is a good=20
digit,<BR> and that it has the right number "d" of =
digits.=20
*/<BR>int<BR>isgood(int n, int d)<BR>{<BR> if(n =
=3D=3D=20
0)<BR> return 0;</STRONG></P>
<P><STRONG> while(n)=20
{<BR>if(!isgooddigit[n%10])<BR> return =
0;<BR>n /=3D=20
10;<BR> =20
d--;<BR> }</STRONG></P>
<P><STRONG> if( d =3D=3D 0=20
)<BR> return =
1;<BR> =20
else<BR> return =
0;<BR>}</STRONG></P>
<P><STRONG>/* check that every product line in n * m is an okay =
number=20
*/<BR>int<BR>isgoodprod(int n, int m)<BR>{<BR> =20
if(!isgood(n,3) || !isgood(m,2) || !isgood(n*m,4))<BR>return=20
0;</STRONG></P>
<P><STRONG> while(m)=20
{<BR>if(!isgood(n*(m%10),3))<BR> return =
0;<BR>m /=3D=20
10;<BR> }<BR> return=20
1;<BR>}</STRONG></P>
<P><STRONG>void<BR>main(void)<BR>{<BR> int i, j, =
n,=20
nfound;<BR> FILE *fin, *fout;</STRONG></P>
<P><STRONG> fin =3D fopen("crypt1.in",=20
"r");<BR> fout =3D fopen("crypt1.out",=20
"w");<BR> assert(fin !=3D NULL && fout =
!=3D=20
NULL);</STRONG></P>
<P><STRONG> for(i=3D0; i<10; i++)=20
{<BR> isgooddigit[i] =3D =
0;<BR> }<BR> fscanf(fin, "%d", =
&n);<BR> for(i=3D0; i<n; i++) =
{<BR>fscanf(fin,=20
"%d", &j);<BR>isgooddigit[j] =3D 1;<BR> =
}</STRONG></P>
<P><STRONG> nfound =3D 0;<BR> for(i=3D100; =
i<1000;=20
i++)<BR>for(j=3D10; j<100; j++)<BR> =20
if(isgoodprod(i, j))<BR> nfound++;</STRONG></P>
<P><STRONG> fprintf(fout, "%d\n", =
nfound);<BR> =20
exit(0);<BR>}</STRONG></P>
<P></P>
<P></P>
<P></P>
<P></P></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/74a6df1ba6fa3bd1ad6e75ae.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D =
[true,'=B7=A2=B8=F6=CA=D3=C6=C1=A3=A8=D1=DB=BE=A6=B4=ED=BE=F5=B5=C4=BD=E2=
=C3=DC=A3=A9', =
'=B7=A2=B8=F6=CA=D3=C6=C1=A3=A8=D1=DB=BE=A6=B4=ED=BE=F5=B5=C4=BD=E2=C3=DC=
=A3=A9','/leokan/blog/item/058b8a44cb4e0548500ffe16.html'];
var post =3D [true,'USACO 1.3.3 Calf Flac =CC=E2=BD=E2','USACO 1.3.3 =
Calf Flac =CC=E2=BD=E2', =
'/leokan/blog/item/ae3ec417efcb470dc83d6dd5.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%2E3%2E4=
%20Prime%20Cryptarithm%20%CC%E2%BD%E2&item=3D74a6df1ba6fa3bd1ad6e75ae">=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%2E3%2E4%20Prime%20Cryptarithm%20%C=
C%E2%BD%E2&item=3D74a6df1ba6fa3bd1ad6e75ae&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
["satily","a595536174696c795600","Satily"],
=09
["linzexu","97af6c696e7a6578755101","linzexu"],
{}
];
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){
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -