#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int count_mushrooms(int n) {
vector<int> s[8], q1 = {0, 1, 5, 2, 6, 3, 7, 4}, q2[8];
map<int, int> mp[8];
for(int mask = 0; mask < 32; mask++) {
vector<int> a(9);
a[8] = 1;
for(int i = 0; i < 5; i++)
a[i] = mask >> i & 1;
int sum = 0;
for(int i = 1; i < 8; i++)
sum += a[q1[i - 1]] ^ a[q1[i]];
s[sum].push_back(mask);
}
for(int i = 0; i < 8; i++){
vector<int> p(9);
iota(p.begin(), p.end(), 0);
bool ok = 0;
do {
map<int, int> sums;
for(int mask : s[i]) {
vector<int> a(9, 0);
a[8] = 1;
for(int i = 0; i < 5; i++)
a[i] = mask >> i & 1;
int sum = 0;
for(int i = 1; i < 9; i++)
sum += a[p[i - 1]] ^ a[p[i]];
sums[sum] = mask;
}
if (s[i].size() == sums.size()) {
ok = 1;
q2[i] = p;
mp[i] = sums;
break;
}
} while (next_permutation(p.begin(), p.end()));
assert(ok);
}
vector<int> type[2];
type[0].push_back(0);
int flag = 0, cur = 1, k = 220, cnt[2] = {0, 0};
while (cur < n) {
if (type[0].size() < type[1].size()) {
flag ^= 1;
swap(type[0], type[1]);
swap(cnt[0], cnt[1]);
}
if ((int) cur < k) {
int num = min(5, n - cur);
if (num < 5 || (int) type[0].size() < 3 || (int) type[1].size() < 1) {
num = min(num, min(2, (int) type[0].size()));
vector<int> a;
for(int i = 0; i < num; i++) {
a.push_back(cur + i);
a.push_back(type[0][i]);
}
int x = use_machine(a);
for(int i = 0; i < num; i++)
type[(x >> i) & 1].push_back(cur + i);
cur += num;
} else {
vector<int> pos;
for(int i = 0; i < 5; i++)
pos.push_back(cur + i);
for(int i = 0; i < 3; i++)
pos.push_back(type[0][i]);
pos.push_back(type[1][0]);
vector<int> a;
for(int x : q1)
a.push_back(pos[x]);
int res = use_machine(a);
a.clear();
for(int x : q2[res])
a.push_back(pos[x]);
int mask = mp[res][use_machine(a)];
for(int i = 0; i < 5; i++)
type[(mask >> i) & 1].push_back(cur + i);
cur += num;
}
} else {
int num = min(n - cur, (int) type[0].size());
vector<int> a;
for(int i = 0; i < num; i++) {
a.push_back(cur + i);
a.push_back(type[0][i]);
}
int x = use_machine(a);
type[x & 1].push_back(cur);
cnt[1] += x / 2;
cnt[0] += (num - 1) - x / 2;
cur += num;
}
}
if (flag) {
flag ^= 1;
swap(type[0], type[1]);
swap(cnt[0], cnt[1]);
}
return cnt[0] + type[0].size();
}
