/**
* Fill in one symbol at the time. To guess the placements of next symbol X,
* consider every gap between characters in existing string and insert X's
* until the answer stops increasing.
*
* Running time: O(|Q| + 1 + freq[X]) for every X. If we work out the math:
*
* - The frequencies sum up to n.
* - The 1's sum up to sigma.
* - The |Q| at each step is the sum of frequencies of previous symbols.
* - Thus the worst case is freq[a] = n - sigma + 1, freq[b..z] = 1,
* which takes n * sigma queries (give or take).
* - For equal frequencies (freq[X] = n / sigma), n * sigma / 2 queries are
* needed.
*
* Author: Catalin Francu
**/
#include <string.h>
#define MAX_N 5000
char q[MAX_N + 1];
int query(char *q);
void shiftRight(char *s) {
char save = *s;
do {
int tmp = save;
save = *(s + 1);
*(s + 1) = tmp;
s++;
} while (*s != '\0');
}
void shiftLeft(char *s) {
do {
*(s - 1) = *s;
s++;
} while (*(s - 1) != '\0');
}
char* guess(int n, int s) {
/* we don't use s */
q[0] = '\0';
int c = 'a'; /* current symbol being inserted */
int answer = 0;
int pos = 0;
int len = 0; /* length of current string */
while (answer < n) {
/* roll back the last change and move on if answer != len */
if (answer != len) {
shiftLeft(q + pos);
len--;
if (q[pos - 1] == '\0') {
/* move on to the next symbol */
c++;
pos = 0;
}
/* otherwise leave pos unchanged, which skips one symbol < c */
}
/* insert another copy of c at position pos */
shiftRight(q + pos);
q[pos++] = c;
len++;
answer = query(q);
}
return q;
}
