10434 - 字母游戏

在家里用电视机做字母游戏是很流行的，其中一种玩法是:每一个字母有一个数值与之对应.你收集字母组成一个或多个字以得到尽可能高的得分.除非你已有了 “找字的方法”(“a way with words”)，你会把你知道的字都试一遍.有时你也许会查阅其拼写，然后计算得分。显然可以用计算机更为准确地完成此任务。上图示出了英文字母及其所对 应的值，当给出英文字(word) 的表列及收集的字母时，请找出所能形成的得分最高的字或字对(pairs of words)。

输入文件lgame.in中有一行由小写字母(A'到Z')组成的字符串， 这就是收集到字母(就是可以使用的字母)，字符串由至少3个字母至多7个字母(以任意顺序) 组成。字典文件lgame.dict由至多40，000行组成，文件的最后一行有'.' 表示文件的结束。文件中的字已按字母顺序排序。其它各行每一行都是由至少3个小写字母，至多7 个小写字母组成的字符串。文件中的字已按字母顺序排序。

在文件lgame.out的第一行，你的程序应 写上最高得分(子任务A)， 随后的每一行是由文件words.txt中查到的具有这个得分的所有的字和或字对(word pairs)(子任务B)。要利用图中给定的字母的值。当两个字能够形成 一个组合(具有给定的字母)时，这两个字应该打印到同一行，两个字中间用一个空格隔开。不许重复表示字对，例如'rag prom'和'prom rag'是同样的字对，因此只应该写出其中的一个。

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 game, every letter has a value, and you collect letters to form one or more words giving the highest possible score. Unless you have `a way with words', you will try all the words you know, sometimes looking up the spelling, and then compute the scores. Obviously, this can be done more accurately by computer.

Given the values in Figure 1, a list of words, and the letters collected: find the highest scoring words or pairs of words that can be formed.

PROGRAM NAME: lgame INPUT FORMAT One line with a string of lowercase letters (from a' to z'). The string consists of at least 3 and at most 7 letters in arbitrary order. SAMPLE INPUT (file lgame.in) prmgroa

DICTIONARY FORMAT At most 40,000 lines, each containing a string of at least 3 and at most 7 lowercase letters. At the end of this file is a line with a single period (`.'). The file is sorted alphabetically and contains no duplicates. SAMPLE DICTIONARY (file lgame.dict) profile program prom rag ram rom .

OUTPUT FORMAT On the first line, your program should write the highest possible score, and on each of the following lines, all the words and/or word pairs from file lgame.dict with this score. Sort the output alphabetically by first word, and if tied, by second word. A letter must not 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 words should be printed on the same line separated by a space. The two words should be in alphabetical order; for example, do not write rag prom', only write prom rag'. A pair in an output line may consist of two identical words.

SAMPLE OUTPUT (file lgame.out) This output uses the tiny dictionary above, not the lgame.dict dictionary.

24 program prom rag