#include <iostream>
#include <vector>
#include <math.h>
#include "mushrooms.h"
using namespace std;
// bool ans[] = {1, 0, 1, 1, 0, 1, 0, 1, 0};
// int use_machine(vector<int> v){
// int curr = ans[v[0]];
// int a = 0;
// for(int i = 1; i<v.size(); i++){
// if(ans[v[i]] != curr) a++;
// curr = ans[v[i]];
// }
// return a;
// }
int count_mushrooms(int n){
int ans = 1;
vector<int> a = {0};
vector<int> b;
int rt = sqrt(n);
int ind = 0;
int res = 1;
while(a.size() < rt && b.size() < rt){
ind++;
int tmp = use_machine({0, ind});
if(tmp == 1) b.push_back(ind);
else {a.push_back(ind); res++;}
}
char g = (a.size() > b.size())? 'a' : 'b';
vector<int> good = (a.size() > b.size())? a : b;
while(ind < n-1){
int k = 0;
vector<int> q;
while(ind < n-1 && k<good.size()){
if(q.size()%2){
q.push_back(good[k++]);
}
else{
q.push_back(++ind);
}
}
if(ind == n-1) q.push_back(good[k++]);
if(g == 'a'){
res += q.size()/2 - ((use_machine(q)+1)/2);
}
else{
res += (use_machine(q) + 1) /2;
}
}
return res;
}
// int main(void){
// cout<<count_mushrooms(9);
// }
/*
a x a x a
4 ->
*/
