#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 20000
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int v[MAXN];
int check(vector<int> m){
if(m.size() == 1)
return 0;
return use_machine(m);
}
int count(int l, int r, int val){
if(!val){
if(check({0, v[l]}) == 0)
return r - l;
return 0;
}
if(val == r - l - 1){
if(check({0, v[l]}))
return (r - l) / 2;
return (r - l + 1) / 2;
}
int x = (r - l) / (min(val, r - l - 1 - val) + 1);
x = max(x, 2);
random_device rd;
mt19937 g(rd());
shuffle(v + l, v + r, g);
int ans = 0;
vector<int> m;
for(int i = l; i < r; i++){
if(m.size() == x){
ans += count(l, i, check(m));
m.clear();
l = i;
}
m.append(v[i]);
}
if(!m.empty())
ans += count(l, r, check(m));
return ans;
}
int count_mushrooms(int n) {
vector<int> m;
for(int i = 1; i < n; i++){
m.append(i);
v[i] = i;
}
return count(1, n, check(m)) + 1;
}
