#include "bits/stdc++.h" using namespace std; // #define int long long // #define DEBUG 0 // #define MAX_QUERIES 50000 // #define MAX_N 5000 // #define MAX_SIGMA 26 // static string password; // static int n, s, numQueries; // static stringstream msg; // static void end(int success) { // cout << (success ? "SUCCESS! " : "ERROR: ") << msg.str() << endl; // exit(0); // } // int query(string q) { // if (++numQueries > MAX_QUERIES) { // msg << "Could not guess the password with " << MAX_QUERIES << " questions."; // end(0); // } // int len = q.size(); // // validation // if (len < 1 || len > n) { // msg << "Query '" << q << "' should have length between 1 and " // << n << " characters."; // end(0); // } // for (int i = 0; i < len; i++) { // if (q[i] < 'a' || q[i] >= 'a' + s) { // msg << "Illegal character '" << q[i] << "' found."; // end(0); // } // } // // while possible, advance one character in q and find its next // // occurrence in password // int i = 0, j = 0, plen = password.size(); // while (i < plen && j < len) { // while ((i < plen) && (password[i] != q[j])) { // i++; // } // if (i < plen) { /* found a match */ // i++; // j++; // } // } // if (DEBUG) { // cout << "Question #" << numQueries << " [" << q << "] answer " << j << endl; // } // return j; // } int query(string s); string guess(int n, int s){ array<int, 2>shi[30][30]; for(int i = 0; i < s; i++){ for(int j = i + 1; j < s; j++){ string a = "", b = ""; for(int k = 0; k < n; k++) a += (k % 2 ? j + 'a' : i + 'a'); for(int k = 0; k < n; k++) b += (k % 2 ? i + 'a' : j + 'a'); int ra = query(a), rb = query(b); if(ra > rb) shi[i][j] = {ra, i}; else shi[i][j] = {rb, j}; } } string sk = ""; bool valid = 1; int cnt[30][30] = {}; while(valid){ valid = 0; bool idk[30]; for(int i = 0; i < 30; i++) idk[i] = 1; for(int i = 0; i < s; i++){ for(int j = i + 1; j < s; j++){ if(cnt[i][j] >= shi[i][j][0]) continue; valid = 1; int f, se; if(shi[i][j][1] == i){ f = i; se = j; } else{ f = j; se = i; } if(cnt[i][j] % 2 == 0) idk[se] = 0; else idk[f] = 0; } } if(!valid) continue; for(int i = 0; i < s; i++){ if(idk[i]){ sk += i + 'a'; for(int j = i + 1; j < s; j++) cnt[i][j]++; for(int j = 0; j < i; j++) cnt[j][i]++; break; } } } if(s == 1) sk = 'a'; int cur = 0; string ans = ""; for(int cur = 0; cur < sk.size(); cur++){ string fh = "", sh = ""; for(int i = 0; i < cur; i++) fh += sk[i]; for(int i = cur + 1; i < sk.size(); i++) sh += sk[i]; int l = 1, r = n - fh.size() - sh.size(); while(l <= r){ int mid = (l + r) / 2; string tmp; tmp += fh; for(int i = 0; i < mid; i++) tmp += sk[cur]; tmp += sh; if(tmp.size() > n) return sk; int a = query(tmp); if(a != tmp.size()) r = mid - 1; else l = mid + 1; } for(int i = 0; i < l - 1; i++) ans += sk[cur]; } return ans; } // int main() { // cin >> n >> s >> password; // string answer = guess(n, s); // if (DEBUG) { // cout << "Your answer: [" << answer << "]\n"; // } // if (answer.compare(password)) { // msg << "Your answer was [" << answer // << "] which does not match the password [" << password << "]."; // end(0); // } else { // msg << "You guessed the password with " << numQueries << " queries."; // end(1); // } // return 0; // }