赞
踩
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.
prmgroa
profile
program
prom
rag
ram
rom
.
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.
This output uses the tiny dictionary above, not the lgame.dict dictionary.
24
program
prom rag
字母游戏
IOI 1995
图1:每个26个小写字母和它的值
字母游戏在家里和电视上都很流行。在游戏的一个版本中,每一个字母都有一个值,你可以收集字母来形成一个或多个单词以获得最高的分数。除非你有“一种方法”,否则你会尝试所有你知道的单词,有时查找拼写,然后计算分数。显然,这可以通过计算机更精确地完成。
给出图1中的值,单词列表和所收集的字母:找到可以形成的最高值的单词或词组。
项目名称:lgame
输入格式
一行有一系列小写字母(从“a”到“z”)。该字符串由至少3个字母组成,最多7个字母。
示例输入(文件lgame.in)
prmgroa
字典格式
在大多数4万行中,每个字符串包含至少3个字符串,最多7个小写字母。在这个文件的末尾,有一行(' . ')。文件按字母顺序排序,不包含重复项。
样本字典(文件lgame.dict)
profile program prom rag ram rom .输出格式
当两个单词的组合可以用给定的字母组成时,单词应该印在同一行上。这两个字应该按字母顺序排列;例如,不要写“rag prom”,只写“prom rag”。一个输出行中的一对可能包含两个相同的单词。
样例输出(文件lgame.out)
这个输出使用了上面的小字典,而不是lgame.dict。
24
program
prom rag
- /*
- ID : mcdonne1
- LANG : C++
- TASK : lgame
- */
-
- #pragma GCC optimize("O3")
-
- #include <iostream>
- #include <fstream>
- #include <cstring>
-
- using namespace std;
-
- string dic[40001];
- string ans[20];
- string s;
- int n, l, __m, temp, maxx, __ans;
- int hs[26], ps[26], qs[26];
- int len[40001], m[40001];
-
- const int val[26] = {2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
-
- inline void find(int x) {
- for (int i = x + 1; i < n ;i++)
- if (m[i] <= __m) {
- memcpy (qs, ps, sizeof(ps));
- for (int j =0; j < len[i]; j++)
- if (!qs[dic[i][j] - 'a']) goto __Con;
- else qs[dic[i][j] - 'a']--;
- if (m[i] + m[temp] > maxx) {
- maxx = m[i] + m[temp];
- __ans = 1;
- ans[1] = dic[temp] + " " + dic[i];
- } else if(m[i] + m[temp] == maxx)
- ans[++__ans] = dic[temp] + " " + dic[i];
- __Con : ;
- }
- }
-
- int main () {
- ios::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- ifstream cin("lgame.dict", ios::in);
- while(cin>>dic[n]) n++;
- --n;
- for (int i = 0; i < n; i++) {
- len[i] = dic[i].length();
- for (int j = 0; j < len[i]; j++)
- m[i] += val[dic[i][j] - 'a'];
- }
- cin.close();
- ifstream fin("lgame.in", ios::in);
- ofstream fout("lgame.out", ios::out);
- fin>>s;
- l = s.length();
- for (int i = 0; i < l; i++) {
- __m += val[s[i] - 'a'];
- ++hs[s[i] - 'a'];
- }
- for (int i = 0; i < n; i++)
- if (len[i] <= l and m[i] <= __m) {
- memcpy (ps, hs, sizeof(hs));
- for (int j = 0; j < len[i]; j++)
- if (!ps[dic[i][j] - 'a']) goto Con;
- else ps[dic[i][j] - 'a']--;
- if (m[i] > maxx) {
- maxx = m[i];
- __ans = 1;
- ans[1] = dic[i];
- } else if(m[i] == maxx)
- ans[++__ans] = dic[i];
- if (l - len[i] >= 3) {
- temp = i;
- __m -= m[i];
- find(i);
- __m += m[i];
- }
- Con : ;
- }
- fout<<maxx<<endl;
- for (int i = 1; i<= __ans; i++)
- fout<<ans[i]<<endl;
- fin.close();
- fout.close();
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。