#include "insects.h"
#include <vector>
#include <iostream>
using namespace std;
bool debug=0;
#define derr if(debug)cerr
int min_cardinality(int N) {
// go around to find the value of D
vector<int> type(N, 0);
vector<int> ogtype(N,0);
vector<bool> is_in(N,false);
int D=1;
move_inside(0);
ogtype[0]=1;
type[0]=1;
is_in[0]=true;
for(int i=1; i<N; i++){
move_inside(i);
if(press_button() > 1){
// this is a repeat :p
move_outside(i);
} else{
// this is a new :/
D++;
ogtype[i]=D;
type[i]=D;
is_in[i]=1;
}
}
// now we know D ig
int sqrtN;
for(int i=0; i*i < N; i++){
sqrtN = i;
}
if(D > sqrtN){
// just keep doing sweeps
derr<<"checking for every answer (repeated sweeps) method...\n";
int curD = D;
int answer=1;
while(true){
// sweep `answer+1`
curD=0;
for(int i=1; i<N; i++){
if(!is_in[i]){
move_inside(i);
if(press_button() > answer+1){
// this thing occurs many times
move_outside(i);
} else{
is_in[i]=true;
curD++;
}
}
}
if(curD < D){
return answer;
} else{
answer++;
}
}
} else{
// do subtask 1 method
derr<<"subtask 1 method...\n";
if(debug){
cerr<<"is_in: ";
for(int i=0; i<N; i++){
cerr<<is_in[i]<<" ";
}
cerr<<"\n";
}
vector<int> typecount(D+1,0);
for(int i=0; i<N; i++){
if(is_in[i]){
move_outside(i);
}
}
for(int u=0; u<N-1; u++){
if(!ogtype[u])continue;
derr<<"u="<<u<<"\n";
if(debug){
cerr<<"$ types:\n";
for(int i=0; i<N; i++){
cerr<<type[i]<<" ";
}cerr<<"\n";
}
move_inside(u);
for(int v=u+1; v<N; v++){
if(type[v] || ogtype[v])continue;
move_inside(v);
if(press_button() == 2){
// same type!
type[v] = type[u];
}
move_outside(v);
}
move_outside(u);
}
for(int i=0; i<N; i++){
typecount[type[i]]++;
}
int answer=2001;
for(int i=1; i<D+1; i++){
answer = min(answer, typecount[i]);
}
if(debug){
cerr<<"$ types:\n";
for(int i=0; i<N; i++){
cerr<<type[i]<<" ";
}cerr<<"\n";
}
return answer;
}
}
