Task: Letter Game (International Olympiad in Informatics)

letterGame.cpp

// ref: http://ioinformatics.org/locations/ioi95/contest/tasks/lgame.shtml

// PLEASE NOTICE THAT THIS IS A SOLUTION FOR THE FIRST STEP ONLY !

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

static map<char, int> values;

void fillValues() {
	values['a'] = 2;
	values['b'] = 5;
	values['c'] = 4;
	values['d'] = 4;
	values['e'] = 1;
	values['f'] = 6;
	values['g'] = 5;
	values['h'] = 5;
	values['i'] = 1;
	values['j'] = 5;
	values['k'] = 6;
	values['l'] = 3;
	values['m'] = 5;
	values['n'] = 2;
	values['o'] = 3;
	values['p'] = 5;
	values['q'] = 7;
	values['r'] = 2;
	values['s'] = 1;
	values['t'] = 2;
	values['u'] = 4;
	values['v'] = 6;
	values['w'] = 6;
	values['x'] = 7;
	values['y'] = 5;
	values['z'] = 7;
}

int getWordValue(map<char, int> input, string& word) {
	int sum = 0;

	for (int i=0 ; i < word.size() ; i++) {
		input[word[i]]--;
		if (input[word[i]] < 0) {
			return -1;
		}

		sum += values[word[i]];
	}

	return sum;
}

int main() {
	string input = "prmgroa";
	map<char, int> iMap;

	/* put input in map */
	for (int i=0 ; i < input.length() ; i++) {
		if (!iMap.count(input[i]))
			iMap[input[i]] = 1;
		else
			iMap[input[i]]++;
	}

	fillValues();

	vector<string> words;
	words.push_back("profile");
	words.push_back("program");
	words.push_back("prom");
	words.push_back("rag");
	words.push_back("ram");
	words.push_back("rom");

	int maxValue = 0;
	string maxWord;
	for (int i=0 ; i < words.size() ; i++) {
		int value = getWordValue(iMap, words[i]);
		if (maxValue < value) {
			maxValue = value;
			maxWord = words[i];
		}
	}

	cout << maxValue << endl;
	cout << maxWord << endl;
}

question.md

Task: Letter Game

Return to IOI '95 Home | IOI '95 Day 2

source: International Olympiad in Informatics

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 English words, and the letters collected: 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 letters (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 WORDS.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 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. Do not duplicate 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