#include "insects.h" #include <bits/stdc++.h> using namespace std; struct insect { int i,sz; }; vector<insect> types; int min_cardinality(int N) { types.push_back(insect{0, 1}); move_inside(0); vector<bool> skip(N); int boxSz=1; for (int i = 1; i < N; i++) { move_inside(i); if(press_button()==1){ types.push_back(insect{i, 1}); boxSz++; } else{ int l=0, r=boxSz-1; while(r-l>0){ int mid=(l+r)/2; for (int j = mid+1; j <= r; j++) move_outside(types[j].i); if(press_button()>1){ r=mid; }else{ l=mid+1; for (int j = mid+1; j <= r; j++) move_inside(types[j].i); for (int j = l; j <= mid; j++) move_outside(types[j].i); } } types[l].sz++; move_outside(l); move_outside(i); for (int j = 0; j < (int)types.size(); j++) move_inside(types[j].i); } } int mn=1e9; for (int j = 0; j < (int)types.size(); j++) mn=min(mn,types[j].sz); return mn; }