namethatnumber - codetrick
http://acmph.blogspot.com/2010/12/usaco-name-that-number.html
There are two approaches to this problem:
https://turing13.wordpress.com/2015/04/06/usaco-name-that-number/
倒过来考虑即可，拿字典去和数字比较
http://blog.csdn.net/lisc741/article/details/8252226
https://dzone.com/articles/usaco-name-number-puzzle
Read full article from namethatnumber - codetrick
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
http://acmph.blogspot.com/2010/12/usaco-name-that-number.html
There are two approaches to this problem:
First : since the input number has at most 12 digits and for each digit there are 3 candidates if you build all the possibilities and then search them in the dictionary the order of your program will become
O(3^12 * nlog(n)) n = 5000 531441 * 42585 that I think is a little too high to run in the time limit.
Second : you can map all the strings in the dictionary to The explained number, and then easily when you read the input number search that whether you have that number in your map data structure and print all the strings mapped to that number, print "NONE" otherwise.
X. http://mangogao.com/read/63.htmlO(3^12 * nlog(n)) n = 5000 531441 * 42585 that I think is a little too high to run in the time limit.
Second : you can map all the strings in the dictionary to The explained number, and then easily when you read the input number search that whether you have that number in your map data structure and print all the strings mapped to that number, print "NONE" otherwise.
https://turing13.wordpress.com/2015/04/06/usaco-name-that-number/
倒过来考虑即可，拿字典去和数字比较
char hash(char &a){ int k = a - 'A'; if (k < 3) return '2'; if (k < 6) return '3'; if (k < 9) return '4'; if (k < 12) return '5'; if (k < 15) return '6'; if (k < 19) return '7'; if (k < 22) return '8'; return '9';}int main(){ ifstream fin("namenum.in"); ifstream ftxt("dict.txt"); ofstream fout("namenum.out"); string p,q,qq; int k(0); fin >> p; for (int i=0;i<4617;++i) { ftxt >> q; qq = q; for (int j=0;j<q.size();++j) q[j]=hash(q[j]); if (p == q) { fout << qq << endl; k=1; } } if (k==0) fout << "NONE" << endl; return 0;}int main()
{
char num[20] ;
bool flag = 0 ;
Count = 0 ;
while( fin >> dict[Count] )
Count ++ ;
in >> num ;
for( int i = 0 ; i < Count ; i ++ )
{
int FLAG = 0 ;
if( strlen( num ) != strlen( dict[i] ) ) continue ;
for( int j = 0 ; j < strlen( dict[i] ) ; j ++ )
{
if( function[dict[i][j] - 'A'] == num[j] - '0' ) continue ;
else {
FLAG = 1 ;
break ;
}
}
if( !FLAG )
{
flag = 1 ;
fout << dict[i] << endl ;
}
}
if( !flag ) fout << "NONE" << endl ;
return 0 ;
}
X. http://www.cnphp6.com/archives/15168char number_letter[10][3] = {
{},// 0
{},// 1
{'A','B','C'}, // 2
{'D','E','F'}, // 3
{'G','H','I'}, // 4
{'J','K','L'}, // 5
{'M','N','O'}, // 6
{'P','R','S'}, // 7
{'T','U','V'}, // 8
{'W','X','Y'} // 9
};
int main()
{
ofstream fout ("namenum.out");
ifstream fin ("namenum.in");
ifstream fdict ("dict.txt");
string word;
vector <string> dicts;
while(fdict.good() && !fdict.eof())
{
getline(fdict,word,'\n');
dicts.push_back(word);
}
string num;
fin >> num;
int numSize = num.size();
for(vector<string>::iterator iter=dicts.begin();iter!=dicts.end();)
{
word = *iter;
int wordSize = word.size();
if(wordSize != numSize)
{
dicts.erase(iter);
continue;
}
++iter;
}
for(int i = 0; i < numSize; i++)
{
int rightNum = (int)num[i] - 48;
for(vector<string>::iterator iter=dicts.begin();iter!=dicts.end();)
{
word = *iter;
char rightLetter = word[i];
bool key = false;
for(int j = 0; j < 3; j++)
{
char letter = number_letter[rightNum][j];
if(letter == rightLetter)
{
key = true;
break;
}
}
if(key)
{
++iter;
}else
{
dicts.erase(iter);
continue;
}
}
}
if(dicts.size() == 0)
{
fout << "NONE" << endl;
}else
{
for(vector<string>::iterator iter=dicts.begin();iter!=dicts.end();++iter)
{
word = *iter;
fout << word << endl;
}
}
return 0;
}
X. Permutationhttps://dzone.com/articles/usaco-name-number-puzzle
Read full article from namethatnumber - codetrick
