#include "mushrooms.h"
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int count_mushrooms(int n) {
set<int> v;
int q = 2*sqrt(n);
set<int> a;
a.insert(0);
if(n<=10){
int o = 0;
for(int i=1; i<n; i++){
o+=use_machine({0, i});
}
return o;
}
int first = use_machine({1, 0, 2});
int touse, tovis =0;
bool flag= true;
if(first ==0){
touse = 1;
a.insert(1);
a.insert(2);
}
else if(first==2) {
touse=1; tovis = 2;
v.insert(1);
v.insert(2);
flag = false;
}
else{
first = use_machine({1, 0});
if(first==1)touse = 2;
else touse = 1;
a.insert(1);
}
for(int i=3; i<q-1; i+=2){
int x = use_machine({touse, i, tovis, i+1});
if(flag){
if(x%2==0){
v.insert(i+1);
if(x!=0)v.insert(i);
}
else{
v.insert(i);
}
}
else{
if(x%2==0){
a.insert(i+1);
if(x!=0)a.insert(i);
}
else{
a.insert(i);
}
}
}
int vv = v.size(), aa = a.size();
flag = (vv<=aa);
int fac = max(vv, aa);
for(int i=q+1; i<n&& i+q<n; i+=fac){
vector<int> mm;
if(flag){
int vo = 0;
for(auto it: a){
mm.push_back(it);
mm.push_back(vo+i);
vo++;
}
int vi = use_machine(mm);
aa+=(fac-(vi+1)/2);
}
else{
int vo = 0;
for(auto it: v){
mm.push_back(it);
mm.push_back(vo+i);
vo++;
}
int vi = use_machine(mm);
aa+=(vi+1)/2;
}
}
return aa;
}
