#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int C = 282;
int count_mushrooms(int n){
int cnt = 1;
vector<int> a{0}, b;
for(int i = 1; i < min(n, 3); ++i){
if(!use_machine(vector<int>{0, i})){
cnt++;
a.push_back(i);
}
else b.push_back(i);
}
for(int i = 3; i < min(n, C + 1); i += 2){
vector<int> v;
bool which;
if(a.size() >= 2){
v = {a[0], a[1]};
which = false;
}
else{
v = {b[0], b[1]};
which = true;
}
if(i == min(n, C + 1) - 1){
if(!use_machine(vector<int>{0, i})){
cnt++;
a.push_back(i);
}
else b.push_back(i);
break;
}
int t = use_machine({v[0], i, v[1], i + 1});
if(!which) t = 3 - t;
if(t & 2){
cnt++;
a.push_back(i);
}
else b.push_back(i);
if(t & 1){
cnt++;
a.push_back(i + 1);
}
else b.push_back(i + 1);
}
for(int i = min(n, C + 1); i < n; i += (C / 2)){
vector<int> v;
int x = min(C / 2, n - i);
if(a.size() > b.size()){
for(int j = 0; j < x; ++j){
v.push_back(a[j]);
v.push_back(i + j);
}
v.push_back(a[x]);
}
else{
for(int j = 0; j < x; ++j){
v.push_back(b[j]);
v.push_back(i + j);
}
v.push_back(b[x]);
}
int t = use_machine(v);
if(a.size() > b.size()) cnt += x - t / 2;
else cnt += t / 2;
}
return cnt;
}
