Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Letter Game
发信站: 哈工大紫丁香 (2002年03月29日13:32:57 星期五), 站内信件

Task: Letter Game
Figure 1:Each of the 26 lowercase letters and its value
Letter games are popular at home and on television. In one version of the ga
me, every letter has a value, and you collect letters to form one or more wo
rds giving the highest possible score. Unless you have `a way with words', y
ou will try all the words you know, sometimes looking up the spelling, and t
hen compute the scores. Obviously, this can be done more accurately by compu
ter.
Given the values in Figure 1, a list of English words, and the letters colle
cted: find the highest scoring words or pairs of words that can be formed.
Input Data
The input file INPUT.TXT contains one line with a string of lowercase letter
s (from `a' to `z'): the letters collected. The string consists of at least 
3 and at most 7 letters in arbitrary order.
The `dictionary' file WORDS.TXT consists of at most 40,000 lines. At the end
 of this file is a line with a single period (`.'). Each of the other lines 
contains a string of at least 3 and at most 7 lowercase letters. The file WO
RDS.TXT is sorted alphabetically and contains no duplicates.
Output Data
On the first line of file OUTPUT.TXT, your program should write the highest 
score (Subtask A), and on each of the following lines, all the words and/or 
word pairs from file WORDS.TXT with this score (Subtask B). A letter must no
t occur more often in an output line than in the input line. Use the letter 
values given in Figure 1.
When a combination of two words can be formed with the given letters, the wo
rds should be printed on the same line separated by a space. Do not duplicat
e pairs; for example, `rag prom' and `prom rag' are the same pair, therefore
 only one of them should be written. A pair in an output line may consist of
 two identical words.
Example Input and Output
Figure 2 gives example input and output.
_____________   _____________    ______________
| WORDS.TXT |   | INPUT.TXT |    | OUTPUT.TXT |
|___________|   |___________|    |____________|
| profile   |   | prmgroa   |    | 24         |
| program   |   |___________|    | program    |
| prom      |                    | prom rag   |
| rag       |                    |____________|
| ram       |
| rom       |
| .         |
|___________|
Figure 2: Example input and output

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]