USACO Section 1.2.4 Name That Number

Mar 5, 2013 2 分钟阅读时间 usc, csdn

此页面通过工具从 csdn 导出，格式可能有问题。

题目

Name That Number

Among the large Wisconsin cattle ranchers, it is customary to brand cows with serial numbers to please the Accounting Department. The cow hands don't appreciate the advantage of this filing system, though, and wish to call the members of their herd by a pleasing name rather than saying, "C'mon, #4734, get along."

Help the poor cowhands out by writing a program that will translate the brand serial number of a cow into possible names uniquely associated with that serial number. Since the cow hands all have cellular saddle phones these days, use the standard Touch-Tone(R) telephone keypad mapping to get from numbers to letters (except for "Q" and "Z"):

          2: A,B,C     5: J,K,L    8: T,U,V
          3: D,E,F     6: M,N,O    9: W,X,Y
          4: G,H,I     7: P,R,S

Acceptable names for cattle are provided to you in a file named "dict.txt", which contains a list of fewer than 5,000 acceptable cattle names (all letters capitalized). Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary which is supplied as dict.txt in the grading environment (and is sorted into ascending order).

For instance, the brand number 4734 produces all the following names:

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

As it happens, the only one of these 81 names that is in the list of valid names is "GREG".

Write a program that is given the brand number of a cow and prints all the valid names that can be generated from that brand number or ``NONE'' if there are no valid names. Serial numbers can be as many as a dozen digits long.

PROGRAM NAME: namenum

INPUT FORMAT

A single line with a number from 1 through 12 digits in length.

SAMPLE INPUT (file namenum.in)

OUTPUT FORMAT

A list of valid names that can be generated from the input, one per line, in ascending alphabetical order.

SAMPLE OUTPUT (file namenum.out)

GREG

思路

思路一：

读入num，生成所有的名字，然后对比字典，听起来很简单的样子。问题是

1）首先你需要构建一张数字字母映射表，对每个数字开一个数组或者一个字符串，写起来比较麻烦。

2）对于每个生成的字符串要对比字典，为了不超时（N_dict=5000），只能是O(n)的算法也就是一边生成一边对比同时记录对比的位置然后下次继续从此处开始对比。写的时候细节要很小心，比较费神。

思路二：

与思路一相反，从字典入手，把每一个名字转换成数字看是不是num，是的话输出（注意不能终止程序因为可能有多个匹配）。扫描一遍字典5000次运算而已。

PS：由于最长的名字有12位，int无力需要开 long long，再就是USACO服务器是linux，所以需要 %lld 。

代码

#include <cstdio>
#include <cstring>
int hash[26]={2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};
long long num;
char a[13];
int main(){
	freopen("namenum.in","r",stdin);
	freopen("namenum.out","w",stdout);
	scanf("%lld",&num);
	freopen("dict.txt","r",stdin);
	int yes=0;
	while (scanf("%s",a) != EOF){
		int l=strlen(a);
		long long s=0;
		for (int i(0);i<l;i++){
			s=s*10+hash[a[i]-'A'];
		}
		if (s==num) {
		   printf("%s\n",a);
		   yes=1;
		}
	}
	if (!yes) printf("NONE\n");
	return 0;
}

USACO Algorithm ACM

huiren

Code Artisan

问渠那得清如许，为有源头活水来