#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 get(int l, int r){
if(r - l == 1)
return 0;
vector<int> m;
for(int i = l; i < r; i++)
m.append(v[i]);
return use_machine(m);
}
int count(int l, int r){
int val = get(l, r);
if(val == 0){
if(use_machine({0, v[l]}))
return 0;
return r - l;
}
if(val == r - l - 1){
if(use_machine({0, v[l]}))
return (r - l) / 2;
return (r - l + 1) / 2;
}
if(r - l < 50){
int ans = 0;
for(int i = l + 1; i < r; i += 2)
ans += count(i - 1, i + 1);
if((l + r) % 2)
ans += count(r - 1, r);
return ans;
}
int mid = (l + r) / 2;
random_device rd;
mt19937 g(rd());
shuffle(v + l, v + r, g);
return count(l, mid) + count(mid, r);
}
int count_mushrooms(int n) {
for(int i = 0; i < n; i++)
v[i] = i;
return count(1, n) + 1;
}
