#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
typedef pair <int, int> pii;
int count_mushrooms(int N) {
int ans = 1;
int root = sqrt(N);
vector <vector <int>> by_type(2);
auto larger = [&]() -> pii {
vector <pii> tmp(2);
for (int i = 0; i < 2; i++)
tmp[i] = {by_type[i].size(), i};
return max(tmp[0], tmp[1]);
};
pii big;
int pos = 1;
by_type[0].push_back(0);
while (pos < N) {
big = larger();
if (big.first > root)
break;
if (big.first >= 3 && pos < N - 1) {
int curr = use_machine({by_type[big.second][0], pos, by_type[big.second][1], by_type[big.second][2], pos + 1});
int x = curr / 2 ^ big.second;
int y = curr % 2 ^ big.second;
by_type[x].push_back(pos);
by_type[y].push_back(pos + 1);
ans += !x;
ans += !y;
pos += 2;
}
else {
int curr = use_machine({0, pos});
by_type[curr].push_back(pos);
ans += !curr;
pos++;
}
}
for (int i = pos; i < N; i += big.first - 1) {
vector <int> sequence = {by_type[big.second][0]};
for (int j = i; j < min(N, i + big.first - 1); j++) {
sequence.push_back(j);
sequence.push_back(by_type[big.second][j - i + 1]);
}
int curr = use_machine(sequence) / 2;
ans += big.second ? curr : (int)sequence.size() / 2 - curr;
}
return ans;
}
