#include<bits/stdc++.h>
#include "combo.h"
using namespace std;
#define debug(x) cerr << #x << " = " << (x) << endl
vector<vector<int>> possible;
char chars[4] = {'A', 'B', 'X', 'Y'};
map<char, int> charsinv;
string guess_sequence(int n) {
charsinv.insert({'A', 0});
charsinv.insert({'B', 1});
charsinv.insert({'X', 2});
charsinv.insert({'Y', 3});
vector<int> res;
int init;
possible = vector<vector<int>>(n);
fill(possible.begin(), possible.end(), vector<int> { 1, 1, 1, 1 });
if (press("AB")) {
init = press("A") ? 0 : 1;
} else {
init = press("X") ? 2 : 3;
}
res.push_back(init);
vector<char> others;
for (int i = 0; i < 4; i++) {
if (i == init) continue;
others.push_back(i);
}
for (int i = 0; i < n; i++) {
possible[i][init] = 0;
}
while (true) {
bool done = true;
for (int i = 0; i < n-1; i++) {
if (accumulate(possible[i].begin(), possible[i].end(), 0) > 1) {
done = false;
break;
}
}
if (done) break;
vector<string> queries = { string(1, chars[init]) };
int i = 0;
int size = 0;
// while (2 * queries.size() * (queries[0].size() + 1) <= 4 * n && i + 1 < n) {
while (i + 1 < n) {
// debug(queries[0].size());
vector<string> queries_next;
int choice_1 = init;
while (!possible[i][choice_1]) choice_1 = rand() % 4;
int choice_2 = init;
while (!possible[i][choice_2]) choice_2 = rand() % 4;
for (string &query : queries) {
int num_possible = accumulate(possible[i].begin(), possible[i].end(), 0);
if (num_possible == 3) {
queries_next.push_back(query + chars[choice_1]);
queries_next.push_back(query + chars[choice_2]);
} else {
queries_next.push_back(query + chars[choice_1]);
}
}
int size = 0;
for (auto &q : queries_next) size += q.size();
if (size > 4 * n) {
break;
}
queries = queries_next;
i++;
}
string query = "";
vector<vector<int>> possible_q(n);
fill(possible_q.begin(), possible_q.end(), vector<int> { 0, 0, 0, 0 });
for (string q : queries) {
query += q;
for (int i = 0; i < q.size(); i++) {
if (q[i] == chars[init]) continue;
possible_q[i-1][charsinv[q[i]]] = 1;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < 4; j++) {
// cerr << possible_q[i][j];
// }
// cerr << " ";
// };
// cerr << endl;
// debug(query.size());
// debug(query);
int coins = press(query);
// debug(coins);
for (int i = 0; i < coins - 2; i++) {
for (int j = 0; j < 4; j++) {
possible[i][j] = possible[i][j] && possible_q[i][j];
}
}
for (int j = 0; j < 4; j++) {
possible[coins-1][j] = possible[coins-1][j] && !possible_q[coins-1][j];
}
// cerr << "possible: ";
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < 4; j++) {
// cerr << possible[i][j];
// }
// cerr << " ";
// };
// cerr << endl;
}
string ans = "";
ans += chars[init];
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < 4; j++) {
if (possible[i][j]) ans += chars[j];
}
}
return ans;
}
// we can cross out possible characters in parallel
// check first two chars for i and i + 1
// i has 111 and i+1 has 111
// try 110, 110
// if +2: i <- 110, b <- 110
// if +1: i <- 110, b <- 001
// if +0: i <- 001, b <- 111
// i has 111 and i+1 has 111
// try 100, 100
// if +2: i <- 100, b <- 100
// if +1: i <- 100, b <- 011
// if +0: i <- 011, b <- 111
// i has 110 and i+1 has 110
// try 100, 100
// if +2: i <- 100, b <- 100
// if +1: i <- 100, b <- 010
// if +0: i <- 010
// i has 110 and i+1 has 110 and i+2 has 111
// try 100, 100, 110
// if +3: i <- 100, i+1 <- 100, i+2 <- 110
// if +2: i <- 100, i+1 <- 100, i+2 <- 001
// if +1: i <- 100, i+1 <- 010
// if +0: i <- 010
// we need to cross out 2*n characters in total
// so we just need to always cross out at least two characters with each query
// problem is when we have 110, 110
// maybe we cross out more than two at the start?
// a has 111, b has 111, c has 111
// try 110, 110, 110
// if +3: a <- 110, b <- 110, c <- 110
// if +2: a <- 110, b <- 110, c <- 001
// if +1: a <- 110, b <- 001
// if +0: a <- 001
// P(+3) = 2/3 * 2/3 * 2/3
// P(+2) = 2/3 * 2/3 * 1/3
// P(+1) = 2/3 * 1/3
// P(+0) = 1/3
// C(n) = 2 + n
// P(n) = 1/3 * (2/3)^n
// M(n) = P(0) * C(0) + P(1) * C(1) + ... + P(n-1) * C(n-1) + 3 * P(n) * (C(n) - 2)
// M(n) - 3 * P(n) * (C(n) - 2)
// y = sum a^n
// a * y = sum a^(n+1) = y + a^(n+1) - a^0
// a * y - y = a^(n+1) - a^0
// y * (a - 1) = a^(n+1) - a^0
// y = (a^(n+1) - 1) / (a - 1)
// for 111, 111, 111, ...
// M(n) - 3 * P(n) * (C(n) - 2) > 3n
// M(n) > 3n + 3 * P(n) * (C(n) - 2) = 3n + n * (2/3)^n
// M(n) > 3n
// m * 2^l = 8000
// 2^l = 8000 / m
// l = log2(8000 / m)
// if m = 1 we have l = 12
// afaik we can reduce to only 110s very fast
// with randomized algorithm :)
// for 110, 110, 110, ...
// possible in at most O(n) queries
