#include "mushrooms.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
std::mt19937 rng(123);
int count_mushrooms(int n) {
std::vector<int> order(n);
for (int i = 0; i < n; i++) {
order[i] = i;
}
std::shuffle(order.begin() + 1, order.end(), rng);
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;
}
}
int i;
std::vector<int> A, B;
A.push_back(0);
for (i = 1; i < (int) order.size() && (int) A.size() <= K && (int) B.size() <= K; i++) {
if (use_machine({0, order[i]}) == 0) {
A.push_back(order[i]);
} else {
B.push_back(order[i]);
}
}
bool swapped = false;
if (A.size() < B.size()) {
std::swap(A, B);
swapped = true;
}
std::vector<int> care;
for (; i < n; i++) {
care.push_back(order[i]);
}
int ret = !swapped? (int) A.size() : (int) B.size();
while (!care.empty()) {
std::vector<int> aici;
for (int ia = 0; ia < (int) care.size() && ia < K; ia++) {
aici.push_back(care.back());
care.pop_back();
}
assert(K >= 1);
assert((int) aici.size() >= 1);
std::vector<int> query;
query.push_back(A[0]);
assert((int) aici.size() < (int) A.size());
for (int i = 0; i < (int) aici.size(); i++) {
query.push_back(aici[i]);
query.push_back(A[i + 1]);
}
assert((int) query.size() >= 2);
if (!swapped) {
ret += use_machine(query) / 2;
} else {
ret += (int) query.size() / 2 - use_machine(query) / 2;
}
}
return ret;
}
