#include <bits/stdc++.h>
using namespace std;
#include "mushrooms.h"
int count_mushrooms(int n) {
if(n <= 999){
int A = 1, B = 0;
for(int i = 1; i < n; i++){
int kek = use_machine({0, i});
if(kek == 0){
A++;
}else{
B++;
}
}
return A;
}
int ans = 1e9;
int kekViename = -1;
for(int i = 1; i < n; i++){
int st = 2 * i + (n - 2*i) / (i) + 1; // kuo tiksliau, tuo geriau!
if(ans > st){
ans = st;
kekViename = i;
}
}
kekViename -= 40;
int lastTaken = 0;
vector<int> A = {0}, B;
int left = n-1;
int answ = 1;
//cout << "ieskosiu pirmuju " << kekViename << " * 2 skaiciu!" << endl;
for(int i = 1; i <= kekViename * 2; i++){
int kek = use_machine({0, i});
if(kek == 0){
A.push_back(i);
answ++;
}else{
B.push_back(i);
}
left--;
lastTaken = i;
if((int)A.size() >= kekViename+1 || (int)B.size() >= kekViename+1){
break;
}
}
//cout << "radau! A: "; for(auto x : A) cout << x<< " ";
//cout << ". B: "; for(auto x : B) cout << x << " "; cout << endl << endl;
while(true){
if(A.size() > B.size()){
//cout << "I tarpus desim A " << endl;
// desim A ir i tarpus kitka
vector<int> st;
int ind = 1;
st.push_back(A[0]);
for(int i = 0; i < min(left, (int) A.size()-1); i++){
st.push_back(++lastTaken);
st.push_back(A[ind++]);
}
st.pop_back();
int visoBuvo = min(left, (int) A.size()-1);
//cout << "gaunam st: "; for(auto x : st) cout << x << " "; cout << endl;
left -= min(left, (int) A.size()-1);
int rz = use_machine(st);
//cout << "pridedame " << visoBuvo << " - " << rz << "/2\n\n";
if(rz & 1){
B.push_back(st.back());
}else{
A.push_back(st.back());
}
answ += visoBuvo - (rz/2 + (rz & 1));
}else{
vector<int> st;
int ind = 1;
st.push_back(B[0]);
for(int i = 0; i < min(left, (int) B.size()-1); i++){
st.push_back(++lastTaken);
st.push_back(B[ind++]);
}
st.pop_back();
left -= min(left, (int) B.size()-1);
int rz = use_machine(st);
if(rz & 1){
A.push_back(st.back());
}else{
B.push_back(st.back());
}
answ += rz/2 + (rz & 1);
}
if(left == 0) break;
}
return answ;
}
