#ifndef COMBO_CPP_INCLUDED
#define COMBO_CPP_INCLUDED
#include "combo.h"
#include <vector>
#include <cassert>
#include <iostream>
std::string str = "";
int NNN;
std::string get(std::vector<std::string> v) {
if ((int) v.size() == 1) {
return v[0];
}
int n = (int) v.size();
std::vector<std::string> lt, rt;
for (int i = 0; i < n / 2; i++) {
lt.push_back(v[i]);
}
for (int i = n / 2; i < n; i++) {
rt.push_back(v[i]);
}
std::string ask = "";
for (const auto &s : lt) {
ask += str + s;
}
assert((int) ask.size() <= 4 * NNN);
if (press(ask) == (int) str.size() + (int) lt[0].size()) {
return get(lt);
} else {
return get(rt);
}
}
std::string guess_sequence(int n) {
NNN = n;
std::vector<std::string> alphabet = {"A", "B", "X", "Y"};
std::string first = "";
for (int i = 0; i < 3; i++) {
if (press(alphabet[i])) {
first = alphabet[i];
break;
}
}
if (first.empty()) {
first = alphabet.back();
}
int ptr = 0;
while (alphabet[ptr] != first) {
ptr++;
}
alphabet.erase(alphabet.begin() + ptr);
str += first;
for (int i = 1; i < n;) {
if (((int) str.size() + 3) * 13 <= 4 * n) { /// floor(3^3 / 2) = 13
std::vector<std::string> cand;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
cand.push_back(alphabet[i] + alphabet[j] + alphabet[k]);
}
}
}
str += get(cand);
i += 3;
} else if (((int) str.size() + 2) * 4 <= 4 * n) { /// floor(3^3 / 2) = 4
std::vector<std::string> cand;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cand.push_back(alphabet[i] + alphabet[j]);
}
}
str += get(cand);
i += 2;
} else {
std::vector<std::string> cand;
for (int i = 0; i < 3; i++) {
cand.push_back(alphabet[i]);
}
str += get(cand);
i++;
}
}
// std::cout << "! " << str << '\n';
return str;
}
#endif // COMBO_CPP_INCLUDED
