#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
void buy_souvenirs(int n, long long p0) {
vector<set<int>> sts(n);
vector<long long> sums(n), ans(n, -1);
ans[0] = p0;
vector<int> ops(n);
while (count(ans.begin(), ans.end(), -1)) {
bool miss = false; // u da real miss
for (int i = n - 1; i >= 0; i--) {
if (ans[i] == -1) {
miss = true;
}
if (ans[i] != -1 && miss) {
auto [v, l] = transaction(ans[i] - 1);
set<int> s;
for (int x : v) {
s.insert(x);
ops[x] += 1;
}
long long got = ans[i] - 1 - l;
for (int j = 0; j < n; j++) {
if (ans[j] != -1 && s.find(j) != s.end()) {
s.erase(j);
got -= ans[j];
}
}
sts[i + 1] = s;
sums[i + 1] = got;
break;
}
if (sts[i].size() == 1) {
ans[i] = sums[i];
sts[i].clear();
for (int j = 0; j < n; j++) {
if (sts[j].count(i)) {
sums[j] -= ans[i];
sts[j].erase(i);
}
}
break;
}
if (sts[i].size()) {
long long x = sums[i] / static_cast<long long>(sts[i].size());
auto [v, l] = transaction(x);
set<int> s;
for (int x : v) {
s.insert(x);
ops[x] += 1;
}
long long got = x - l;
for (int j = 0; j < n; j++) {
if (ans[j] != -1 && s.find(j) != s.end()) {
got -= ans[j];
s.erase(j);
}
}
int k = *s.begin();
sts[k] = s;
sums[k] = got;
break;
}
}
}
for (int i = 0; i < n; i++) {
while (ops[i] < i) {
transaction(ans[i]);
ops[i] += 1;
}
}
return;
}
