#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 2e3+3, inf = INT_MAX;
mt19937 rng((chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
int n, mx, taken, ans;
vector<int> v;
bitset<N> vis;
int min_cardinality(int N) {
// move_inside(i);
// move_outside(i);
// press_button(i);
ans = inf;
n = N;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = i;
// Busco el maximo
for (int i = 0; i < n; i++) {
move_inside(i);
}
mx = press_button();
for (int i = 0; i < n; i++) {
move_outside(i);
}
// Busco los primeros
for (int i = 0; i < n; i++) {
move_inside(i);
vis[i] = 1;
if (press_button() > 1) {
move_outside(i);
vis[i] = 0;
}
}
// Hago el greedy
int sz = vis.count();
taken = sz;
for (int i = 0; i < sz; i++) {
shuffle(all(v), rng);
mx = min(mx, n-taken+1);
int curr = 1;
vector<int> added;
for (int j = 0; j < n && curr < mx; j++) {
int x = v[j];
if (vis[x]) continue;
move_inside(x);
if (press_button() == curr+1) {
vis[x] = 1;
curr++;
added.push_back(x);
}
else {
move_outside(x);
}
}
for (int& x : added) {
move_outside(x);
}
ans = min(ans, curr);
taken += curr-1;
}
return ans;
}
/*
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 2e3+3, inf = INT_MAX;
mt19937 rng((chrono::steady_clock::now().time_since_epoch().count()) + ((uint64_t) new char));
int n, mx, taken, ans, tp[N];
vector<int> v, f;
int min_cardinality(int N) {
// move_inside(i);
// move_outside(i);
// press_button(i);
memset(tp, -1, sizeof(tp));
ans = inf;
n = N;
v.resize(n);
for (int i = 0; i < n; i++) v[i] = i;
// en el primer for los meto todos y intento identificar los que son iguales al primero
// y los primeros (si el max es 1 y despues de añadir sigue siendo 1, es un primero)
// quiero saber cuanto vale max
shuffle(all(v), rng);
mx = 1;
int extra = 0;
bool ok = 1;
move_inside(v[0]);
f.push_back(v[0]);
tp[v[0]] = 0;
for (int i = 1; i < n; i++) {
int x = v[i];
move_inside(x);
mx = press_button();
if (ok && mx == i+1) {
tp[x] = 0;
extra++;
}
else {
ok = 0;
if (mx == 1) {
tp[x] = tp[f.back()]+1;
f.push_back(x);
}
}
}
// quito los no primeros
int curr = 0;
for (int i = 0; i < n; i++) {
int x = v[i];
if (curr < (int)f.size() && f[curr] == x) {
curr++;
continue;
}
move_outside(x);
}
// primer for y ver cuantos son iguales al primero
shuffle(all(v), rng);
for (int i = 0; i < n; i++) {
int x = v[i];
if (tp[x] != -1) continue;
move_inside(x);
if (press_button() > 1) {
move_outside(x);
}
else {
tp[x] = tp[f.back()]+1;
f.push_back(x);
}
}
taken = f.size();
// miro cada grupo
for (int t = 0; t < (int)f.size(); t++) {
shuffle(all(v), rng);
mx = min(mx, n-taken+1);
if (t) extra = 0;
curr = 1; // cuantos he metido?
vector<int> added;
for (int i = 0; i < n && curr+extra < mx; i++) {
int x = v[i];
if (tp[x] != -1) continue;
move_inside(x);
if (press_button() == curr+1) {
tp[x] = t;
added.push_back(x);
curr++;
}
else {
move_outside(x);
}
}
for (int& x : added) {
move_outside(x);
}
ans = min(ans, curr+extra);
taken += curr+extra-1;
}
return ans;
}
*/
