#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N_MAX = 100 + 11;
bool used[N_MAX][N_MAX], eq[N_MAX][N_MAX];
int sum[N_MAX], P[N_MAX];
int _transaction(int pay) {
// cout << "TRANS " << pay << endl;
auto [C, rem] = transaction(pay);
assert(!C.empty());
for (int i = 0; i < (int) C.size(); i++) {
used[C[0]][C[i]] = eq[C[0]][C[i]] = true;
}
int cost = pay - rem;
sum[C[0]] = cost;
return C[0];
}
void solve(int N) {
if (N == 0) return;
int prv = -1, cnt = 1;
for (int j = N - 1; j >= 0; j--) {
if (eq[j][j]) {
prv = j;
cnt = accumulate(eq[j] + j, eq[j] + N, 0LL);
break;
}
}
assert(prv >= 0);
while (prv < N - 1) {
int r = _transaction((sum[prv] - 1) / cnt);
prv = r;
cnt = accumulate(eq[prv] + prv, eq[prv] + N, 0LL);
}
P[N - 1] = sum[N - 1];
for (int i = 0; i < N; i++) {
if (eq[i][N - 1]) eq[i][N - 1] = false, sum[i] -= P[N - 1];
}
solve(N - 1);
}
void buy_souvenirs(int32_t N, int P0) {
eq[0][0] = 1; sum[0] = P[0] = P0;
solve(N);
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j++) {
if (!used[i][j]) {
_transaction(P[j]);
}
}
}
}
