#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
int count_mushrooms(int n) {
int tam = 141;
vector<int> a = {0}, b;
for (int i = 1; i <= min(n-1,2); i++){
vector<int> aux = {0,i};
if(use_machine(aux) == 0)a.push_back(i);
else b.push_back(i);
}
int lst = 2;
for (int i = 3; i < n; i+=2){
if(i == n-1){
vector<int> aux = {0,i};
if(use_machine(aux) == 0)a.push_back(i);
else b.push_back(i);
lst = i;
break;
}
if(sz(a) >= 2){
vector<int> aux = {i,a[0],i+1,a[1]};
int x = use_machine(aux);
if(x == 0){ a.push_back(i); a.push_back(i+1); }
else if(x == 1){ b.push_back(i); a.push_back(i+1); }
else if(x == 2){ a.push_back(i); b.push_back(i+1); }
else { b.push_back(i); b.push_back(i+1); }
}else{
vector<int> aux = {i,b[0],i+1,b[1]};
int x = use_machine(aux);
if(x == 0){ b.push_back(i); b.push_back(i+1); }
else if(x == 1){ a.push_back(i); b.push_back(i+1); }
else if(x == 2){ b.push_back(i); a.push_back(i+1); }
else { a.push_back(i); a.push_back(i+1); }
}
lst = i+1;
if(sz(a) >= tam || sz(b) >= tam)break;
}
if(lst+1 == n)return sz(a);
vector<int> aux;
int pt = 0, ans = sz(a);
for(int i = lst+1; i <= n; i++){
if(sz(a) > sz(b))aux.push_back(a[pt]);
else aux.push_back(b[pt]);
pt++;
if(pt == tam || i == n){
if(sz(aux) == 1)break;
if(sz(a) > sz(b))ans += sz(aux) - pt - use_machine(aux)/2;
else ans += use_machine(aux)/2;
aux.clear();
if(sz(a) > sz(b))aux.push_back(a[0]);
else aux.push_back(b[0]);
pt = 1;
}
if(i == n)break;
aux.push_back(i);
}
return ans;
}
