#include "mushrooms.h"
using namespace std;
typedef vector<int> vi;
int queryOne(int ind) {
return 1-use_machine(vi{0, ind});
}
int naive(int n) {
int ans = 0;
for (int i = 1; i<n; ++i) ans += queryOne(i);
return ans+1;
}
int count_mushrooms(int n) {
if (n < 3) return naive(n);
vi temp(3); temp[0] = 1;
for (int i = 1; i<2; ++i) temp[i] = queryOne(i);
int a, b;
bool As = (temp[1] + temp[2]);
As ? (a = temp[1], b = temp[2]) : (a = 0, b = (temp[1] ? 1 : 2));
vi trans = As ? (vi){2, 1, 1, 0} : (vi){0, 1, 2, 2};
int ans = 1 + temp[1] + temp[2];
for (int i = 3; i<n-1; i += 2) {
int val = use_machine((vi){i, a, i+1, b});
ans += trans[val];
}
if (n % 2 == 0) ans += queryOne(n-1);
return ans;
}
