#include "souvenirs.h"
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 100;
ll sum[mx+1], val[mx+1], c[mx+1], d, n;
vi who[mx+1];
int buy (ll p) {
pair<vi, ll> res = transaction (p);
int f = res.fi [0];
sum[f] = p - res.se;
who[f] = res.fi;
return f;
}
void go (int i) {
while (true) {
int k = 0;
ll s = 0;
for (int j : who[i]) {
k += val[j] > 0;
s += val[j];
}
if (k == len(who[i])-1) val[i] = sum[i] - s;
if (val[i]) {
if (i == n-1-d) {
++d;
return;
}
else go ( buy ( val[i]-1 ) );
}
else go ( buy ( (sum[i]-s)/(len(who[i])-k) ) );
}
}
void buy_souvenirs(int N, ll P0) {
n = N;
who[0].pb(0);
sum[0] = P0;
val[0] = P0;
go (0);
rep (i,1,N-1) while (c[i] < i) buy (val[i]);
return;
}
