#include "souvenirs.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 105;
int N, last, buy[MAXN], bp[MAXN];
ll P[MAXN];
bitset <MAXN> B[MAXN];
pair <vector<int>,ll> res;
void dapat(int id) {
while (last && bp[last] == 1) {
last--;
}
for (int i=1;i<id;i++) {
if (B[i][id]) {
B[i][id] = 0;
P[i] -= P[id];
bp[i]--;
if (bp[i] == 1) {
dapat(i);
}
}
}
}
void beli(ll M) {
res = transaction(M);
int id = res.fi[0];
P[id] = M-res.se;
for (int x : res.fi) {
if (bp[x] == 1) {
P[id] -= P[x];
}
else {
B[id][x] = 1;
bp[id]++;
}
buy[x]++;
}
if (bp[id] == 1) {
dapat(id);
}
}
void buy_souvenirs(int n, long long P0) {
N = n;
P[0] = P0;
bp[0] = 1;
last = N-1;
while (last) {
for (int i=last;i>=0;i--) {
if (bp[i]) {
beli((P[i]-1)/bp[i]);
break;
}
}
}
for (int i=1;i<N;i++) {
while (buy[i] < i) {
buy[i]++;
transaction(P[i]);
}
}
}
