#include <iostream>
#include <vector>
using namespace std;
int use_machine(vector<int> l);
int count_mushrooms(int n){
vector<int> known_as;
vector<int> known_bs;
if(n == 1)
return 1;
if(n == 2){
vector<int> use = {0, 1};
int rs = use_machine(use);
if(rs == 1)
return 1;
else
return 2;
}
known_as.push_back(0);
int idx = 0; // index tested
while(known_as.size() < 2 && known_bs.size() < 2){
vector<int> use = {0, idx+1};
int rs = use_machine(use);
if(rs == 0)
known_as.push_back(idx+1);
else if(rs == 1)
known_bs.push_back(idx+1);
idx++;
}
bool swapped = false;
if(known_as.size() < known_bs.size()){
swap(known_as, known_bs);
swapped = true;
} // a is b - b is a
while(known_as.size() < 135 && known_bs.size() < 135 && idx + 2 < n){
vector<int> use = {known_as[0], idx+1, known_as[1], idx+2};
int rs = use_machine(use);
if(rs == 0){
// both as
known_as.push_back(idx+1);
known_as.push_back(idx+2);
}else if(rs == 1){
known_as.push_back(idx+1);
known_bs.push_back(idx+2);
}else{
known_bs.push_back(idx+1);
known_bs.push_back(idx+2);
}
idx += 2;
}
if(known_as.size() < known_bs.size()){
swap(known_as, known_bs);
swapped = !swapped;
}
int res = 0;
while(idx < n-1){
vector<int> use;
int new_idx = idx;
for(int t = 1; t <= min(n-idx-1, (int)known_as.size()); t++){
use.push_back(known_as[t-1]);
use.push_back(new_idx+1);
new_idx++;
}
int rs = use_machine(use);
if(rs % 2 == 0){
known_as.push_back(new_idx);
}else{
known_bs.push_back(new_idx);
rs--;
}
res += rs/2;
idx = new_idx;
}
int num_bs = known_bs.size() + res;
int num_as = n - num_bs;
if(swapped){
swap(num_as, num_bs);
swap(known_as, known_bs);
}
return num_as;
}
