[UVA] 11201 - The problem of the crazy linguist
| The Problem of the Crazy Linguist |
Background
Please, help the crazy linguist! He is trapped in his madness. He has developed a ``Spanish Beauty Criterion'' for words. It is defined as follows. Given a word w
(where n is the length of the word), he is interested in words which are formed by letters following pattern:
and, also, in his madness, he won't allow a word that actually has i, j,
and k, so that 
(that is, any letter can appear in the word at most two times).
Then, the ``Spanish Beauty Criterion'' (SBC) is defined as:
where P is defined as the probability of appearance of a letter in Spanish, defined by the following table:
| a | b | c | d | e | f | g | h | i | j | k | l | m |
| 12.53 | 1.42 | 4.68 | 5.86 | 13.68 | 0.69 | 1.01 | 0.70 | 6.25 | 0.44 | 0.00 | 4.97 | 3.15 |
| n | o | p | q | r | s | t | u | v | w | x | y | z |
| 6.71 | 8.68 | 2.51 | 0.88 | 6.87 | 7.98 | 4.63 | 3.93 | 0.90 | 0.02 | 0.22 | 0.90 | 0.52 |
So, given a word w, of size n, our poor linguist wants to know if this word is above or below the average of the SBC of all the words of size n that can be constructed following the above pattern and start with the same letter than w.
The Input
The input will have a first line with a number, N, the number of samples that will be entered to know if they are above or below the average. Following this first line, N lines with a word in each one (of at most seven characters each). All the input words follow the given pattern.
The Output
The output will have N lines, each line corresponding to one input word in order, showing just ``above or equal'' or ``below'', depending on the value of the SBC of that word relative to the average of those of the same size.
Sample Input
5 bubu terabit hacer qed loco
Sample Output
below above or equal above or equal above or equal above or equal
題目描述：
給定一個字串，問這個字串是在 平均 SBC 之上還是之下。
平均 SBC 的取樣：相同字元開頭，且相同長度，產生方式如上描述。
題目解法：
基本上可以本地建表，畢竟每次都要窮舉一次很慢，但是會過就算了。
#include <stdio.h>
#include <string.h>
int count[26], n;
char s[105];
double prob[26] = {
12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25, 0.44,
0.00, 4.97, 3.15, 6.71, 8.68, 2.51, 0.88, 6.87, 7.98, 4.63,
3.93, 0.90, 0.02, 0.22, 0.90, 0.52
};
char odd[] = {'a', 'e', 'i', 'o', 'u'};
char even[] = {'b', 'c', 'd', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'p', 'q', 'r', 's', 't', 'v', 'w', 'x', 'y', 'z'};
double SBC(char s[]) {
double ret = 0;
int i;
for(i = 0; s[i]; i++)
ret += (i+1)*prob[s[i]-'a'];
return ret;
}
double avgsbc;
int cnt;
void dfs(int idx) {
if(idx == n) {
s[idx] = '\0';
avgsbc += SBC(s);
cnt++;
return;
}
int i;
if(idx&1) {
for(i = 0; i < 5; i++) {
if(count[odd[i]-'a'] > 0) {
count[odd[i]-'a']--;
s[idx] = odd[i];
dfs(idx+1);
count[odd[i]-'a']++;
}
}
} else {
for(i = 0; i < 21; i++) {
if(count[even[i]-'a'] > 0) {
count[even[i]-'a']--;
s[idx] = even[i];
dfs(idx+1);
count[even[i]-'a']++;
}
}
}
}
int main() {
int testcase;
int i;
scanf("%d", &testcase);
while(testcase--) {
scanf("%s", s);
memset(count, 0, sizeof(count));
double sbc = SBC(s);
for(i = 0; s[i]; i++)
count[s[i]-'a']++;
for(i = 0; i < 26; i++)
count[i] = 2;
count[s[0]-'a'] = 1;
avgsbc = 0, cnt = 0;
n = strlen(s);
dfs(1);
avgsbc /= cnt;
puts(sbc < avgsbc ? "below" : "above or equal");
}
return 0;
}