/* https://ioi2020.sg/wp-content/uploads/sites/4/2020/09/mushrooms-solutions-ISC.pdf */
#include "mushrooms.h"
#include <ctype.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef vector<int> vi;
const int N = 20000, K = 45, C = 5, B = 1 << C, Q = 3, M = 171903, L = 10, T = 2 * L * L * L;
int queries(int k) {
int q = k * 2 + 1, n = k * C + 1;
while (n < N) {
n += (k * C + 1 + q - (k * 2 + 1) + 1) / 2;
q++;
}
return q;
}
void print_K() {
int k;
for (k = 1; k * C <= N; k++)
if (queries(k) <= 226)
printf("%d: %d\n", k, queries(k));
}
char ss[M][L + 1], cc[L + 1]; int ll[M], m;
void generate_(int b, int x, int y, int l) {
int i;
if (l > 0)
strcpy(ss[m], cc), ll[m] = l, m++;
for (i = 0; i < C; i++)
if ((b & 1 << i) != 0)
cc[l] = i + 'A', generate_(b ^ 1 << i, x, y, l + 1);
if (x > 0)
cc[l] = '0', generate_(b, x - 1, y, l + 1);
if (y > 0)
cc[l] = '1', generate_(b, x, y - 1, l + 1);
cc[l] = 0;
}
int use_machine_(int h, int b) {
int i, cnt;
cnt = 0;
for (i = 0; i + 1 < ll[h]; i++) {
int x = isdigit(ss[h][i]) ? ss[h][i] - '0' : b >> ss[h][i] - 'A' & 1;
int y = isdigit(ss[h][i + 1]) ? ss[h][i + 1] - '0' : b >> ss[h][i + 1] - 'A' & 1;
if (x != y)
cnt++;
}
return cnt;
}
int branch(char ss_[][L + 1], int t, int q, long long mask) {
static long long masks[Q + 1][L];
int h, i, b, k;
if (mask == 0) {
ss_[t][0] = 0;
return 1;
}
if ((mask & mask - 1) == 0) {
for (b = 0; b < B; b++)
if ((mask & 1LL << b) != 0) {
ss_[t][0] = '[', ss_[t][C + 1] = ']', ss_[t][C + 2] = 0;
for (i = 0; i < C; i++)
ss_[t][i + 1] = (b >> i & 1) + '0';
break;
}
return 1;
}
if (q == 0)
return 0;
for (h = 0; h < m; h++) {
int good;
if (q == 3 && ll[h] != 6)
continue;
memset(masks[q], 0, L * sizeof *masks[q]);
for (b = 0; b < B; b++)
if ((mask & 1LL << b) != 0)
masks[q][use_machine_(h, b)] |= 1LL << b;
good = 1;
for (k = 0; k < L; k++)
if (!branch(ss_, t * L + k, q - 1, masks[q][k])) {
good = 0;
break;
}
if (good) {
strcpy(ss_[t], ss[h]);
return 1;
}
}
return 0;
}
void print(char ss_[][L + 1], int t) {
int k;
if (ss_[t][0] == 0)
return;
printf("%d: %s\n", t, ss_[t]);
if (ss_[t][0] == '[')
return;
for (k = 0; k < L; k++)
print(ss_, t * L + k);
}
char ss103[T][L + 1];
void build103() {
m = 0, generate_(B - 1, 1, 0, 0);
branch(ss103, 1, 3, (1LL << 32) - 1);
#if 0
print(ss103, 1);
#endif
}
char ss212[T][L + 1];
void build212() {
#if 0
m = 0, generate_(B - 1, 3, 1, 0);
branch(ss212, 1, 2, (1LL << 32) - 1);
print(ss212, 1);
#else
strcpy(ss212[1], "ABC0D0E");
strcpy(ss212[10], "[00000]");
strcpy(ss212[11], "AB1C");
strcpy(ss212[110], "[11100]");
strcpy(ss212[111], "[11000]");
strcpy(ss212[112], "[00001]");
strcpy(ss212[113], "[10000]");
strcpy(ss212[12], "A0B0ED1C");
strcpy(ss212[121], "[00100]");
strcpy(ss212[122], "[00010]");
strcpy(ss212[123], "[01100]");
strcpy(ss212[124], "[01000]");
strcpy(ss212[125], "[10001]");
strcpy(ss212[126], "[11101]");
strcpy(ss212[127], "[11001]");
strcpy(ss212[13], "BE10A0D0C");
strcpy(ss212[131], "[01001]");
strcpy(ss212[132], "[01101]");
strcpy(ss212[133], "[00101]");
strcpy(ss212[134], "[00011]");
strcpy(ss212[135], "[10100]");
strcpy(ss212[136], "[10010]");
strcpy(ss212[137], "[11010]");
strcpy(ss212[138], "[11110]");
strcpy(ss212[14], "A0E0DC1B");
strcpy(ss212[141], "[01110]");
strcpy(ss212[142], "[00110]");
strcpy(ss212[143], "[01010]");
strcpy(ss212[144], "[11111]");
strcpy(ss212[145], "[10101]");
strcpy(ss212[146], "[11011]");
strcpy(ss212[147], "[10011]");
strcpy(ss212[15], "AB0DC");
strcpy(ss212[151], "[00111]");
strcpy(ss212[152], "[10110]");
strcpy(ss212[153], "[01111]");
strcpy(ss212[154], "[01011]");
strcpy(ss212[16], "[10111]");
#endif
}
vi ii; int ii0[N], ii1[N], n0, n1;
void solve(char ss_[][L + 1], int i, int flip) {
int t = 1;
while (1)
if (ss_[t][0] == '[') {
for (i = 0; i < 5; i++)
if ((ss_[t][i + 1] - '0' ^ flip) == 0)
ii0[n0++] = i;
else
ii1[n1++] = i;
return;
} else {
int l = strlen(ss_[t]), h, h0, h1;
ii.resize(l);
for (h = 0, h0 = 0, h1 = 0; h < l; h++)
if (isdigit(ss_[t][h]))
ii[h] = (ss_[t][h] - '0' ^ flip) == 0 ? ii0[h0++] : ii1[h1++];
else
ii[h] = i * 5 + ss_[t][h] - 'A' + 1;
t = t * L + (l <= 1 ? 0 : use_machine(ii));
}
}
int count_mushrooms(int n) {
int n_, h, i, k, ans;
build103(), build212();
if (n < K * 5 + 1) {
ans = n;
for (i = 1; i < n; i++)
ii.resize(2), ii[0] = 0, ii[1] = i, ans -= use_machine(ii);
} else {
ii0[n0++] = 0;
for (i = 0; i < K; i++)
if (n1 == 0)
solve(ss103, i, 0);
else
solve(ss212, i, n0 >= 3 ? 0 : 1);
i = K * 5 + 1;
ans = n0;
while (i < n)
if (n0 > n1) {
ii.resize(0);
for (h = 0; h < n0; h++) {
ii.push_back(ii0[h]);
if (i < n)
ii.push_back(i++);
}
n_ = ii.size();
k = use_machine(ii);
if (n_ == n0 * 2) {
if (k % 2 == 1)
ii1[n1++] = ii[--n_], k--;
else
ii0[n0++] = ii[n_ - 1], ans++;
}
ans += n_ - n0 - k / 2;
} else {
ii.resize(0);
for (h = 0; h < n1; h++) {
ii.push_back(ii1[h]);
if (i < n)
ii.push_back(i++);
}
n_ = ii.size();
k = use_machine(ii);
if (n_ == n1 * 2) {
if (k % 2 == 1)
ii0[n0++] = ii[--n_], ans++, k--;
else
ii1[n1++] = ii[n_ - 1];
}
ans += k / 2;
}
}
return ans;
}
