// Problem URL: https://oj.uz/problem/view/IOI18_combo
// Start Time: 5/22/2025, 1:37:39 PM
#include <bits/stdc++.h>
#include "combo.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int i = a; i < b; i++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
string guess_sequence(int n)
{
vector<char> abc = {'A','B','X','Y'};
/* ---- 1. find the first letter ---- */
int r = press("AB"); // 0, 1 or 2
char first;
if (r) { // it's A or B
first = press("A") ? 'A' : 'B';
} else { // it's X or Y
first = press("X") ? 'X' : 'Y';
}
string pref(1, first);
/* keep the three letters that can still appear */
vector<char> rest;
for (char c : abc) if (c != first) rest.push_back(c);
const char p = rest[0]; // old “A”
const char q = rest[1]; // sentinel, old “Y”
const char r_ = rest[2]; // old “B”
/* ---- 2. build positions 2 … n-1 ---- */
for (int i = 1; i < n - 1; ++i) {
string qstr;
qstr.reserve((i + 1) * 4 + 3); // small perf tweak
qstr += pref; qstr.push_back(p);
qstr += pref; qstr.push_back(q); qstr.push_back(q);
qstr += pref; qstr.push_back(q); qstr.push_back(p);
qstr += pref; qstr.push_back(q); qstr.push_back(r_);
int k = press(qstr);
if (k == pref.size() + 1) pref.push_back(p);
else if (k == pref.size() + 2) pref.push_back(r_);
else pref.push_back(q);
}
if (n == 1) return pref; // nothing else to do
/* ---- 3. resolve the very last character ---- */
string try1 = pref + q + pref + p; // ...q...p
int k = press(try1);
if (k == n - 1) { // mismatch at last char
pref.push_back(r_);
} else { // could be q or p
pref.push_back(press(pref + q) == n ? q : p);
}
return pref;
}
// string guess_sequence(int n){
// string pref = "X";
// // guess first letter
// int res = press("XY");
// switch (res)
// {
// case 1:
// res = press("XA");
// if(!res) pref = "Y";
// break;
// case 0:
// pref="A";
// res = press("AX");
// if(!res) pref = "B";
// break;
// default:
// break;
// }
// li(i,1,n-1){
// stringstream q;
// q << pref << "A" << pref << "YY" << pref <<"YA"<<pref<<"YB";
// res = press(q.str());
// if(res==i+1){
// pref.append("B");
// }
// else if(res == i+2){
// pref.append("A");
// }
// else{
// pref.append("Y");
// }
// }
// stringstream q;
// q << pref <<"Y"<<pref<<"A";
// res = press(q.str());
// if(res==n-1){
// pref.append("B");
// }
// else{
// q.clear();
// q << pref <<"Y";
// res = press(q.str());
// if(res == n){
// pref.append("Y");
// }
// else{
// pref.append("A");
// }
// }
// return pref;
// }
