📄 usaco 1_2_3 name that number 题解_leokan的blog.mht
字号:
<DIV id=3Dtabline></DIV>
<DIV id=3Dtab><A href=3D"http://hi.baidu.com/leokan">=D6=F7=D2=B3</A><A =
class=3Don=20
href=3D"http://hi.baidu.com/leokan/blog">=B2=A9=BF=CD</A><A=20
href=3D"http://hi.baidu.com/leokan/album">=CF=E0=B2=E1</A><SPAN>|</SPAN><=
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
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.2.3 Name That Number =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2007=C4=EA12=D4=C231=C8=D5 =D0=C7=C6=DA=D2=BB =
23:11</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 1.2.3 Name That Number</H2>
<DIV class=3Dt_msgfont>Name That Number<BR><BR>Among the large =
Wisconsin=20
cattle ranchers, it is customary to brand cows with serial numbers =
to=20
please the Accounting Department. The cow hands don't appreciate =
the=20
advantage of this filing system, though, and wish to call the =
members of=20
their herd by a pleasing name rather than saying, "C'mon, #4734, =
get=20
along." <BR><BR>Help the poor cowhands out by writing a program =
that will=20
translate the brand serial number of a cow into possible names =
uniquely=20
associated with that serial number. Since the cow hands all have =
cellular=20
saddle phones these days, use the standard Touch-Tone(R) telephone =
keypad=20
mapping to get from numbers to letters (except for "Q" and "Z"):=20
<BR><BR> 2: A,B,C 5: =
J,K,L 8:=20
T,U,V<BR> 3: D,E,F 6: =
M,N,O 9:=20
W,X,Y<BR> 4: G,H,I 7:=20
P,R,S<BR><BR>Acceptable names for cattle are provided to you in a =
file=20
named "dict.txt", which contains a <SPAN class=3Dt_tag=20
href=3D"tag.php?name=3Dlis">lis</SPAN>t of fewer than 5,000 =
acceptable cattle=20
names (all letters capitalized). Take a cow's brand number and =
report=20
which of all the possible words to which that number maps are in =
the given=20
dictionary which is supplied as dict.txt in the grading =
environment (and=20
is sorted into ascending order). <BR><BR>For instance, the brand =
number=20
4734 produces all the following names: <BR><BR>GPDG GPDH GPDI GPEG =
GPEH=20
GPEI GPFG GPFH GPFI GRDG GRDH GRDI<BR>GREG GREH GREI GRFG GRFH =
GRFI GSDG=20
GSDH GSDI GSEG GSEH GSEI<BR>GSFG GSFH GSFI HPDG HPDH HPDI HPEG =
HPEH HPEI=20
HPFG HPFH HPFI<BR>HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI =
HSDG HSDH=20
HSDI<BR>HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH=20
IPEI<BR>IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH=20
IRFI<BR>ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI<BR><BR>As it =
happens,=20
the only one of these 81 names that is in the list of valid names =
is=20
"GREG". <BR><BR>Write a program that is given the brand number of =
a cow=20
and prints all the valid names that can be generated from that =
brand=20
number or ``NONE'' if there are no valid names. Serial numbers can =
be as=20
many as a dozen digits long. <BR><BR>PROGRAM NAME: =
namenum<BR>INPUT=20
FORMAT<BR>A single line with a number from 1 through 12 digits in =
length.=20
<BR>SAMPLE INPUT (file namenum.in) <BR>4734<BR><BR>OUTPUT =
FORMAT<BR>A list=20
of valid names that can be generated from the input, one per line, =
in=20
ascending alphabetical order. <BR>SAMPLE OUTPUT (file=20
namenum.out)<BR>GREG<BR><BR><BR><BR>Name That =
Number<BR><BR>=C3=FC=C3=FB=C4=C7=B8=F6<SPAN=20
class=3Dt_tag =
href=3D"tag.php?name=3D%CA%FD%D7%D6">=CA=FD=D7=D6</SPAN><BR><BR>=D2=EB =
by=20
=
timgreen<BR><BR>=D4=DA=CD=FE=CB=B9=BF=B5=D0=C1=D6=DD=C5=A3=B4=F3=C5=A9=B3=
=A1=BE=AD=D3=AA=D5=DF=D6=AE=D6=D0=A3=AC=B6=BC=CF=B0=B9=DF=D3=DA=C7=EB=BB=E1=
=BC=C6=B2=BF=C3=C5=D3=C3=C1=AC=D0=F8=CA=FD=D7=D6=B8=F8=C4=B8=C5=A3=B4=F2=C9=
=CF=C0=D3=D3=A1=A1=A3<BR>=B5=AB=CA=C7,=C4=B8=C5=A3=D3=C3=CA=D6=BB=FA=CA=B1=
=B2=A2=C3=BB=B8=D0=B5=BD=D5=E2=B8=F6=CF=B5=CD=B3=B5=C4=B1=E3=C0=FB,=CB=FC=
=C3=C7=B8=FC=CF=B2=BB=B6=D3=C3=CB=FC=C3=C7=CF=B2=BB=B6=B5=C4=C3=FB=D7=D6=C0=
=B4=BA=F4=BD=D0=CB=FC=C3=C7=B5=C4=CD=AC=B0=E9=A3=AC=B6=F8=B2=BB=CA=C7=D3=C3=
=CF=F1=D5=E2=B8=F6=B5=C4=D3=EF=BE=E4"C'mon,=20
#4734, get=20
=
along."=A1=A3<BR>=C7=EB=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=C0=B4=B0=EF=D6=FA=BF=
=C9=C1=AF=B5=C4=C4=C1=C5=A3=B9=A4=BD=AB=D2=BB=D6=BB=C4=B8=C5=A3=B5=C4=C0=D3=
=D3=A1=B1=E0=BA=C5=B7=AD=D2=EB=B3=C9=D2=BB=B8=F6=BF=C9=C4=DC=B5=C4=C3=FB=D7=
=D6=A1=A3<BR>=D2=F2=CE=AA=C4=B8=C5=A3=C3=C7=CF=D6=D4=DA=B6=BC=D3=D0=CA=D6=
=BB=FA=C1=CB=A3=AC=CA=B9=D3=C3=C4=C7=B1=EA=D7=BC=B5=C4=B0=B4=BC=FC=B5=C4=C5=
=C5=B2=BC=C0=B4=B0=D1=CA=D5=B5=BD=B4=D3=CA=FD=C4=BF=B7=AD=D2=EB=B5=BD=CE=C4=
=D7=D6,=B3=FD=C1=CB"Q"=20
=BA=CD =
"Z"(=C3=BB=B3=F6=CF=D6=B9=FD=A3=A9<BR><BR> =
2: A,B,C=20
5: J,K,L 8: T,U,V<BR> =
3: D,E,F=20
6: M,N,O 9: W,X,Y<BR> =
4: G,H,I=20
7: =
P,R,S<BR><BR>=BF=C9=BD=D3=CA=DC=B5=C4=C3=FB=D7=D6=B6=BC=B1=BB=B7=C5=D4=DA=
=D5=E2=D1=F9=D2=BB=B8=F6=BD=D0=D7=F7"dict.txt"=20
=
=B5=C4=CE=C4=BC=FE=D6=D0=A3=AC=CB=FC=B0=FC=BA=AC=D2=BB=C1=AC=B4=AE=B5=C4=C9=
=D9=D3=DA 5,000=B8=F6=BF=C9=BD=D3=CA=DC=B5=C4=C5=A3=C3=FB=D7=D6=A1=A3=20
=
(=CB=F9=D3=D0=B5=C4=C3=FB=D7=D6=B6=BC=CA=C7=B4=F3=D0=B4=B5=C4)<BR>=CA=D5=B5=
=BD=C4=B8=C5=A3=B5=C4=B1=E0=BA=C5=B7=B5=BB=D8=C4=C7=D0=A9=C4=DC=B4=D3=B1=E0=
=BA=C5=B7=AD=D2=EB=B3=F6=C0=B4=B2=A2=C7=D2=D4=DA=D7=D6=B5=E4=D6=D0=B5=C4=C3=
=FB=D7=D6=A1=A3<BR>=BE=D9=C0=FD=C0=B4=CB=B5,=B1=E0=BA=C5 4734=20
=
=C4=DC=B2=FA=C9=FA=B5=C4=CF=C2=C1=D0=B8=F7=CF=EE=C3=FB=D7=D6:<BR>GPDG =
GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH=20
GRDI<BR>GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH=20
GSEI<BR>GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH=20
HPFI<BR>HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH=20
HSDI<BR>HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH=20
IPEI<BR>IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH=20
IRFI<BR>ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH=20
=
ISFI<BR><BR>=C5=F6=C7=C9=A3=AC81=B8=F6=D6=D0=D6=BB=D3=D0=D2=BB=B8=F6"GREG=
"=CA=C7=D3=D0=D0=A7=B5=C4(=D4=DA=D7=D6=B5=E4=D6=D0)=A1=A3<BR><BR>Challeng=
e=20
=
One<BR>=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=C0=B4=B6=D4=B8=F8=B3=F6=B5=C4=B1=E0=
=BA=C5=B4=F2=D3=A1=B3=F6=CB=F9=D3=D0=B5=C4=D3=D0=D0=A7=C3=FB=D7=D6=A3=AC=C8=
=E7=B9=FB=C3=BB=D3=D0=D4=F2=CA=E4=B3=F6"NONE'' =
=A1=A3<BR>=B1=E0=BA=C5=BF=C9=C4=DC=D3=D012<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%CE%BB%CA%FD">=CE=BB=CA=FD</SPAN>=D7=D6=A1=A3<BR>P=
ROGRAM NAME:=20
namenum<BR><BR>INPUT =
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=B0=FC=BA=AC=D2=BB=B8=F6=B1=E0=BA=
=C5(=B3=A4=B6=C8=BF=C9=C4=DC=B4=D31=B5=BD12)=A1=A3<BR><BR>SAMPLE INPUT=20
(file namenum.in) <BR>4734<BR><BR>OUTPUT=20
=
FORMAT<BR>=D2=D4=D7=D6=B5=E4=CB=B3=D0=F2=CA=E4=B3=F6=D2=BB=B8=F6=D3=D0=D0=
=A7=C3=FB=D7=D6=B5=C4=B2=BB=B8=BA=C1=D0=B1=ED=A3=AC=D2=BB=D0=D0=D2=BB=B8=F6=
=C3=FB=D7=D6=A1=A3<BR><BR>SAMPLE OUTPUT (file=20
namenum.out)<BR>GREG</DIV>
=
<P><STRONG>=B6=D4=D7=D6=B5=E4=D7=F6=D2=BB=B4=CE=C9=A8=C3=E8=A3=AC=BD=AB=C3=
=BF=B8=F6=B5=A5=B4=CA=CB=F9=B6=D4=D3=A6=B5=C4=CA=FD=D6=B5=BC=C6=CB=E3=B3=F6=
=C0=B4=A3=AC=C8=E7=B9=FB=D3=EBn=CF=E0=B5=C8=D4=F2=CA=E4=B3=F6=A1=A3=B4=CB=
=CC=E2=CE=D22=B4=CEAC=A3=AC=B5=DA=D2=BB=B4=CE=B3=F6=CF=D6=C1=CB=C6=E6=B9=D6=
=B5=C4=B7=B4=D3=A6exited=20
with signal #9<BR>resource limits=20
=
exceeded=A3=AC=BA=F3=C0=B4=BD=AB=C1=BD=B4=CEinput=B7=D6=B1=F0=B8=B3=C1=CB=
=B8=F6text=D6=B5=BE=CD=B9=FD=C1=CB=A3=A8=D4=AD=CF=C8=D6=BB=B8=B3=D6=B5=C1=
=CB=D2=BB=B8=F6=A3=A9=A1=A3</STRONG></P>
=
<P><STRONG>=D4=B4=C2=EB=A3=BA=A3=A8=D5=E2=D0=A9=CC=E2=C8=F5=D6=C7=CC=E2=A3=
=AC=B3=F5=D1=A7=D5=DF=D7=EE=BA=C3=D7=D4=BC=BA=D7=F6=A3=AC=B2=BB=D2=AA=BF=B4=
=A3=A9</STRONG></P>
<P>|</P>
<P>|</P>
<P>|</P>
<P>|</P>
<P>|<BR><STRONG>TASK:namenum<BR>LANG:PASCAL<BR>}<BR>program=20
namenum;<BR>var<BR>dict:array[1..5000] of =
string;<BR>rule:array['A'..'Z']=20
of integer;<BR>p:integer;<BR>n:qword;<BR>fp,ff:text;<BR>function=20
pf(x:integer):qword;<BR>var<BR> =20
i:integer;<BR>begin<BR> =
pf:=3D1;<BR> for=20
i:=3D1 to x do<BR> =
pf:=3Dpf=20
*10;<BR>end;</STRONG></P>
<P><STRONG>procedure =
initdict;{=B6=C1=C8=EB=D7=D6=B5=E4}<BR>var<BR> =20
i,j:integer;<BR>begin<BR> =20
assign(fp,'dict.txt');reset(fp);<BR> =20
p:=3D0;<BR> while not eof(fp)=20
do<BR> =20
begin<BR> =20
inc(p);<BR> =20
readln(fp,dict[p]);<BR> =20
end;<BR> close(fp);<BR>end;<BR>procedure=20
=
init;{=B6=C1=C8=EB=CA=FD=D7=D6=BA=CD=B3=F5=CA=BC=BB=AF=D7=AA=BB=BB=B9=E6=D4=
=F2}<BR>begin<BR> =20
assign(ff,'namenum.in');reset(ff);<BR> =20
readln(ff,n);<BR> =
close(ff);<BR> =20
rule['A']:=3D2;<BR> =
rule['B']:=3D2;<BR> =20
rule['C']:=3D2;<BR> =
rule['D']:=3D3;<BR> =20
rule['E']:=3D3;<BR> =
rule['F']:=3D3;<BR> =20
rule['G']:=3D4;<BR> =
rule['H']:=3D4;<BR> =20
rule['I']:=3D4;<BR> =
rule['J']:=3D5;<BR> =20
rule['K']:=3D5;<BR> =
rule['L']:=3D5;<BR> =20
rule['M']:=3D6;<BR> =
rule['N']:=3D6;<BR> =20
rule['O']:=3D6;<BR> =
rule['P']:=3D7;<BR> =20
rule['R']:=3D7;<BR> =
rule['S']:=3D7;<BR> =20
rule['T']:=3D8;<BR> =
rule['U']:=3D8;<BR> =20
rule['V']:=3D8;<BR> =
rule['W']:=3D9;<BR> =20
rule['X']:=3D9;<BR> rule['Y']:=3D9;</STRONG></P>
<P><STRONG>end;<BR>procedure work;<BR>var<BR> =20
i,j,len:integer;<BR> =
t:qword;<BR> =20
being:boolean;<BR>begin<BR> =20
=
assign(output,'namenum.out');rewrite(output);<BR> =20
being:=3Dfalse;<BR> for i:=3D1 to p=20
=
do{=C9=A8=C3=E8=D7=D6=B5=E4}<BR>  =
;=20
begin<BR> =20
t:=3D0;<BR> =20
=
len:=3Dlength(dict[i]);<BR> =
for=20
j:=3Dlen downto 1=20
=
do<BR> =
=
inc(t,rule[dict[i,j]]*pf(len-j));{=D7=AA=BB=BB=CA=FD=D6=B5}<BR> &nbs=
p; =20
if t=3Dn then begin=20
=
being:=3Dtrue;writeln(dict[i]);end;{=C8=F4=C6=A5=C5=E4}<BR> &n=
bsp; =20
end;<BR> if not being then=20
writeln('NONE');<BR> =20
=
close(output);<BR>end;<BR>begin<BR>initdict;<BR>init;<BR>work;<BR>end.</S=
TRONG></P>
<P></P>
=
<P><STRONG>=CF=C2=C3=E6=CA=C7USACO=B5=C4=B7=D6=CE=F6=A3=A8c=D3=EF=D1=D4=A3=
=A9=A3=AC=B5=DA=D2=BB=D6=D6=CB=E3=B7=A8=D0=A7=C2=CA=B8=DF=A3=AC=D3=C3=C1=CB=
2=B7=D6=A3=AC=B5=DA=B6=FE=D6=D6=BE=CD=CA=C7=BA=CD=CE=D2=B2=EE=B2=BB=B6=E0=
=B5=C4=C4=C7=D6=D6=C1=CB=A1=A3</STRONG></P><STRONG>
<P>There are two ways to do this problem. One is, given the =
number, to=20
generate all possible strings that encode to that number and look =
them up=20
in the dictionary. Since there are 3 letters for each number and =
12 digits=20
in the string, that's 3<SUP>12</SUP> =3D 531441 lookups into a =
dictionary of=20
size 5000, which although manageable would be a little on the long =
side=20
(binary search can help this).</P>
<P>Or, we can examine each word in the dictionary to see if it =
maps to the=20
digits of the number in question. This has the the advantage of a =
shorter=20
program that probably will work right first time.</P>
<HR>
<P>Here is Argentina competitor's Michel Mizrah's solution using =
the first=20
method with a binary search. While it is blazingly fast, it does =
have the=20
disadvantage of some fairly tricky coding in the binary search =
routine. A=20
single off-by-one error would doom a program in a =
contest.</P><PRE>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char num[12],sol[12];
char dict[5000][13];
int nsolutions =3D 0;
int nwords;
int maxlen;
FILE *out;
void calc (int charloc, int low, int high) {
if (charloc =3D=3D maxlen) {
sol[charloc] =3D '\0';
for (int x =3D low; x < high; x++) {
if (strcmp (sol, dict[x]) =3D=3D 0) {
fprintf (out, "%s\n", sol);
nsolutions++;
}
}
return;
}
if (charloc > 0) {
for (int j=3Dlow; j <=3D high; j++){
if (sol[charloc-1] =3D=3D dict[j][charloc-1]) {
low=3Dj;
while (sol[charloc-1] =3D=3D dict[j][charloc-1])
j++;
high=3Dj;
break;
}
if (j =3D=3D high) return;
}
}
if (low > high) return;
switch(num[charloc]){
case '2':sol[charloc] =3D 'A'; calc(charloc+1,low,high);
sol[charloc] =3D 'B'; calc(charloc+1,low,high);
sol[charloc] =3D 'C'; calc(charloc+1,low,high);
break;=20
case '3':sol[charloc] =3D 'D'; calc(charloc+1,low,high);
sol[charloc] =3D 'E'; calc(charloc+1,low,high);
sol[charloc] =3D 'F'; calc(charloc+1,low,high);
break;=20
case '4':sol[charloc] =3D 'G'; calc(charloc+1,low,high);
sol[charloc] =3D 'H'; calc(charloc+1,low,high);
sol[charloc] =3D 'I'; calc(charloc+1,low,high);
break;=20
case '5':sol[charloc] =3D 'J'; calc(charloc+1,low,high);
sol[charloc] =3D 'K'; calc(charloc+1,low,high);
sol[charloc] =3D 'L'; calc(charloc+1,low,high);
break;=20
case '6':sol[charloc] =3D 'M'; calc(charloc+1,low,high);
sol[charloc] =3D 'N'; calc(charloc+1,low,high);
sol[charloc] =3D 'O'; calc(charloc+1,low,high);
break;=20
case '7':sol[charloc] =3D 'P'; calc(charloc+1,low,high);
sol[charloc] =3D 'R'; calc(charloc+1,low,high);
sol[charloc] =3D 'S'; calc(charloc+1,low,high);
break;=20
case '8':sol[charloc] =3D 'T'; calc(charloc+1,low,high);
sol[charloc] =3D 'U'; calc(charloc+1,low,high);
sol[charloc] =3D 'V'; calc(charloc+1,low,high);
break;=20
case '9':sol[charloc] =3D 'W'; calc(charloc+1,low,high);
sol[charloc] =3D 'X'; calc(charloc+1,low,high);
sol[charloc] =3D 'Y'; calc(charloc+1,low,high);
break;
}
}
int main(){
FILE *in=3Dfopen ("namenum.in", "r");
FILE *in2=3Dfopen ("dict.txt", "r");
int j;
out=3Dfopen ("namenum.out","w");
for (nwords =3D 0; fscanf (in2, "%s", &dict[nwords++]) !=3D EOF; =
)
;
fscanf (in, "%s",&num);
maxlen =3D strlen(num);
calc (0, 0, nwords);
if (nsolutions =3D=3D 0) fprintf(out,"NONE\n");
return 0;
}</PRE></STRONG></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/060b0224fcf8c737c995597f.htm=
l#send">=C6=C0=C2=DB</A> (0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 1.1.1 1.1.2 1.1.3 1.1.4 =
=B5=C8=C8=F5=D6=C7=CC=E2=CC=E2=BD=E2', 'USACO 1.1.1 1.1.2 1.1.3 =
1.1.4...','/leokan/blog/item/dd92253419d6183f5ab5f56d.html'];
var post =3D [true,'USACO 1.2.4 Palindromic Squares =CC=E2=BD=E2','USACO =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -