#include "bits/stdc++.h"
#include "mushrooms.h"
using namespace std;
int count_mushrooms(int n) {
if(n <= 226){
int cnt = 1;
vector<int> v;
v.push_back(0);
for(int j = 1; j < n; j++){
v.push_back(j);
int x = use_machine(v);
if(!x) cnt++;
v.pop_back();
}
return cnt;
}
vector<int> type[2];
type[0].push_back(0);
vector<int> v;
v.push_back(0);
int ind = 0;
for(int j = 1; j < n; j++){
v.push_back(j);
int x = use_machine(v);
type[x].push_back(j);
v.pop_back();
if(max(type[0].size(), type[1].size()) >= 100){
ind = j+1;
}
}
int ans = type[0].size();
while(ind < n){
vector<int> query;
if(type[0].size() > type[1].size()){
int koy = 0;
for(int i = 0; i < type[0].size()-1; i++){
query.push_back(type[0][i]);
if(ind < n){
query.push_back(ind);
ind++;
koy++;
}
}
query.push_back(type[0].back());
int val = use_machine(query);
ans += (koy*2 - val) / 2;
}
else{
for(int i = 0; i < type[1].size()-1; i++){
query.push_back(type[1][i]);
if(ind < n){
query.push_back(ind);
ind++;
}
}
query.push_back(type[1].back());
int val = use_machine(query);
ans += (val / 2);
}
}
return ans;
}
