#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
int count_mushrooms(int n) {
// int mn = 1000000, sz;
// for(int k = 2; k <= 500; ++k){
// int q = k;
// int rem = 20000 - k;
// for(; rem > 0; ){
// rem -= k;
// rem -= k;
// k++;
// q+=2;
// }
// if(mn>q) sz=k;
// mn=min(mn,q);
// }
// cout << mn << ' ' << sz;
vector<int> A, B;
A.pb(0);
int last = 1, add = 0;
int q = use_machine({0, 1});
if(q == 0){
A.pb(1);
last = 2;
}else{
B.pb(1);
last =2 ;
if(n == 2) return 1;
int q = use_machine({0, 2});
if(q == 1) B.pb(2);
else A.pb(2);
last = 3;
}
for(int i = 0; i < 100 && last + 1 < n; ++i){
if(A.size()>1){
int x = use_machine({A[0], last, A[1], last + 1});
if(x % 2 == 0) A.pb(last + 1);
else B.pb(last + 1);
if(x > 1) B.pb(last);
else A.pb(last);
last += 2;
}else{
int x = use_machine({B[0], last, B[1], last + 1});
if(x % 2 == 0) B.pb(last + 1);
else A.pb(last + 1);
if(x > 1) A.pb(last);
else B.pb(last);
last += 2;
}
}
while(last < n){
if(A.size() > B.size()){
vector<int> q;
int s = A.size();
for(int j = last; j < min(n, last + s); ++j){
q.pb(j);
q.pb(A[j - last]);
}
last = min(n, last + s);
int f = use_machine(q);
s = q.size()/2 - 1;
add += s - f/2;
if(f%2==0) A.pb(q[0]);
else B.pb(q[0]);
}else{
vector<int> q;
int s = B.size();
for(int j = last; j < min(n, last + s); ++j){
q.pb(j);
q.pb(B[j - last]);
}
int f = use_machine(q);
add += f/2;
if(f%2==1) A.pb(q[0]);
else B.pb(q[0]);
last = min(n, last + s);
}
}
return int(A.size()) + add;
}
