/**
* Guess one character at the time. To guess the next character, try to insert
* every character in sigma at every position in the current query.
*
* Queries: n^2 sigma, but somewhat better in practice
*
* Author: Catalin Francu
**/
#define MAX_N 5000
char q[MAX_N + 1]; /* initially empty */
int query(char *q);
char* guess(int n, int s) {
for (int l = 1; l <= n; l++) {
/* Guess one more character. Start from the end and work backwards */
q[l] = '\0';
int pos = l - 1, c = 'a', answer;
do {
q[pos] = c;
answer = query(q);
if (answer != l) {
c++;
if (c >= 'a' + s) {
c = 'a';
q[pos] = q[pos - 1];
pos--;
}
}
} while (answer < l);
}
return q;
}
