#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 _N;
int _transaction(int pay) {
// cout << "TRANS " << pay << endl;
auto [C, rem] = transaction(pay);
assert(!C.empty());
int cost = pay - rem;
sum[C[0]] = cost;
for (int i = 0; i < (int) C.size(); i++) {
used[C[0]][C[i]] = eq[C[0]][C[i]] = true;
if (i > 0 && P[C[i]] && eq[C[0]][C[i]]) {
eq[C[0]][C[i]] = false, sum[C[0]] -= P[C[i]];
}
}
// for (int i = 0; i < _N; i++) {
// for (int j = 0; j < _N; j++) {
// cout << eq[i][j] << ' ';
// }
// cout << ' ';
// cout << sum[i] << ' ';
// cout << P[i] << ' ';
// cout << '\n';
// }
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;
}
}
// cout << "prv = " << prv << endl;
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 - 1; 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) {
_N = N;
eq[0][0] = 1; sum[0] = P[0] = P0;
solve(N);
// for (int i = 0; i < _N; i++) {
// for (int j = 0; j < _N; j++) {
// cout << used[i][j] << ' ';
// }
// cout << '\n';
// }
// for (int i = 0; i < _N; i++) {
// cout << P[i] << ' ';
// }
// cout << '\n';
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j++) {
if (!used[i][j]) {
transaction(P[j]);
}
}
}
}
