#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int N, P = 1, ans = 1;
vector <int> A[2];
void pre() {
if (A[0].size() >= 3) {
int c = use_machine({P,0,P+1,A[0][1],P+2,A[0][2]});
A[c&1].push_back(P);
if (c < 2) {
A[0].push_back(P+1);
A[0].push_back(P+2);
}
else if (c > 3) {
A[1].push_back(P+1);
A[1].push_back(P+2);
}
else if (A[1].size() >= 2) {
c = use_machine({A[1][0],P+1,A[1][1],A[0][0],P+2,A[0][1],P+3,A[0][2],P+4}) - 1;
A[~c>>2&1].push_back(P+1);
A[c>>2&1].push_back(P+2);
A[c>>1&1].push_back(P+3);
A[c&1].push_back(P+4);
P+=2;
}
else {
c = use_machine({P+1,0,P+2,A[0][1],P+3,A[0][2]});
A[c&1].push_back(P+1);
A[~c&1].push_back(P+2);
A[c>2].push_back(P+3);
P++;
}
P+=3;
return;
}
if (A[1].size() >= 3) {
int c = use_machine({P,A[1][0],P+1,A[1][1],P+2,A[1][2]});
A[~c&1].push_back(P);
if (c < 2) {
A[1].push_back(P+1);
A[1].push_back(P+2);
}
else if (c > 3) {
A[0].push_back(P+1);
A[0].push_back(P+2);
}
else if (A[0].size() >= 2) {
c = use_machine({A[0][0],P+1,A[0][1],A[1][0],P+2,A[1][1],P+3,A[1][2],P+4}) - 1;
A[c>>2&1].push_back(P+1);
A[~c>>2&1].push_back(P+2);
A[~c>>1&1].push_back(P+3);
A[~c&1].push_back(P+4);
P+=2;
}
else {
c = use_machine({P+1,A[1][0],P+2,A[1][1],P+3,A[1][2]});
A[~c&1].push_back(P+1);
A[c&1].push_back(P+2);
A[c<3].push_back(P+3);
P++;
}
P+=3;
return;
}
if (A[0].size() >= 2) {
int c = use_machine({P,0,P+1,A[0][1]});
A[c&1].push_back(P);
A[c>>1&1].push_back(P+1);
P+=2;
return;
}
if (A[1].size() >= 2) {
int c = use_machine({P,A[1][0],P+1,A[1][1]});
A[~c&1].push_back(P);
A[~c>>1&1].push_back(P+1);
P+=2;
return;
}
int c = use_machine({P,0});
A[c].push_back(P);
P++;
return;
}
int count_mushrooms(int n) {
N = n;
A[0].push_back(0);
if (N > 10000) {
while (P < 200) {
pre();
}
ans = A[0].size();
}
while (P < N) {
if (A[0].size() > A[1].size()) {
vector <int> m;
for (int x : A[0]) {
m.push_back(P);
m.push_back(x);
P++;
if (P == N) {
break;
}
}
int c = use_machine(m);
ans += m.size()/2 - (c+1)/2;
A[c&1].push_back(m[0]);
}
else {
vector <int> m;
for (int x : A[1]) {
m.push_back(P);
m.push_back(x);
P++;
if (P == N) {
break;
}
}
int c = use_machine(m);
ans += (c+1)/2;
A[~c&1].push_back(m[0]);
}
}
return ans;
}
