#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
int dp[255][255][255];
int go(int known_a, int known_b, int qcnt);
pair<int,int> max_val(int known_a, int known_b, int qcnt) {
int v = 0, operation = 2;
// A.A.(...)
// B.B.(...)
for (int i : {2, known_a}) {
if (i > known_a)
continue;
int opt = inf;
for (int b = 0; b < 2 && opt > v; b++) {
if (i == 2) {
for (int a = 0; a < 2 && opt > v; a++)
opt = min(opt, i + go(known_a + (b ^ 1) + a, known_b + b + (a ^ 1), qcnt - 1));
} else {
opt = min(opt, i + go(known_a + (b ^ 1), known_b + b, qcnt - 1));
}
}
if (opt > v) {
v = opt;
operation = i == 2 ? 1 : 2;
}
}
int ok = 1;
// 000001111100
if (qcnt > 3) {
int cnt = 12, qry = 4;
if (known_a >= 7 && known_b >= 5) {
int opt = inf;
for (int a = 0; a <= cnt && opt > v; a++) {
if (qcnt > qry && cnt + known_b <= known_a && a != 0)
break;
int b = cnt - a;
opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
}
if (opt > v) {
v = opt;
operation = 3;
}
ok = 0;
}
}
// 00011
if (qcnt > 1) {
int cnt = 5, qry = 2;
if (known_a >= 3 && known_b >= 2) {
int opt = inf;
for (int a = 0; a <= cnt; a++) {
if (qcnt > qry && cnt + known_b <= known_a && a != 0)
break;
int b = cnt - a;
opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
}
if (opt > v) {
v = opt;
operation = 4;
}
}
}
// 000
if (qcnt > 1) {
int cnt = 3, qry = 2;
if (known_a >= 3 && known_b >= 0) {
int opt = inf;
for (int a = 0; a <= cnt; a++) {
if (qcnt > qry && cnt + known_b <= known_a && a != 0)
break;
int b = cnt - a;
opt = min(opt, cnt + go(known_a + a, known_b + b, qcnt - qry));
}
if (opt > v) {
v = opt;
operation = 5;
}
}
}
return make_pair(v, operation);
}
int go(int known_a, int known_b, int qcnt) {
if (known_b > known_a)
swap(known_a, known_b);
if (qcnt == 0)
return 0;
if (known_a > 250)
return -inf;
if (~dp[known_a][known_b][qcnt])
return dp[known_a][known_b][qcnt];
int v = max_val(known_a, known_b, qcnt).first;
return dp[known_a][known_b][qcnt] = v;
}
vector<int> ind_a, ind_b;
int cnt_a = 0, cnt_b = 0;
void flip(int fl) {
if (fl) {
swap(ind_a, ind_b);
swap(cnt_a, cnt_b);
}
}
void askA(vector<int>& x) {
int len = int(x.size());
assert(int(ind_a.size()) >= len);
vector<int> cur;
for (int i = 0; i < len; i++)
cur.push_back(ind_a[i]), cur.push_back(x[i]);
int ret = use_machine(cur);
if (ret & 1) {
ind_b.push_back(x.back());
cnt_b++, ret--, len--;
} else {
ind_a.push_back(x.back());
cnt_a++, len--;
}
cnt_b += ret / 2;
cnt_a += len - (ret / 2);
if (ret == 0) {
for (int i = 0; i < len; i++)
ind_a.push_back(x[i]);
} else if (ret == len * 2) {
for (int i = 0; i < len; i++)
ind_b.push_back(x[i]);
}
}
struct op3 {
static const int qcnt = 4, len = 12;
inline static vector<int> ord[qcnt] = {
{8, 0, 9, 10, 7, 11, 5, 1, 6, 4, 2, 3},
{3, 8, 4, 2, 1, 11, 5, 10, 6, 0, 9, 7},
{5, 7, 10, 1, 9, 3, 8, 6, 2, 11, 4, 0},
{2, 3, 11, 4, 6, 1, 9, 8, 7, 0, 5, 10}
};
inline static vector<int> msk = {0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0};
inline static map<array<int,qcnt>,int> rev;
};
struct op4 {
static const int qcnt = 2, len = 5;
inline static vector<int> ord[qcnt] = {
{2, 3, 1, 0, 4},
{1, 2, 0, 4, 3}
};
inline static vector<int> msk = {1, 1, 0, 0, 0};
inline static map<array<int,qcnt>,int> rev;
};
struct op5 {
static const int qcnt = 2, len = 3;
inline static vector<int> ord[qcnt] = {
{0, 1, 2},
{1, 2, 0}
};
inline static vector<int> msk = {0, 0, 0};
inline static map<array<int,qcnt>,int> rev;
};
template<class op> void ask(int mx_unused, int n, int& qcnt) {
vector<int> x;
for (int i = 0; i < op::len && mx_unused + i < n; i++)
x.push_back(mx_unused + i);
if (int(x.size()) != op::len) {
askA(x);
qcnt--;
return;
}
assert(int(x.size()) == op::len);
int fl = int(ind_a.size()) < int(ind_b.size());
flip(fl);
array<int,op::qcnt> arr;
for (int i = 0; i < op::qcnt; i++) {
vector<int> x_ord;
for (int j = 0, ja = 0, jb = 0; j < op::len; j++) {
x_ord.push_back(op::msk[j] == 0 ? ind_a[ja++] : ind_b[jb++]);
x_ord.push_back(x[op::ord[i][j]]);
}
arr[i] = use_machine(x_ord);
}
int ans = op::rev[arr];
cnt_b += __builtin_popcount(ans);
cnt_a += op::len - __builtin_popcount(ans);
for (int i = 0; i < op::len; i++)
if ((ans >> i) & 1)
ind_b.push_back(x[i]);
else
ind_a.push_back(x[i]);
flip(fl);
qcnt -= op::qcnt;
}
template<class op> void upd() {
auto eval = [&](vector<int>& a, vector<int>& b) {
assert(int(a.size()) == int(b.size()));
int r = 0;
for (int i = 0, j = int(a.size()); i < j; i++)
r += int(a[i] != b[i]) + int(i + 1 != j ? b[i] != a[i+1] : 0);
return r;
};
for (int msk = 0; msk < (1 << op::len); msk++) {
array<int,op::qcnt> arr;
for (int it = 0; it < op::qcnt; it++) {
vector<int> ord;
for (int j = 0; j < op::len; j++)
ord.push_back((msk >> op::ord[it][j]) & 1);
arr[it] = eval(op::msk, ord);
}
op::rev[arr] = msk;
}
}
void build() {
upd<op3>();
upd<op4>();
upd<op5>();
}
void solve(int known_a, int known_b, int qcnt, int n) {
assert(qcnt >= 0);
int mx_unused = cnt_a + cnt_b;
if (mx_unused >= n)
return;
int fl = int(known_a < known_b);
if (fl)
swap(known_a, known_b);
flip(fl);
int operation = max_val(known_a, known_b, qcnt).second;
vector<int> x;
switch (operation) {
case 1: {
for (int i = 0; i < 2 && mx_unused + i < n; i++)
x.push_back(mx_unused + i);
askA(x);
qcnt--;
break;
}
case 2: {
for (int i = 0; i < known_a && mx_unused + i < n; i++)
x.push_back(mx_unused + i);
askA(x);
qcnt--;
break;
}
case 3: {
ask<op3>(mx_unused, n, qcnt);
break;
}
case 4: {
ask<op4>(mx_unused, n, qcnt);
break;
}
case 5: {
ask<op5>(mx_unused, n, qcnt);
break;
}
}
flip(fl);
solve(int(ind_a.size()), int(ind_b.size()), qcnt, n);
}
int count_mushrooms(int n) {
memset(dp, -1, sizeof dp);
go(1, 0, 213);
build();
ind_a.push_back(0);
cnt_a = 1;
solve(1, 0, 213, n);
return cnt_a;
}
