#include<bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
void buy_souvenirs(int n, long long int P0) {
vector<int> cnt(n, 0);
vector<long long int> val(n, -1);
val[0] = P0;
vector<long long int> total(n, -1);
vector<vector<int>> hist(n);
while (true) {
bool done = true;
for (int i = 0; i < n; i++) if (val[i] == -1) done = false;
if (done) break;
bool flag = false;
int idx;
for (int i = n - 1; i >= 0; i--) {
if (val[i] == -1 && total[i] == -1) flag = true;
else if (flag || total[i] != -1) {
idx = i;
break;
}
}
long long int query;
if (val[idx] != -1) query = val[idx] - 1;
else {
vector<int> nxt;
for (auto i: hist[idx]) {
if (val[i] == -1) nxt.push_back(i);
else total[idx] -= val[i];
}
hist[idx] = move(nxt);
int a = hist[idx].size();
if (a == 1) {
val[idx] = total[idx];
total[idx] = -1;
continue;
}
long long int b = total[idx];
for (int i = 0; i < a - 1; i++) {
b -= hist[idx].back() - hist[idx][i];
}
query = b / a;
}
auto [list, left] = transaction(query);
for (auto i: list) cnt[i]++;
idx = list[0];
hist[idx] = list;
total[idx] = query - left;
}
for (int i = 0; i < n; i++) {
for (int j = cnt[i]; j < i; j++) transaction(val[i]);
}
}
