// 57 points, q = 397
#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// ideias:
// - encontrar um conjunto de caras com mesmo valor
// - usar eles como "separadores" para contar desconhecidos
//
// passo 1:
// 2k - 2 queries [0, i] para encontrar k iguais
// entre os 2k - 1 primeiros
//
// passo 2:
// agora sobraram n - 2k + 1 ainda pra contar
// #queries adicionais = teto( (n - 2k + 1) / k )
//
// otimizacao:
// minimize 2k - 2 + (n - 2k + 1) / k
// = 2k + (n + 1)/k - 4
// ~ 2k + n/k
//
// minimize 2k + n/k
// 2k = n/k
// k = sqrt(n / 2)
// k = 100
//
// total:
// 198 queries para encontrar 100 iguais entre os 199 primeiros
// teto[(20000 - 199) / 100] = 199 queries pro resto
// 198 + 199 = 397 queries
int count_mushrooms(int n) {
if (n == 1) return 1;
vector<int> pos_A;
vector<int> pos_B;
pos_A.push_back(0);
int k = 100;
// passo 1
for (int i = 1; i < 2 * k - 1; i++) {
if (i >= n) return ((int) pos_A.size());
if (use_machine({0, i}) == 0) pos_A.push_back(i);
else pos_B.push_back(i);
}
int step = pos_A.size();
bool using_b = false;
if (pos_A.size() < pos_B.size()) {
using_b = true;
step = pos_B.size();
}
// cout << "pos_A: ";
// for (int x: pos_A) {
// cout << x << " ";
// }
// cout << endl;
// cout << "pos_B: ";
// for (int x: pos_B) {
// cout << x << " ";
// }
// cout << endl;
// cout << "using_b = " << using_b << endl;
// cout << "step = " << step << endl;
int ans = pos_A.size();
int ini = 2 * k - 1;
while (ini < n) {
// ini x0 ini+1 x1 ini+2 x2 ... ini+step-1 xstep-1
// alternadamente
vector<int> aux;
int last = min(n - 1, ini + step - 1);
int cur_sz = last - ini + 1;
for (int j = 0; j < cur_sz; j++) {
aux.push_back({ini + j});
int pos_to_use = using_b ? pos_B[j] : pos_A[j];
aux.push_back(pos_to_use);
}
// cout << "will make query ";
// for (int x: aux) {
// cout << x << " ";
// }
// cout << endl;
int ret = use_machine(aux);
// cout << "got " << ret << endl;
if (using_b) {
ans += (ret + 1) / 2;
} else {
ans += cur_sz - (ret + 1) / 2;
}
ini += cur_sz;
// cout << "now ans = " << ans << endl;
// cout << "now ini = " << ini << endl;
}
return ans;
}
