#include "cave.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
using namespace std;
///int tryCombination(intS[]);
bool nadjen[5010];
int N;
void exploreCave(int N) {
int znak[5010];
int n=N;
int gde[5010], koga[5010];
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++) if (!nadjen[j]) znak[j]=0;
int koja=tryCombination(znak);
///ispisi(znak);
int trZnak;///=(int)(koja!=-1 && koja<=i);
if (koja==-1 || koja>i) trZnak=0;
else trZnak=1;
///cout<<i<<" "<<koja<<" "<<trZnak<<endl;
int l=0, r=n-1;
while (l<=r)
{
int mid=l+(r-l)/2;
for (int j=0; j<n; j++) if (!nadjen[j]) { if (j<=mid) znak[j]=trZnak; else znak[j]=1-trZnak; }
///cout<<mid<<":"<<endl;
///ispisi(znak);
///cout<<tryCombination(znak)<<endl;
int kombinacija=tryCombination(znak);
if (kombinacija>i || kombinacija==-1)
{
gde[i]=mid;
r=mid-1;
}
else l=mid+1;
}
znak[gde[i]]=trZnak;
nadjen[gde[i]]=true;
koga[gde[i]]=i;
///cout<<"gde? "<<gde[i]<<endl;
}
answer(znak, koga);
}
