54 lines
3.2 KiB
HTML
54 lines
3.2 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
|
|
<!-- saved from url=(0056)http://olympiads.win.tue.nl/ioi/ioi95/contest/lgame.html -->
|
|
<HTLM><HTML><HEAD><TITLE>IOI'95 Task: Letter Game</TITLE>
|
|
<META http-equiv=Content-Type content="text/html; charset=gb2312">
|
|
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
|
|
<BODY background="IOI'95 Task Letter Game.files/backgrnd.gif">
|
|
<H1><A href="http://olympiads.win.tue.nl/ioi/ioi95/index.html"><IMG
|
|
alt="[ IOI Home page ]" hspace=5 src="IOI'95 Task Letter Game.files/logo.gif"
|
|
align=middle border=0></A> Task: Letter Game</H1>
|
|
<CENTER><IMG src="" align=bottom> <BR>Figure 1:Each of the 26 lowercase
|
|
letters and its value </CENTER>
|
|
<P>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.
|
|
<P>Given the values in Figure 1, a list of English words, and the letters
|
|
collected: find the highest scoring words or pairs of words that can be formed.
|
|
<H2>Input Data</H2>The input file <TT>INPUT.TXT</TT> contains one line with a
|
|
string of lowercase letters (from `<TT>a</TT>' to `<TT>z</TT>'): the letters
|
|
collected. The string consists of at least 3 and at most 7 letters in
|
|
arbitrary order.
|
|
<P>The `dictionary' file <TT>WORDS.TXT</TT> consists of at most 40,000 lines. At
|
|
the end of this file is a line with a single period (`<TT>.</TT>'). Each of the
|
|
other lines contains a string of at least 3 and at most 7 lowercase
|
|
letters. The file <TT>WORDS.TXT</TT> is sorted alphabetically and contains no
|
|
duplicates.
|
|
<H2>Output Data</H2>On the first line of file <TT>OUTPUT.TXT</TT>, 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 <TT>WORDS.TXT</TT> with this
|
|
score (Subtask B). A letter must not occur more often in an output line
|
|
than in the input line. Use the letter values given in Figure 1.
|
|
<P>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. Do not duplicate
|
|
pairs; for example, `<TT>rag prom</TT>' and `<TT>prom rag</TT>' are the same
|
|
pair, therefore only one of them should be written. A pair in an output line may
|
|
consist of two identical words.
|
|
<H2>Example Input and Output</H2>Figure 2 gives example input and output.
|
|
<CENTER><PRE>
|
|
_____________ _____________ ______________
|
|
| WORDS.TXT | | INPUT.TXT | | OUTPUT.TXT |
|
|
|___________| |___________| |____________|
|
|
| profile | | prmgroa | | 24 |
|
|
| program | |___________| | program |
|
|
| prom | | prom rag |
|
|
| rag | |____________|
|
|
| ram |
|
|
| rom |
|
|
| . |
|
|
|___________|
|
|
</PRE>Figure 2: Example input and output </CENTER>
|
|
<HR>
|
|
<A href="mailto:ioi95@win.tue.nl">IOI 95</A> </BODY></HTML>
|