#include<bits/stdc++.h>
#include "cave.h"
const int MAXN=5010;
int s[MAXN];
int d[MAXN];
int tryCombination(int s[]);
void answer(int s[],int d[]);
void exploreCave(int n){
/*if(tryCombination(s)==-1){
for(int i=0;i<n;i++){
s[i]=1;
int a=tryCombination(s);
d[i]=a;
s[i]=0;
}
answer(s,d);
}*/
for(int i=0;i<n;i++) d[i]=-1;
for(int i=0;i<n;i++){
int x;
if(tryCombination(s)==i) x=0;
else x=1;
int ini=0,fim=n-1;
while(ini!=fim){
int i0=ini;
int m=(ini+fim)/2;
for(int j=ini;j<=m;j++){
if(d[j]!=-1) continue;
s[j]=!s[j];
}
if(x==0){
if(tryCombination(s)==i) ini=m+1;
else fim=m;
}
if(x==1){
if(tryCombination(s)!=i) ini=m+1;
else fim=m;
}
for(int j=i0;j<=m;j++){
if(d[j]!=-1) continue;
s[j]=!s[j];
}
}
if(x==0) s[fim]=1;
d[fim]=i;
}
answer(s,d);
/*for(int i=0;i<n;i++){
d[i]=i;
if(tryCombination(s)==i) s[i]=1;
}
answer(s,d);*/
}
