#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 2005;

int n;
int used[N];
vector<int> diff;

}

int min_cardinality(int grdn) {
	n = grdn;
	for (int i = 0; i < n; ++i) {
		move_inside(i);
		if (press_button() > 1) {
			move_outside(i);
		} else {
			used[i] = 1;
			diff.push_back(i);
		}
	}
	int k = diff.size();
	if (k <= 2) {
		for (int i : diff) {
			move_outside(i);
		}
		int ret = n;
		for (int it = 0; it < 100; ++it) {
			vector<int> a;
			for (int i = 0; i < n; ++i) {
				if (!used[i]) {
					a.push_back(i);
				}
			}
			if (a.empty()) {
				break;
			}
			vector<int> b;
			for (int i : a) {
				move_inside(i);
				if (press_button() == (int)b.size() + 1) {
					b.push_back(i);
				} else {
					move_outside(i);
				}
			}
			ret = min(ret, (int)b.size());
			for (int i : b) {
				move_outside(i);
				used[i] = 1;
			}
		}
		return ret;
	}
	int ret = 1;
	int m = n / k - 1;
	while (true) {
		vector<int> a;
		for (int i = 0; i < n; ++i) {
			if (!used[i]) {
				a.push_back(i);
			}
		}
		if ((int)a.size() < k || m == 0) {
			break;
		}
		int x = m * 0.28;
		x = max(x, 1);
		x = min(x, m);
		vector<int> b;
		for (int i : a) {
			move_inside(i);
			if (press_button() - ret > x) {
				move_outside(i);
			} else {
				b.push_back(i);
			}
		}
		if ((int)b.size() == x * k) {
			m -= x;
			ret += x;
			for (int i : b) {
				used[i] = 1;
			}
		} else {
			for (int i : b) {
				move_outside(i);
			}
			m = x - 1;
		}
	}
	return ret;
}