#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) lt.size() <= (int) rt.size());
assert((int) ask.size() <= 4 * NNN);
if (press(ask) == (int) str.size() + (int) lt[0].size()) {
return get(lt);
} else {
return get(rt);
}
}
std::vector<std::string> bkt(std::vector<std::string> alphabet, int len) {
if (len == 1) {
return alphabet;
}
std::vector<std::string> ret;
std::vector<std::string> aux = bkt(alphabet, len - 1);
for (int i = 0; i < (int) alphabet.size(); i++) {
for (const auto &q : aux) {
ret.push_back(alphabet[i] + q);
}
}
return ret;
}
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++;
}
int p3[8] = {};
p3[0] = 1;
for (int i = 1; i < 8; i++) {
p3[i] = 3 * p3[i - 1];
}
alphabet.erase(alphabet.begin() + ptr);
str += first;
for (int i = 1; i < n;) {
for (int len = 7; len > 0; len--) {
if ((long long) ((int) str.size() + len) * (p3[len] / 2) > 4 * n) {
continue;
}
std::vector<std::string> cand = bkt(alphabet, len);
str += get(cand);
i += len;
break;
}
}
return str;
}
#endif // COMBO_CPP_INCLUDED
