#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
#define MAXN 1048579 // 2^20+3
#define forR(i, n) for (int i = 0; i < (n); i++)
#ifdef TEST_LOCAL
int use_machine(vector<int> x) {
return -1;
}
#else
int use_machine(vector<int> x);
#endif // TEST_LOCAL
int count_mushrooms(int n) {
if (n < 200) {
int cntA = 1;
for (int i = 1; i < n; i++) {
if (use_machine(vector<int>{0, i}) == 0)
cntA++;
}
return cntA;
}
vector<int> As, Bs; As.push_back(0);
int i = 1;
while (As.size() < 2 && Bs.size() < 2) {
int m = use_machine(vector<int>{0, i});
if (m == 0) As.push_back(i);
else Bs.push_back(i);
i++;
}
while (i <= 160) {
auto as = &As, bs = &Bs;
if (As.size() < 2) swap(as, bs);
int m = use_machine(vector<int>{ (*as)[0], i, (*as)[1], i + 1 });
if ((m & 2) == 0) {
as->push_back(i);
} else {
bs->push_back(i);
}
if ((m & 1) == 0) {
as->push_back(i + 1);
} else {
bs->push_back(i + 1);
}
i += 2;
}
int cntA = 0;
while (i < n) {
int rest = n - i;
auto as = &As, bs = &Bs;
if (As.size() < Bs.size()) swap(as, bs); // as is larger
int l = min(rest, (int)as->size());
vector<int> test;
for (int j = 0; j < l; j++) {
test.push_back((*as)[j]);
test.push_back(i + j);
}
int m = use_machine(test);
if ((m & 1) == 0) {
as->push_back(test.back());
} else {
bs->push_back(test.back());
}
int cnt_b = m / 2;
int cnt_a = l - 1 - cnt_b;
if ((*as)[0] == 0) {
cntA += cnt_a;
} else {
cntA += cnt_b;
}
i += l;
}
return As.size() + cntA;
}
#ifdef TEST_LOCAL
vector<vector<int>> gen01Seq(int n) {
if (n == 1) return vector<vector<int>>{ { 0 }, { 1 }};
vector<vector<int>> all;
vector<vector<int>> seqs = gen01Seq(n - 1);
for (auto s : seqs) {
s.push_back(0);
all.push_back(s);
}
for (auto s : seqs) {
s.push_back(1);
all.push_back(s);
}
return all;
}
int calc(vector<int> ns) {
int ans = 0;
for (int i = 0; i < ns.size() - 1; i++) {
if (ns[i] != ns[i + 1])
ans++;
}
return ans;
}
int main() {
auto s4 = gen01Seq(4);
vector<vector<int>> alleq2;
for (auto& s : s4) {
if (calc(vector<int> { 0, s[0], s[1], s[2], s[3] }) == 2) {
alleq2.push_back(s);
}
}
int bestStep = 1000000, bestm = -1;
for (int m = 60; m < 300; m++) {
int step = m;
int rest = 20000 - 2 * m;
int k = m * 2;
// got A*m
while (rest > 0) {
rest -= (k + 1) / 2; step++;
k++;
}
if (step < bestStep) {
bestStep = step;
bestm = m;
}
}
return 0;
}
#endif
