#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int an[20005];
/*int use_machine(vector<int> s)
{
int ans = 0;
for(int i = 1; i < s.size(); i++) ans += (an[s[i]] != an[s[i-1]]);
return ans;
}*/
int count_mushrooms(int n)
{
int ans = 1;
if(n <= 200){
for(int i = 1; i < n; i++) ans += 1-use_machine({0, i});
return ans;
}
vector<int> a, b;
a.push_back(0);
for(int i = 1; i <= 200; i++){
if(use_machine({0, i}) == 1) b.push_back(i);
else{
a.push_back(i);
ans++;
}
}
if(a.size() > 100){
int p = 201;
while(p < n){
vector<int> truncate = {a[0]};
int add = 0;
for(int i = 1; i < a.size(); i++){
if(p == n) break;
truncate.push_back(p++);
truncate.push_back(a[i]);
add++;
}
ans += add - use_machine(truncate)/2;
}
}
else{
int p = 201;
while(p < n){
vector<int> truncate = {b[0]};
for(int i = 1; i < b.size(); i++){
if(p == n) break;
truncate.push_back(p++);
truncate.push_back(b[i]);
}
ans += use_machine(truncate)/2;
}
}
return ans;
}
/*mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
signed main()
{
int n, c = 0; cin>>n;
for(int i = 0; i < n; i++){
an[i] = rng()%2;
if(i == 0) an[i] = 1;
c += an[i];
}
cerr<<c<<" "<<count_mushrooms(n);
}*/
