IOI '95 - Eindhoven, Netherlands

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 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.

Input Format

The first section of the input will consist of the dictionary. There will be at most 40,000 lines in the dictionary, each containing a string of at least 3 and at most 7 lowercase letters. The end of the dictionary will be denoted by a line with a single period ('.'). The dictionary is sorted alphabetically and contains no duplicates.

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.

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 the dictionary 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 Input

profile
program
prom
rag
ram
rom
.
prmgroa

Sample Output

24
program
prom rag

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 25, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I solved it with a brute force O(n^2) solution, which doesn't happen a lot for 15pt problems... Is there something I'm missing?

Yeah, my solution of O(N (length of string)!) solution somehow passed too. I guess this problem just has weak data.

I just realised this is a twenty year old question, that's probably why.

I tried it offline and the output matched the test case, but it's still giving me WA.

Sigh, Jeffrey...

[quote]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.[/quote]

Okay the output in the IOI test data confused me