188 - Perfect Hash

[Joe Smith]

I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added the long long just as an extra precaution.)

[cpp]
while (gets(buf)) {
printf("%s\n", buf);
vector<string> vs = split(buf, " ");
c.clear();
for (int i=0; i<vs.size(); i++) {
int code = 0;
for (int j=0; j<vs.length(); j++)
code = code*32 + (vs[j]-'a'+1);
c.push_back(code);
}
int n=c.size();
long long C=2;
for (;;) {
long long biggest=-1;
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
if (i!=j && ((C/c)%n == (C/c[j])%n))
biggest >?= min((C/c+1)*c,(C/c[j]+1)*c[j]);
if (biggest==-1) break;
C=biggest;
}
printf("%lld\n\n", C);
}
}
[/cpp]

Thanks...

[fcarlos]

Folks!!

I would like of a tests sample of input/output for test my program. I test it
with following samples and i got the correct answer

this is a test of some words to try out
a bee see dee
the of and to a in that is i it with for as

this is a test of some words to try out
17247663

a bee see dee
4427

the of and to a in that is i it with for as
667241.

But, I got WA of Judge.

Thanks advance.

[obayashi]

then waht if the words duplicates?

see example below

Code: Select all

aaa bbb bbb ccc ccc

[zbogi]

The second part seems alright to me(it is almost the same as mine- I got ACC). However, I don`t know if you read the words ok. Are you sure you read the last word?

[uzioriluzan]

you must use long long. but the initial value for C must be the minimum of the vector, not 2.

I don't understand why I'm getting WA here. The problem desc. says exactly what to do and it works on all the input i've tried. Can anyone see the problem? (I know my split function is fine, and i added the long long just as an extra precaution.)

[cpp]
while (gets(buf)) {
printf("%s\n", buf);
vector<string> vs = split(buf, " ");
c.clear();
for (int i=0; i<vs.size(); i++) {
int code = 0;
for (int j=0; j<vs.length(); j++)
code = code*32 + (vs[j]-'a'+1);
c.push_back(code);
}
int n=c.size();
long long C=2;
for (;;) {
long long biggest=-1;
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
if (i!=j && ((C/c)%n == (C/c[j])%n))
biggest >?= min((C/c+1)*c,(C/c[j]+1)*c[j]);
if (biggest==-1) break;
C=biggest;
}
printf("%lld\n\n", C);
}
}
[/cpp]

Thanks...

[Quantris]

wrong, the problem assures 32-bit integer (unsigned, of course) is sufficient.

[alexg]

wrong, the problem assures 32-bit integer (unsigned, of course) is sufficient.

Works fine with signed 32-bit integers. There are a maximum of 5 letters in each word. 5 bits for each letter = a maximum of 25 bits required.

[Quantris]

I'm pretty sure you can make the required C exceed signed 32-bit.

EDIT:

zzzzz zzzzy fafa zdfdz dfazz zzxf s

gives 2532818294, which fits in unsigned but not in signed.

[zaomaohao]

I understand what you are saying but I think there should be more comments regarding the threat that was initially started so that the pool of thoughts is attracted. Regards.

[ryx]

Does anyone know, for every possible input, how to guarantee there is always an answer exist?
I have no ideas.
Thanks