#include "mushrooms.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> a[2];
int ans = 0, nw = 1;
vector<int> m;
void ZER(){
m.pb(a[0][0]); m.pb(nw++); m.pb(a[0][1]); m.pb(nw++);
int ret = use_machine(m);
if((ret>>1) & 1) a[1].pb(nw-2);
else a[0].pb(nw-2);
if(ret & 1) a[1].pb(nw-1);
else a[0].pb(nw-1);
}
void ONE(){
m.pb(a[1][0]); m.pb(nw++); m.pb(a[1][1]); m.pb(nw++);
int ret = use_machine(m);
if((ret>>1) & 1) a[0].pb(nw-2);
else a[1].pb(nw-2);
if(ret & 1) a[0].pb(nw-1);
else a[1].pb(nw-1);
}
void pre(){
while(nw <= 200){
m.clear();
// cout << nw << " nw\n";
if(a[0].size() >= 3){
m.pb(nw++); m.pb(a[0][0]); m.pb(nw++); m.pb(a[0][1]); m.pb(nw++); m.pb(a[0][2]);
int ret = use_machine(m);
if(ret & 1) a[1].pb(nw-3);
else a[0].pb(nw-3);
if(ret >= 4) a[1].pb(nw-1), a[1].pb(nw-2);
else if(ret <= 1) a[0].pb(nw-1), a[0].pb(nw-2);
else {
m.clear();
if(a[1].size() >= 2){
m.pb(a[1][0]); m.pb(nw-2); m.pb(a[1][1]);
m.pb(a[0][0]); m.pb(nw-1); m.pb(a[0][1]); m.pb(nw++); m.pb(a[0][2]); m.pb(nw++);
int ret = use_machine(m)-1;
if(ret & 1) a[1].pb(nw-1);
else a[0].pb(nw-1);
if((ret>>1) & 1) a[1].pb(nw-2);
else a[0].pb(nw-2);
if((ret>>2) & 1) a[1].pb(nw-3), a[0].pb(nw-4);
else a[0].pb(nw-3), a[1].pb(nw-4);
} else {
nw -= 2;
ZER();
}
}
} else if(a[1].size() >= 3){
m.pb(nw++); m.pb(a[1][0]); m.pb(nw++); m.pb(a[1][1]); m.pb(nw++); m.pb(a[1][2]);
int ret = use_machine(m);
if(ret & 1) a[0].pb(nw-3);
else a[1].pb(nw-3);
if(ret >= 4) a[0].pb(nw-1), a[0].pb(nw-2);
else if(ret <= 1) a[1].pb(nw-1), a[1].pb(nw-2);
else {
m.clear();
if(a[0].size() >= 2){
m.pb(a[0][0]); m.pb(nw-2); m.pb(a[0][1]);
m.pb(a[1][0]); m.pb(nw-1); m.pb(a[1][1]); m.pb(nw++); m.pb(a[1][2]); m.pb(nw++);
int ret = use_machine(m)-1;
if(ret & 1) a[0].pb(nw-1);
else a[1].pb(nw-1);
if((ret>>1) & 1) a[0].pb(nw-2);
else a[1].pb(nw-2);
if((ret>>2) & 1) a[0].pb(nw-3), a[1].pb(nw-4);
else a[1].pb(nw-3), a[0].pb(nw-4);
} else {
nw -= 2;
ZER();
}
}
} else if(a[0].size() >= 2){
ZER();
} else if(a[1].size() >= 2){
ONE();
} else {
m.pb(a[1][0]); m.pb(nw++);
if(use_machine(m) == 1) a[0].pb(nw-1);
else a[1].pb(nw-1);
}
}
}
int count_mushrooms(int N) {
int n = N;
a[1] = {0};
if(n >= 300) pre();
ans = a[1].size();
while(nw <= n-1){
int tot = 0;
vector<int> m;
if(a[0].size() < a[1].size()){//pake a
for(int i=0; i<a[1].size(); i++){
m.pb(a[1][i]); m.pb(nw++);
tot++;
if(nw == n) break;
}
int ret = use_machine(m);
ans += tot-1-ret/2; // ret/2 = B
if(ret%2 == 1) a[0].pb(m.back()); // ada b di depan
else ans++, a[1].pb(m.back());
} else {//pake b
for(int i=0; i<a[0].size(); i++){
m.pb(a[0][i]); m.pb(nw++);
tot++;
if(nw == n) break;
}
int ret = use_machine(m);
ans += ret/2; // ret/2 = A
if(ret%2 == 1) ans++, a[1].pb(m.back()); // ada b di depan
else a[0].pb(m.back());
}
}
return ans;
}
