Page 1 of 1

### Problem Hidden Password from ACM-ICPC

Posted: Mon Oct 10, 2005 2:04 pm
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;
}
``````

### Wrong input file

Posted: Mon Oct 10, 2005 3:39 pm
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

Posted: Thu Oct 20, 2005 8:50 pm
``      for (; t > 1;)  ``