ZOJ Problem Set - 1481
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:
Acceptable names for cattle are provided to you in the input, which contains a list of fewer than 50,000 acceptable cattle names. Take a cow's brand number and report which of all the possible words to which that number maps are in the given dictionary.
For instance, the brand number 4734 produces all the following names:
GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
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 30 digits long.
The first part of input is the dictionary of all valid names, one word per line. The dictionary ends with a line contains '#' only.
Following are several test cases, each test case has one single line with a number from 1 through 30 digits in length.
For each test case, output one line of valid names that can be generated from the input(in alphabetic order), seperated by space.
Author: CHENG, Long
Source: ZOJ Monthly, January 2003