#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int which[5001],N;
int up[5001], isUp[5001];
bool check (int s[], int cur) {
int ret = tryCombination(s);
return ret == -1 || ret > cur;
}
void exploreCave (int n) {
memset(which,-1,sizeof which);
for (int cur = 0; cur < n; cur++) {
for (int x = 0; x < n; x++) {
if (which[x] == -1) up[x] = 0;
else up[x] = isUp[x];
}
bool curup = !check(up,cur);
int low = 0, high = n-1;
while (low < high) {
int mid = (low+high)>>1;
for (int x = low; x <= mid; x++) if (which[x] == -1) up[x] = curup;
for (int x = mid+1; x <= high; x++) if(which[x] == -1) up[x] = !curup;
if (check(up,cur)) high = mid;
else low = mid+1;
}
which[low] = cur;
isUp[low] = curup;
}
answer(isUp,which);
}
