UVA – 188 – Perfect Hash

#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <sstream>
#include <set>
#include <ctype.h>
using namespace std;
int C, n, w[20];
char line[200];
char words[20][10];
char* word;
int calc() {
unsigned i, rep = 0;
for (i = 0; i < strlen(word); ++i)
rep = (rep << 5) + word[i] - 'a' + 1;
return rep;
}
int make() {
int i, j;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
if ((C / w[i]) % n == (C / w[j]) % n) {
C = min((C / w[i] + 1) * w[i], (C / w[j] + 1) * w[j]);
return 0;
}
return 1;
}
int main() {
while (gets(line)) {
set<int> exist;
puts(line);
n = 0;
word = strtok(line, " ");
while (word) {
w[n] = calc();
if (exist.find(w[n]) == exist.end())
exist.insert(w[n++]);
word = strtok(NULL, " ");
}
C = *min_element(w, w + n);
while (!make())
;
printf("%d\n\n", C);
}
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: