#include "mushrooms.h"
using namespace std;
typedef vector<int> vi;
const int N = 20000, B = 100;
int aa[N], bb[N];
int count_mushrooms(int n) {
vi ii;
int na, nb, h, i, x, ans;
i = 1, na = nb = 0;
aa[na++] = 0;
while (i < n && na < B && nb < B)
if (na >= 2) {
ii.resize(0);
ii.push_back(aa[0]), ii.push_back(i), ii.push_back(aa[1]);
if (i + 1 < n)
ii.push_back(i + 1);
x = use_machine(ii);
if ((x & 2) == 0)
aa[na++] = i;
else
bb[nb++] = i;
if (i + 1 < n) {
if ((x & 1) == 0)
aa[na++] = i + 1;
else
bb[nb++] = i + 1;
}
i += 2;
} else if (nb >= 2) {
ii.resize(0);
ii.push_back(bb[0]), ii.push_back(i), ii.push_back(bb[1]);
if (i + 1 < n)
ii.push_back(i + 1);
x = use_machine(ii);
if ((x & 2) == 0)
bb[nb++] = i;
else
aa[na++] = i;
if (i + 1 < n) {
if ((x & 1) == 0)
bb[nb++] = i + 1;
else
aa[na++] = i + 1;
}
i += 2;
} else {
ii.resize(0);
ii.push_back(0), ii.push_back(i);
if (use_machine(ii) == 0)
aa[na++] = i;
else
bb[nb++] = i;
i++;
}
if (i >= n)
return na;
ans = na;
while (i < n) {
int n_;
if (na > nb) {
ii.resize(0);
for (h = 0; h < na; h++) {
ii.push_back(aa[h]);
if (i < n)
ii.push_back(i++);
}
n_ = ii.size();
x = use_machine(ii);
if (n_ == na * 2) {
if (x % 2 == 1)
bb[nb++] = ii[--n_], x--;
else
aa[na++] = ii[n_ - 1], ans++;
}
ans += n_ - na - x / 2;
} else {
ii.resize(0);
for (h = 0; h < nb; h++) {
ii.push_back(bb[h]);
if (i < n)
ii.push_back(i++);
}
n_ = ii.size();
x = use_machine(ii);
if (n_ == nb * 2) {
if (x % 2 == 1)
aa[na++] = ii[--n_], ans++, x--;
else
bb[nb++] = ii[n_ - 1];
}
ans += x / 2;
}
}
return ans;
}
