#include "mushrooms.h"
using namespace std;
typedef vector<int> vi;
const int N = 141;
int aa[N * 2], bb[N * 2];
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 < N && nb < N)
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;
if (na > nb) {
ans = n - nb;
while (i < n) {
ii.resize(0);
for (h = 0; h < na; h++) {
ii.push_back(aa[h]);
if (i < n)
ii.push_back(i++);
}
ans -= (use_machine(ii) + 1) / 2;
}
} else {
ans = na;
while (i < n) {
ii.resize(0);
for (h = 0; h < nb; h++) {
ii.push_back(bb[h]);
if (i < n)
ii.push_back(i++);
}
ans += (use_machine(ii) + 1) / 2;
}
}
return ans;
}
