Problem Hidden Password from ACM-ICPC

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

EfEr
New poster
Posts: 5
Joined: Thu Sep 22, 2005 8:56 pm
Location: Bucuresti, Romania
Contact:

Problem Hidden Password from ACM-ICPC

I tried to solve the problem from http://acmicpc-live-archive.uva.es/nuev ... php?p=2755
I got WA, even though I got Accepted on another on-line judge (with exactly the same source), and I got 100 points at a romanian contest in which it was a similar problem (I tested it with the tests from that contest).
I think the tests are wrong, but still there are some Accepted solutions...

Here is my code:

Code: Select all

``````#include <cstdio>
#include <cassert>

int n;
inline int next(int s) {
return (s + 1) % n;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("t.in", "rt", stdin);
#endif

const int nmax = 100000;
int ts;
scanf("%d", &ts);
for (int it = 0; it < ts; ++ it) {
scanf("%d", &n);
char s[nmax];
scanf("%s", s);
int w[nmax], t = n;
for (int i = 0; i < n; ++ i)
w[i] = i;
for (; t > 1;) {
int nt = 0;
for (int i = 0; i < t; ++ i) {
if (i + 1 < t) {
int s1 = w[i], s2 = w[i + 1], j = 0;
const int l = s2 - s1;
assert(l > 0);
for (; s[s1] == s[s2] && j < l; ++ j, s1 = next(s1), s2 = next(s2));
if (j < l && s[s1] > s[s2])
w[nt ++] = w[i + 1];
else w[nt ++] = w[i];
++ i;
}
else w[nt ++] = w[i];
}
t = nt;
}

printf("%d\n", w[0]);
}
return 0;
}
``````

EfEr
New poster
Posts: 5
Joined: Thu Sep 22, 2005 8:56 pm
Location: Bucuresti, Romania
Contact:

Wrong input file

Well, I managed to solve it after all... The problem was that the number of tests was different then it should have been... I got AC when I read until I got EOF

ledins
New poster
Posts: 2
Joined: Sat Oct 01, 2005 3:23 am
your coding style rocks:

Code: Select all

``      for (; t > 1;)  ``