#include "souvenirs.h"
// #include "debug.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
void buy_souvenirs(int N, long long P0) {
vector<ll> p(N, -1);
vector<int> cnt(N);
p[0] = P0;
vector<set<int>> dep(N);
vector<ll> sum(N);
while (1) {
int left = N;
for (int i = 0; i < N; ++i) {
left -= p[i] != -1;
}
if (left == 0) break;
bool f = 0;
// dbg(p);
// dbg(cnt);
for (int i = 0; i < N; ++i) {
set<int> st;
for (int j : dep[i]) {
if (p[j] != -1) {
sum[i] -= p[j];
} else {
st.insert(j);
}
}
dep[i].swap(st);
// cerr<<i<<":\n";
// dbg(dep[i]);
// dbg(sum[i]);
}
for (int i = N - 1; i >= 0; --i) {
if (p[i] == -1) {
f = 1;
}
if (p[i] != -1 && f) {
auto now = transaction(p[i] - 1);
ll cost = p[i] - 1 - now.second;
set<int> st;
for (int j : now.first) {
cnt[j] += 1;
if (p[j] != -1) cost -= p[j];
else st.insert(j);
}
dep[i+1] = st;
sum[i+1] = cost;
break;
}
if (sz(dep[i]) == 1) {
p[i]=sum[i];
dep[i].clear();
break;
}
if (sz(dep[i]) > 1) {
ll ask = sum[i] / sz(dep[i]);
auto now = transaction(ask);
set<int> st;
ask -= now.second;
for (int j : now.first) {
cnt[j] += 1;
if (p[j] != -1) ask -= p[j];
else st.insert(j);
}
dep[*begin(st)] = st;
sum[*begin(st)] = ask;
break;
}
}
}
for (int i = 0; i < N; ++i) {
assert(p[i] != -1);
while (cnt[i]++ < i) {
// dbg(transaction(p[i]));
transaction(p[i]);
}
}
}
