10506 - The Ouroboros problem
Posted: Thu Jun 19, 2003 5:45 am
There seem to be issues with the test data (or verifier) for this problem. I say this because I wrote my own verifier, and it returned "YES" for all valid input (besides the cases where n=1, where I verified the "0" output by my program by hand). Following is the verifier code (again, it doesn't work if n=1, and I know why):
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int m, n;
int ntom;
char blah[200000];
int doit(int st) {
int i, j=0;
for (i = st; i < st+m; i++) {
j *= n;
j += blah-'0';
}
return j;
}
main() {
int seen[131072];
int i;
while(scanf("%i %i %s", &m, &n, blah) != EOF) {
ntom=1;
for (i = 0; i < m; i++) ntom *= n;
if (strlen(blah) != ntom) goto reject;
strncat(blah, blah, ntom);
memset(seen, 0, sizeof(seen));
for (i = 0; i < ntom; i++) {
seen[doit(i)]++;
}
for (i = 0; i < ntom; i++) {
if (seen != 1) goto reject;
}
printf("YES\n");
continue;
reject:
printf("NO %i %i\n", m, n);
}
}
[/c]
When run on every legal input, my program outputs something which this verifier says is a "YES" or a "NO m 1". The "NO m 1" cases are actually correct, since the solution outputs a lone "0."
If I've done something stupid, please let me know.
[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int m, n;
int ntom;
char blah[200000];
int doit(int st) {
int i, j=0;
for (i = st; i < st+m; i++) {
j *= n;
j += blah-'0';
}
return j;
}
main() {
int seen[131072];
int i;
while(scanf("%i %i %s", &m, &n, blah) != EOF) {
ntom=1;
for (i = 0; i < m; i++) ntom *= n;
if (strlen(blah) != ntom) goto reject;
strncat(blah, blah, ntom);
memset(seen, 0, sizeof(seen));
for (i = 0; i < ntom; i++) {
seen[doit(i)]++;
}
for (i = 0; i < ntom; i++) {
if (seen != 1) goto reject;
}
printf("YES\n");
continue;
reject:
printf("NO %i %i\n", m, n);
}
}
[/c]
When run on every legal input, my program outputs something which this verifier says is a "YES" or a "NO m 1". The "NO m 1" cases are actually correct, since the solution outputs a lone "0."
If I've done something stupid, please let me know.