#include "insects.h"
#include <vector>
// void move_inside(int i)
// void move_outside(int i)
// int press_button()
// gaseste numarul de valori distincte in N operatii
int dist_val( int N ) {
std::vector<bool> rem( N, false );
int ret = 0;
for( int i = 0 ; i < N ; i++ ){
move_inside( i );
if( press_button() > 1 )
move_outside( i );
else{
ret++;
rem[i] = true;
}
}
// cleanup
for( int i = 0 ; i < N ; i++ )
if( rem[i] )
move_outside( i );
return ret;
}
bool at_least_x( std::vector<int> &poz, int x, int dist ) {
int n = (int)poz.size();
std::vector<bool> rem( n, false );
int good_poz = 0;
for( int i = 0 ; i < n ; i++ ){
move_inside( poz[i] );
if( press_button() > x )
move_outside( poz[i] );
else{
rem[i] = true;
good_poz++;
}
}
// cleanup
for( int i = 0 ; i < n ; i++ )
if( rem[i] )
move_outside( poz[i] );
bool decision = (good_poz == dist * x); // min(freq) >= x
int news = 0;
for( int i = 0 ; i < n ; i++ )
if( rem[i] != decision )
poz[news++] = poz[i];
poz.erase( poz.begin() + news, poz.end() );
return decision;
}
int min_cardinality( int N ) {
int dist = dist_val( N );
std::vector<int> poz;
for( int i = 0 ; i < N ; i++ )
poz.push_back( i );
int st = 0, dr = N / dist + 1;
while( dr - st > 1 ){
int mij = (st + dr) >> 1;
int bias = (dr - st) / 100;
mij -= bias;
if( at_least_x( poz, mij - st, dist ) )
st = mij;
else
dr = mij;
}
return st;
}
