#include "mushrooms.h"
#include <vector>
#include <algorithm>
const int chunkSize = 265;
int div2RoundUp(int x)
{
int d = x / 2;
if (d * 2 < x)
return d + 1;
return d;
}
int count_mushrooms(int n)
{
using namespace std;
vector<int> aIndex = {0}, bIndex;
std::vector<int> m;
if (n == 1)
return 1;
if (n == 2)
{
m = {0, 1};
int a = use_machine(m);
if (a == 0)
return 2;
else
return 1;
}
m = {0, 1};
int a = use_machine(m);
if (a == 0)
aIndex.push_back(1);
else
bIndex.push_back(1);
m = {0, 2};
a = use_machine(m);
if (a == 0)
aIndex.push_back(2);
else
bIndex.push_back(2);
for (int i = 3; i < min(chunkSize, n); i += 2)
{
if (i + 1 < min(chunkSize, n))
{
if (bIndex.size() >= 2)
{
// use _B_B
m = {i, bIndex[0], i + 1, bIndex[1]};
a = use_machine(m);
switch (a)
{
case 0:
bIndex.push_back(i);
bIndex.push_back(i + 1);
break;
case 1:
aIndex.push_back(i);
bIndex.push_back(i + 1);
break;
case 2:
bIndex.push_back(i);
aIndex.push_back(i + 1);
break;
case 3:
aIndex.push_back(i);
aIndex.push_back(i + 1);
break;
}
}
else
{
// use _A_A
m = {i, aIndex[0], i + 1, aIndex[1]};
a = use_machine(m);
switch (a)
{
case 0:
aIndex.push_back(i);
aIndex.push_back(i + 1);
break;
case 1:
bIndex.push_back(i);
aIndex.push_back(i + 1);
break;
case 2:
aIndex.push_back(i);
bIndex.push_back(i + 1);
break;
case 3:
bIndex.push_back(i);
bIndex.push_back(i + 1);
break;
}
}
}
else
{
m = {0, i};
a = use_machine(m);
if (a == 0)
aIndex.push_back(i);
else
bIndex.push_back(i);
}
}
int aCount = 0;
int len = max(aIndex.size(), bIndex.size());
for (int i = chunkSize; i < n; i += len)
{
if (aIndex.size() > bIndex.size())
{
// use A_A_A_...
m.clear();
for (int j = 0; j < min(n - i, (int)aIndex.size()); j++)
{
m.push_back(aIndex[j]);
m.push_back(i + j);
}
a = use_machine(m);
aCount += min(n - i, (int)aIndex.size()) - div2RoundUp(a);
}
else
{
// use B_B_B_...
m.clear();
for (int j = 0; j < min(n - i, (int)bIndex.size()); j++)
{
m.push_back(bIndex[j]);
m.push_back(i + j);
}
a = use_machine(m);
aCount += div2RoundUp(a);
}
}
return aCount + aIndex.size();
}
