#include "mushrooms.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
std::mt19937 rng(123);
int calcK(int n) {
int K = 1;
int best = 1e9;
for (int k = 1; k <= n; k++) {
if (3 * k / 2 + (n - 3 * k / 2) / k < best) {
best = 3 * k / 2 + (n - 3 * k / 2) / k;
K = k;
}
}
return K;
}
int count_mushrooms(int n) {
std::vector<int> A, B;
A.push_back(0);
int cntA = 0;
for (int i = 1; i < n;) {
int addI = std::max((int) A.size(), (int) B.size());
if (A.size() > B.size()) { // xAyAzA
std::vector<int> query;
for (int k = 0; k < (int) A.size() && i + k < n; k++) {
query.push_back(i + k);
query.push_back(A[k]);
}
int aux = use_machine(query);
// aux % 2 imi spune despre prima valoare daca e B(1) sau A(0)
// hai sa iau un ex
// bAaAaAbAbAaA (are lungime 12)
// fiecare a imi da +0
// fiecare b imi da +2, mai putin primul care imi da +1
// 2 * 2 + 1 = 5 de la b uri
// primesc rezultatul 5
// eu zic ca am 12 / 2 - 5 / 2 - 1 = 6 - 2 - 1 = 4 - 1 = 3 a uri (sper ca e bine)
if (aux % 2 == 0) {
A.push_back(i);
} else {
B.push_back(i);
}
aux -= aux % 2; // practic am sters primul element
int sz = (int) query.size() - 2;
// x * (sz / 2)
// bs * 2 == aux
// as + bs = sz / 2
// 2 * as + aux == sz
// as = (sz - aux) / 2
// asta pare bine
cntA += sz / 2 - aux / 2;
} else { // xByBzB
std::vector<int> query;
for (int k = 0; k < (int) B.size() && i + k < n; k++) {
query.push_back(i + k);
query.push_back(B[k]);
}
int aux = use_machine(query);
if (aux % 2 == 0) {
B.push_back(i);
} else {
A.push_back(i);
}
aux -= aux % 2; // practic am sters primul element
cntA += aux / 2;
}
i += addI;
}
return cntA + (int) A.size();
}
