#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], sum[MAXN], cnt[MAXN];
bool equation[MAXN][MAXN];
int build_equation(int pay) {
auto [items, leftover] = transaction(pay);
int total = pay - leftover;
int base = items[0];
sum[base] = total;
cnt[base]++;
for (int i : items) {
if (i != base) {
equation[base][i] = true;
cnt[i]++;
if (P[i]) {
equation[base][i] = false;
sum[base] -= P[i];
}
}
}
return base;
}
void buy_souvenirs(signed num, int P0) {
N = num;
equation[0][0] = true;
sum[0] = P[0] = P0;
cnt[0]++;
int known = 1;
while (known < N) {
int pivot = -1, k = 0;
for (int i = N - 1; i >= 0; --i) {
if (equation[i][i]) {
pivot = i;
k = 0;
for (int j = pivot; j < N; ++j)
if (equation[pivot][j]) ++k;
break;
}
}
while (pivot < N - 1) {
int next = build_equation((sum[pivot] - 1) / k);
pivot = next;
k = 0;
for (int j = pivot; j < N; ++j)
if (equation[pivot][j]) ++k;
}
int cur = N - known;
P[cur] = sum[cur];
++known;
for (int i = 0; i < cur; ++i) {
if (equation[i][cur]) {
equation[i][cur] = false;
sum[i] -= P[cur];
}
}
}
for (int i = 1; i < N; ++i) {
while (cnt[i] < i) {
transaction(P[i]);
cnt[i]++;
}
}
}
