#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
int p[101], cnt[101];
pair<set<int>, int> e[101];
void buy_souvenirs(i32 N, int P0) {
int cur = P0 - 1, smol = 0;
while (smol < N - 1) {
auto [vec, c] = transaction(cur);
c = cur - c;
smol = vec[0];
set<int> temp;
for (auto& x : vec) temp.insert(x), cnt[x]++;
e[smol] = {temp, c};
if (smol == N - 1) {
p[N - 1] = c;
for (int i = 1; i < N; i++) if (e[i].first.count(N - 1)) e[i].second -= c, e[i].first.erase(N - 1);
} else if (temp.size() == 1) cur = c - 1;
else cur = c / temp.size();
}
for (int i = N - 2; i >= 1; i--) {
if (!e[i].first.empty()) {
p[i] = e[i].second;
for (int k = 1; k < N; k++) if (e[k].first.count(i)) e[k].second -= p[i], e[k].first.erase(i);
} else {
int j;
for (j = i; j >= 1; j--) if (!e[j].first.empty()) break;
if (e[j].first.size() == 1) cur = e[j].second - 1;
else cur = e[j].second / e[j].first.size();
while (j < i) {
auto [vec, c] = transaction(cur);
c = cur - c;
j = vec[0];
set<int> temp;
for (auto& x : vec) {
cnt[x]++;
if (p[x] != 0) c -= p[x];
else temp.insert(x);
}
e[j] = {temp, c};
if (j == i) {
p[i] = c;
for (int k = 1; k < N; k++) if (e[k].first.count(i)) e[k].second -= c, e[k].first.erase(i);
} else if (temp.size() == 1) cur = c - 1;
else cur = c / temp.size();
}
}
}
for (int i = 1; i < N; i++) while (cnt[i] < i) transaction(p[i]), cnt[i]++;
}
