#include <bits/stdc++.h>
#include "koala.h"
using namespace std;
const int MAXN = 105;
int n, w, flg;
int dp[105][105];
int B[MAXN], R[MAXN];
bool f (int ll, int rr, int c) {
vector <int> a, b;
for (int i = n; i >= 1; i--) {
if (ll <= i && i <= rr) {
if (a.empty()) a.push_back(i); else a.push_back(a.back() + i);
} else {
if (b.empty()) b.push_back(i); else b.push_back(b.back() + i);
}
}
vector < pair <int, int> > res;
int mx = -1;
for (int i=0; i<=a.size(); i++) {
for (int j=0; j<=b.size(); j++) {
int cost = i * (c + 1) + j;
int val = 0;
if (i > 0) val += a[i-1];
if (j > 0) val += b[j-1];
if (cost <= w) {
if (val > mx) {
mx = val;
res.clear();
res.push_back(make_pair(i, j));
} else if (val == mx) {
res.push_back(make_pair(i, j));
}
}
}
}
for (auto par : res) {
if (par.first == 0 || par.first == a.size()) return 0;
}
return 1;
}
int calc (int ll, int rr) {
int len = rr - ll + 1;
int mx = w / len;
for (int i = mx; i >= 1; i--) {
if (f(ll, rr, i)) return i;
}
return -1;
}
void precompute () {
for (int i=1; i<=n; i++) {
for (int j=i+1; j<=n; j++) {
dp[i][j] = calc(i, j);
}
}
}
vector <int> rjesi (int lo, int hi, vector <int> v) {
if (lo == hi) return v;
for (int i=0; i<n; i++) {
B[i] = R[i] = 0;
}
for (auto x : v) {
B[x] = dp[lo][hi];
}
playRound(B, R);
vector <int> lef, rig;
for (auto x : v) {
if (R[x] > B[x]) rig.push_back(x); else lef.push_back(x);
}
if (flg == 0) lef = rjesi(lo, lo + lef.size() - 1, lef);
rig = rjesi(lo + lef.size(), hi, rig);
if (flg) return rig;
for (auto x : rig) lef.push_back(x);
return lef;
}
int minValue(int N, int W) {
n = N; w = W;
for (int i=0; i<n; i++) {
B[i] = R[i] = 0;
}
B[0] = 1;
playRound(B, R);
for (int i=0; i<n; i++) {
if (R[i] == 0) return i;
}
}
int maxValue(int N, int W) {
n = N; w = W;
if (flg == 0) precompute();
flg++;
vector <int> sol;
for (int i=0; i<n; i++) sol.push_back(i);
return rjesi(1, n, sol).back();
}
int greaterValue(int N, int W) {
n = N; w = W;
int lo = 1, hi = min(W / 2, 9);
while (lo <= hi) {
int mid = (lo + hi) / 2;
for (int i=0; i<n; i++) {
B[i] = R[i] = 0;
}
B[0] = B[1] = mid;
playRound(B, R);
bool ok0 = R[0] > B[0];
bool ok1 = R[1] > B[1];
if (ok0 == ok1) {
if (ok0 == 1) {
lo = mid + 1;
} else {
hi = mid - 1;
}
} else {
if (ok0) return 0;
return 1;
}
}
}
void allValues(int N, int W, int *P) {
n = N; w = W;
precompute();
vector <int> sol;
for (int i=0; i<n; i++) sol.push_back(i);
sol = rjesi(1, n, sol);
for (int i=0; i<N; i++) {
P[sol[i]] = i + 1;
}
}
