Submission #160331

#	Time	Username	Problem	Language	Result	Execution time	Memory
160331		model_code	Password (RMI18_password)	C11	30 / 100	389 ms	376 KiB

password

/**
 * 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 30
• Subtask 5: 0 / 20