资源描述:
《USACO CRYPT1》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、PrimeCryptarithmThefollowingcryptarithmisamultiplicationproblemthatcanbesolvedbysubstitutingdigitsfromaspecifiedsetofNdigitsintothepositionsmarkedwith*.Ifthesetofprimedigits{2,3,5,7}isselected,thecryptarithmiscalledaPRIMECRYPTARITHM.***x**-------***<--partialproduct1***<--partialproduct2-
2、------****Digitscanappearonlyinplacesmarkedby`*'.Ofcourse,leadingzeroesarenotallowed.Notethatthe'partialproducts'areastaughtinUSAschools.Thefirstpartialproductistheproductofthefinaldigitofthesecondnumberandthetopnumber.Thesecondpartialproductistheproductofthefirstdigitofthesecondnumberand
3、thetopnumber.Writeaprogramthatwillfindallsolutionstothecryptarithmaboveforanysubsetofdigitsfromtheset{1,2,3,4,5,6,7,8,9}.PROGRAMNAME:crypt1INPUTFORMATLine1:N,thenumberofdigitsthatwillbeusedLine2:NspaceseparateddigitswithwhichtosolvethecryptarithmSAMPLEINPUT(filecrypt1.in)523468OUTPUTFORMA
4、TAsinglelinewiththetotalnumberofuniquesolutions.Hereisthesinglesolutionforthesampleinput:222x22------444444---------4884SAMPLEOUTPUT(filecrypt1.out)1{ID:hyysmmu1PROG:crypt1LANG:PASCAL}vari,j,k,m,n,ans:longint;a1:longint;a:array[1..9]ofboolean;functioncheck(kk:longint):boolean;begincheck:=
5、false;whilekk>0dobeginifnota[kkmod10]thenexit;kk:=kkdiv10;end;check:=true;end;proceduresub(k1:longint);vari1,m1,m2,m3:longint;beginifk1=6thenbeginm1:=a1mod10;m2:=a1mod100;m3:=a1div100;if(m2*m3>=1000)and(m2*m3<=9999)and(m1*m3<1000)and(m1*m3>=100)andcheck(m2*m3)andcheck(m1*m3)theninc(ans);e
6、xit;end;ifk1=5thenbeginm1:=a1mod10;m2:=a1div10;if(m1*m2>=1000)or(m1*m2<100)ornotcheck(m1*m2)thenexit;end;fori1:=1to9doifa[i1]thenbegina1:=a1*10+i1;sub(k1+1);a1:=a1div10;end;end;beginassign(input,'crypt1.in');assign(output,'crypt1.out');reset(input);rewrite(output);ans:=0;fillchar(a,sizeof
7、(a),false);readln(n);fori:=1tondobeginread(m);a[m]:=true;end;a1:=0;sub(1);writeln(ans);close(input);close(output);end.