#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
int rep=1;
vector<int> A={0},B={};
int racine=sqrt(n);
racine=max(racine,(int)2);
int ec=1;
while ((int)A.size()<2 and (int)B.size()<2 and ec<n){
if (use_machine({0,ec})==0){
A.push_back(ec);
rep++;
}
else {
B.push_back(ec);
}
ec++;
}
//cout<<"racine"<<racine<<endl;
if (A.size()==2){
while ((int)A.size()<racine and (int)B.size()<racine and ec<n){
//cout<<42<<endl;
if (ec==n-1){
if (use_machine({0,ec})==0){
A.push_back(ec);
rep++;
}
else {
B.push_back(ec);
}
ec++;
}
else {
int val=use_machine({ec,A[0],ec+1,A[1]});
if (val==0){
A.push_back(ec);
A.push_back(ec+1);
rep+=2;
}
else if (val==1){
A.push_back(ec+1);
B.push_back(ec);
rep++;
}
else if (val==2){
A.push_back(ec);
B.push_back(ec+1);
rep++;
}
else {
B.push_back(ec);
B.push_back(ec+1);
}
ec+=2;
}
}
}
else {
//cout<<A.size()<<" "<<B.size()<<" "<<ec<<" "<<racine<<endl;
while ((int)A.size()<racine and (int)B.size()<racine and ec<n){
//cout<<ec<<endl;
if (ec==n-1){
if (use_machine({0,ec})==0){
A.push_back(ec);
rep++;
}
else {
B.push_back(ec);
}
ec++;
}
else {
int val=use_machine({ec,B[0],ec+1,B[1]});
//cout<<val<<endl;
if (val==0){
B.push_back(ec);
B.push_back(ec+1);
}
else if (val==1){
B.push_back(ec+1);
A.push_back(ec);
rep++;
}
else if (val==2){
B.push_back(ec);
A.push_back(ec+1);
rep++;
}
else {
A.push_back(ec);
A.push_back(ec+1);
rep+=2;
}
ec+=2;
}
}
}
/*for (auto i:A){
cout<<i<<" ";
}
cout<<endl;
for (auto i:B){
cout<<i<<" ";
}
cout<<endl;*/
//cout<<ec<<endl;
if ((int)A.size()>=racine){
while (ec<n){
vector<int> quest={};
int indice=0;
while (ec<n and indice<(int)A.size()){
quest.push_back(A[indice]);
quest.push_back(ec);
ec++;
indice++;
}
rep+=(int)quest.size()/2-(use_machine(quest)+1)/2;
}
//cout<<rep<<endl;
return rep;
}
while (ec<n){
vector<int> quest={};
int indice=0;
while (ec<n and indice<(int)B.size()){
quest.push_back(B[indice]);
quest.push_back(ec);
ec++;
indice++;
}
/*for (auto i:quest){
cout<<i<<" ";
}
cout<<endl;*/
rep+=(use_machine(quest)+1)/2;
}
//cout<<rep<<endl;
return rep;
}
