小皮博客 | Xiaopi's Blog

11_USACO_Section-1.2_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)

4734

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


翻译:

在威斯康星州大型牧场,通常为了统计方便给奶牛编上数字的编号,养牛人不欣赏这个备案制度的优势,他们希望给牛们取一个赏心悦目的名字而不是说“过来,4734号,一边待着去”。

请你帮助贫穷的牧牛人写一个程序,将牛的序列号翻译成尽量唯一的一个名称,由于牧牛工都有蜂窝电话,所以使用标准的按键式电话键盘的从数字到字母的映射(R),Q和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 :P ,R,S

可接受的牛的名称在提供给您的一个名为“ dict.txt ”的文件中 ,其中包含一个少于5000个名字的(全部由大写字母构成)的列表 。请根据一个牛的序列号来报告出这个数字通过上述的映射可以得出的在字典分级环境中可能的名称 ,这个字典是按照升序排列的。

例如, 4734号的品牌生产所有的名称如下:
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
碰巧的是,这81名字中只有一个是有效的,在列表中它是“格雷” 。

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.

写一个程序给出一个牛的序列号对应的在字典中所有合法的名称,或者给出”NONE”如果在字典中一个也找不到。序列号可能有10几个字母那么多。
程序名称: namenum
输入格式
只有一行,从1数到12位长度。
SAMPLE INPUT (文件namenum.in)

4734

输出格式
从输入,字母升序排列,每行一个有效的名字。
样本输出(文件namenum.out)

GREG

代码:

C++代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
ID: sunsetx1
PROG: namenum
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

char char2name(char a);

int main() {
ofstream fout ("namenum.out");
ifstream fin ("namenum.in");
ifstream fd("dict.txt");

char name[5000][13];
char brand[13];
fin >> brand;

int alpha[26] = { 2 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 5 , 5 , 5 , 6 , 6 , 6 , 7 , 0 , 7 , 7 , 8 , 8 , 8 , 9 , 9 , 9 , 0 } ;
int count = 0;
while (fd >> name[count])
count++;

char current[13];
int find = 0;
for(int i = 0; i < count; i++) {
int flag = 0;
if(strlen(brand) != strlen(name[i]))continue;
for (int j = 0; j < strlen(name[i]) && j < strlen(brand); j++) {
if (alpha[name[i][j] - 'A'] == brand[j] - '0')
continue;
else{
flag = 1;
break;
}
}
if (!flag) {
find = 1;
fout << name[i] << endl;
}
}
if (!find) {
fout << "NONE" << endl;
}
}

USACO测试库输出结果:

USER: 领 盛 [sunsetx1]
TASK: namenum
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 3504 KB]
   Test 2: TEST OK [0.000 secs, 3504 KB]
   Test 3: TEST OK [0.000 secs, 3504 KB]
   Test 4: TEST OK [0.000 secs, 3504 KB]
   Test 5: TEST OK [0.000 secs, 3504 KB]
   Test 6: TEST OK [0.000 secs, 3504 KB]
   Test 7: TEST OK [0.011 secs, 3504 KB]
   Test 8: TEST OK [0.000 secs, 3504 KB]
   Test 9: TEST OK [0.000 secs, 3504 KB]
   Test 10: TEST OK [0.000 secs, 3504 KB]
   Test 11: TEST OK [0.000 secs, 3504 KB]
   Test 12: TEST OK [0.000 secs, 3504 KB]
   Test 13: TEST OK [0.000 secs, 3504 KB]
   Test 14: TEST OK [0.000 secs, 3504 KB]
   Test 15: TEST OK [0.011 secs, 3504 KB]

All tests OK.
Your program ('namenum') produced all correct answers! 
This is your submission #7 for this problem. Congratulations!

Here are the test data inputs:
------- test 1 ----
4734
------- test 2 ----
234643
------- test 3 ----
5747867437
------- test 4 ----
223
------- test 5 ----
532

版权声明

本文标题:11_USACO_Section-1.2_Name-That-Number

文章作者:盛领

发布时间:2015年02月02日 - 13:11:39

原始链接:http://blog.xiaoyuyu.net/post/a98567c9.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

如您有任何商业合作或者授权方面的协商,请给我留言:sunsetxiao@126.com

盛领 wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!