#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
struct Result {
int num_added;
int done_after;
int num_tried;
};
Result check(deque<int>& remaining, int old_h, int target_h, int num_different) {
cerr << "Running with target_h = " << target_h << endl;
Result res;
res.num_added = 0;
res.done_after = 0;
res.num_tried = 0;
int max_tried = sz(remaining);
while (res.num_tried < max_tried) {
int x = remaining.front();
cerr << "Checking " << x << endl;
remaining.pop_front();
++res.num_tried;
move_inside(x);
if (press_button() <= target_h) {
cerr << "Accepted" << endl;
++res.num_added;
res.done_after = res.num_tried;
if (res.num_added == num_different * (target_h-old_h)) {
break;
}
} else {
cerr << "Rejected" << endl;
remaining.push_back(x);
move_outside(x);
}
}
return res;
}
int min_cardinality(int N) {
vector<int> v;
rep(i,0,N)
v.push_back(i);
deque<int> remaining;
for (int x : v)
remaining.push_back(x);
random_shuffle(all(remaining));
auto res = check(remaining, 0, 1, N);
int num_different = res.num_added;
int h = 1;
while (true) {
res = check(remaining, h, h+1, num_different);
if (res.num_added < num_different) {
return h;
}
h++;
}
}
