#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int sqt=140;
int solve(int n){
int resp=0;
vector<int>a, b;
a.push_back(0);
int id=1;
while(max(a.size(),b.size())<=sqt&&id<n){
vector<int>aux;
aux.push_back(0); aux.push_back(id);
if(use_machine(aux)) b.push_back(id);
else a.push_back(id);
id++;
}
resp=a.size();
if(a.size()>=sqt){
//cout << "A" << endl;
while(id<n){
vector<int>aux;
int qtd=0;
for(int i=0;i<a.size()-1;i++){
aux.push_back(a[i]);
if(id<n){
aux.push_back(id);
id++;
qtd++;
}
}
aux.push_back(a.back());
resp+=((2*qtd-use_machine(aux))/2);
}
}else{
//cout << "B" << endl;
while(id<n){
vector<int>aux;
int qtd=0;
for(int i=0;i<b.size()-1;i++){
aux.push_back(b[i]);
if(id<n){
aux.push_back(id);
id++;
qtd++;
}
}
aux.push_back(b.back());
resp+=(use_machine(aux)/2);
}
}
return resp;
}
int count_mushrooms(int n){
if(n<=500) return solve(n);
int resp=0;
vector<int>a, b;
a.push_back(0);
int id=1;
while(max(a.size(),b.size())<=2&&id<n){
vector<int>aux;
aux.push_back(0); aux.push_back(id);
if(use_machine(aux)) b.push_back(id);
else a.push_back(id);
id++;
}
if(a.size()>=2){
while(max(a.size(),b.size())<=sqt&&id<n){
vector<int>aux;
aux.push_back(id); id++;
aux.push_back(a[0]);
aux.push_back(id); id++;
aux.push_back(a[1]);
aux.push_back(id); id++;
int at1=use_machine(aux);
if(at1==0){
a.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
if(at1==4){
b.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
swap(aux[0],aux[2]);
int at2=use_machine(aux);
if(at1==at2&&at1==1){
a.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
if(at1==at2&&at1==3){
b.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
if(at1==1){
a.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
if(at1==3){
b.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
// ent at1=2, se caiu agr
if(at2==1){
b.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
if(at2==3){
a.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
}
}else{
while(max(a.size(),b.size())<=sqt&&id<n){
vector<int>aux;
aux.push_back(id); id++;
aux.push_back(b[0]);
aux.push_back(id); id++;
aux.push_back(b[1]);
aux.push_back(id); id++;
int at1=use_machine(aux);
if(at1==0){
b.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
if(at1==4){
a.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
swap(aux[0],aux[2]);
int at2=use_machine(aux);
if(at1==at2&&at1==1){
b.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
if(at1==at2&&at1==3){
a.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
if(at1==1){
b.push_back(aux[0]); a.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
if(at1==3){
a.push_back(aux[0]); b.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
// ent at1=2, se caiu agr
if(at2==1){
a.push_back(aux[0]); b.push_back(aux[2]); b.push_back(aux[4]);
continue;
}
if(at2==3){
b.push_back(aux[0]); a.push_back(aux[2]); a.push_back(aux[4]);
continue;
}
}
}
// ja ta certo essa parte
resp=a.size();
if(a.size()>=sqt){
//cout << "A" << endl;
while(id<n){
vector<int>aux;
int qtd=0;
for(int i=0;i<a.size()-1;i++){
aux.push_back(a[i]);
if(id<n){
aux.push_back(id);
id++;
qtd++;
}
}
aux.push_back(a.back());
resp+=((2*qtd-use_machine(aux))/2);
}
}else{
//cout << "B" << endl;
while(id<n){
vector<int>aux;
int qtd=0;
for(int i=0;i<b.size()-1;i++){
aux.push_back(b[i]);
if(id<n){
aux.push_back(id);
id++;
qtd++;
}
}
aux.push_back(b.back());
resp+=(use_machine(aux)/2);
}
}
return resp;
}
