#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int f(int n, int k){
return k + (n + k - 2) / k - 2;
}
int count_mushrooms(int n) {
if (n <= 227){
int ans = 1;
for (int i = 1; i < n; i++){
ans += 1 - use_machine({0, i});
}
return ans;
}
vector<int> vec;
int k = 1;
for (int i = 1; i <= n; i++){
if (f(n, i) < f(n, k)) k = i;
}
vector<int> A = {0}, B;
for (int i = 1; i <= 2; i++){
if (use_machine({0, i})) B.push_back(i); else
A.push_back(i);
}
for (int i = 3; i < min(n, 2 * k - 1); i += 2){
if (i + 1 == n){
if (use_machine({0, i})) B.push_back(i); else
A.push_back(i);
break;
}
if (A.size() >= 2){
vec = {i, A[0], i + 1, A[1]};
int res = use_machine(vec);
if (res % 2) B.push_back(i); else
A.push_back(i);
if (res >= 2) B.push_back(i + 1); else
A.push_back(i + 1);
} else {
vec = {i, B[0], i + 1, B[1]};
int res = use_machine(vec);
if (res % 2) A.push_back(i); else
B.push_back(i);
if (res >= 2) A.push_back(i + 1); else
B.push_back(i + 1);
}
}
int beg = 2 * k - 1;
int ans = A.size();
for (int i = beg; i < n;){
vec.clear();
k = max(A.size(), B.size());
bool ok = A.size() >= B.size();
for (int j = i; j < min(n, i + k); j++){
vec.push_back(j);
vec.push_back(ok ? A[j - i] : B[j - i]);
}
int res = use_machine(vec);
if (ok) ans += vec.size() / 2 - (res + 1) / 2; else
ans += (res + 1) / 2;
if (res % 2){
if (ok) B.push_back(i); else
A.push_back(i);
}
i += k;
}
return ans;
}
