#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e2+5;
ll p[nx];
int cnt[nx];
vector<int> item[nx];
ll spend[nx];
void reeval(int idx)
{
vector<int> newitem;
for (auto i:item[idx])
{
if (p[i]) spend[idx]-=p[i];
else newitem.push_back(i);
}
item[idx]=newitem;
}
void buy(ll x) // return lead
{
auto [it, lft]=transaction(x);
int f=it[0];
spend[f]=x-lft;
item[f]=it;
for (auto u:it) cnt[u]++;
reeval(f);
}
void trybuy(int idx)
{
int p=idx;
while (item[p].empty()) p--;
reeval(p);
ll newval=0;
if (item[p].size()==1) newval=spend[p]-1;
else newval=spend[p]/item[p].size();
buy(newval);
}
void buy_souvenirs(int N, long long P0) {
p[0]=P0;
buy(P0-1);
for (int i=N-1; i>=1; i--)
{
while (item[i].empty()) trybuy(i);
p[i]=spend[i];
}
for (int i=0; i<N; i++) while (cnt[i]<i) transaction(p[i]), cnt[i]++;
}
