#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x).size()
const int MAXN = 105;
int N;
int P[MAXN], rhs[MAXN], cnt[MAXN];
bool equation[MAXN][MAXN];
int build_equation(int M) {
auto [items, leftover] = transaction(M);
if (items.empty()) exit(0);
int total = M - leftover;
int base = items[0];
rhs[base] = total;
cnt[base]++;
for (int i : items) {
equation[base][i] = true;
if (i != base) {
cnt[i]++;
if (P[i] && equation[base][i]) {
equation[base][i] = false;
rhs[base] -= P[i];
}
}
}
return base;
}
void buy_souvenirs(signed num, int P0) {
N = num;
equation[0][0] = true;
rhs[0] = P0; P[0] = P0;
int cur = N;
while (cur != 0) {
int pivot = -1, k = 1;
for (int i = cur - 1; i >= 0; --i) {
if (equation[i][i]) {
pivot = i;
k = accumulate(equation[i] + i, equation[i] + cur, 0LL);
break;
}
}
if (pivot == -1) exit(0);
while (pivot < cur - 1) {
pivot = build_equation((rhs[pivot] - 1) / k);
k = accumulate(equation[pivot] + pivot, equation[pivot] + cur, 0LL);
}
P[cur - 1] = rhs[cur - 1];
for (int i = 0; i < cur - 1; ++i) {
if (equation[i][cur - 1]) {
equation[i][cur - 1] = 0;
rhs[i] -= P[cur - 1];
}
}
--cur;
}
for (int i = 1; i < N; ++i) {
while (cnt[i] < i) {
transaction(P[i]);
cnt[i]++;
}
}
}
