#include<bits/stdc++.h>
#include "combo.h"
#define str string
using namespace std;
// note that we don't have to press a string of length exactly 4N, instead 4N is the maximum length of the pressed string
set<char> C;
char c[3];
str guess_sequence(int N) {
str p = "";
C.insert('A');
C.insert('B');
C.insert('X');
C.insert('Y');
// firstly, there are 4 options for the first character (A, B, X, Y)
// the most optimal way to get the first character is to press "AB"
// if we get coins >= 1, then the first character is 'A' or 'B'
// similarly the first character is 'X' or 'Y' if we get 0 coins
int Q1 = press("AB"), Q2;
if (Q1 > 0) {
Q2 = press("A");
if (Q2 > 0) {
p += 'A';
C.erase('A');
}
else {
p += 'B';
C.erase('B');
}
}
else {
Q2 = press("X");
if (Q2 > 0) {
p += 'X';
C.erase('X');
}
else {
p += 'Y';
C.erase('Y');
}
}
// NOTE that the first character will not appear again later in S
// for the next n-2 characters we use the following format as a strategy
// let P be the already known/fixed prefix
// p = PXXPXAPXBPA
// p = PC[0]C[0]PC[0]C[1]PC[0]C[2]PC[1]
char c[3];
int idx = 0;
for (char j: C) {
c[idx] = j;
idx++;
}
for (int i=1; i<N; i++) {
int Qmid = press(p+c[0]+c[0]+p+c[0]+c[1]+p+c[0]+c[2]+p+c[1]);
if (Qmid == i) {
// then the next char is c[2]
p += c[2];
continue;
}
else if (Qmid == i+1) {
// ... next char is c[1]
p += c[1];
continue;
}
else {
// ... next char is c[0]
p += c[0];
continue;
}
if (i == N-1) break;
}
// so far we've pressed 2 + n-2 = n times
// 2 presses left
int Qlast1 = press(p+c[0]);
int Qlast2 = press(p+c[1]);
if (Qlast1 == N) p += c[0];
else if (Qlast2 == N) p += c[1];
else p += c[2];
str S = "";
for (int i = 0; i < N; ++i) {
S += p[0];
}
return S;
}
