#include "souvenirs.h"
#include <map>
#include <iostream>
using namespace std;
using ll = long long;
int n;
ll p[100], cnt[100];
bool flag[100];
map<ll, pair<vector<int>, ll>> ma;
ll calc(pair<vector<int>, ll>& x) {
ll l = 0, r = x.second, mid = 0, ret = -1;
while (l < r) {
mid = (l + r) >> 1;
ll cur = 0;
for (auto e: x.first) cur += mid - e + x.first[0];
if (cur < x.second) ret = mid, l = mid + 1;
else r = mid - 1;
}
if (ret == -1) {
for (int i =0; i < 1e9; i++) cerr << "fkld;ahjflkajh;dflkjdaskl;dfjdklajflak;djsf";
}
return ret;
}
pair<vector<int>, ll> buy(ll m) {
pair<vector<int>, ll> ret;
vector<int> a;
if (ma.count(m)) ret = ma[m];
else {
ma[m] = ret = transaction(m);
for (auto e: ret.first) cnt[e]++;
}
ret.second = m - ret.second;
for (auto e: ret.first) {
if (p[e]) ret.second -= p[e];
else a.push_back(e);
}
return {a, ret.second};
}
void solve(int m) {
if (ma.count(m)) return;
pair<vector<int>, ll> res = buy(m);
flag[res.first[0]] = 1;
while (res.first.size() > 1) {
solve(calc(res));
res = buy(m);
}
if (res.first.size() == 1) {
p[res.first[0]] = res.second;
if (res.first[0] != n-1 && !flag[res.first[0] + 1]) solve(res.second - 1);
}
}
void buy_souvenirs(int N, long long P0) {
n = N;
p[0] = P0;
for (int i = 1; i < n; i++) if (!flag[i]) solve(p[i-1] - 1);
for (int i = 1; i < n; i++) for (int j = 0; j < i-cnt[i]; j++) transaction(p[i]);
}
