#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
struct greateri
{
template<class T>
bool operator()(T const &a, T const &b) const { return a > b; }
};
int visited[5001];
int pos[5001];
int n;
map<string,int>gg;
void exploreCave(int n)
{
memset(visited,-1,sizeof visited);
int high=n;
int low=0;
int k = 0;
int ans1=0,ans2=0;
while(k!=n)
{
high=n-1;
int tab[n]={0};
low=0;
for (int i = 0; i < n; ++i)
{
if(visited[i]==-1)
{tab[i]=0;}
else {tab[i]=pos[i];}
}
ans1=tryCombination(tab);
while(true)
{
string kali;
if(high == low && visited[low]==-1)
{
//debug(low);
tab[high]=1;
ans2 = tryCombination(tab);
break;
}
else if(high==low){/*debug(low);*/break;}
// debugs(high,low);
int mid=((high+low)/2)+1;
//debug(kali);
/*if(gg.find(kali)!=gg.end())ans1=gg[kali];
else gg[kali]=tryCombination(tab);
ans1=gg[kali];*/
//kali.clear();
//debugs(mid,high);
for (int i = mid; i <= high; ++i)
{
//debugs(i,visited[i]);
if(visited[i]==-1)
tab[i]=1;
else {tab[i]=pos[i];}
}
for (int i = 0; i < n; ++i)
{
kali.pb((char)(tab[i]+48));
}
/*debug(kali);
if(gg.find(kali)!=gg.end())ans2=gg[kali];
else gg[kali]=tryCombination(tab);
ans2=gg[kali];*/
ans2=tryCombination(tab);
if(ans1==ans2)
{
high=mid-1;
}
else
{
low=mid;
}
}
if(ans1==-1)ans1=n;
if(ans2==-1)ans2=n;
//debugs(low,min(ans1,ans2));
visited[low]=min(ans2,ans1);
if(ans1>ans2)
{
pos[low]=0;
}
else pos[low]=1;
k++;
}
answer(pos,visited);
return;
}
