#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
#define ll long long
const int N = 105;
using namespace std;
ll ans[N];
int cnt[N];
void reduce(vector<int> &v, ll& sum){
vector<int> g;
for(auto u: v){
if(ans[u] != -1)sum -= ans[u];
else g.push_back(u);
}
v = g;
}
int n;
void kur(ll x){
pair<vector<int>, ll> res = transaction(x);
vector<int> v = res.first;
for(auto u: v)cnt[u]++;
ll sum = x - res.second;
if(ans[v[0]] == -1){
reduce(v, sum);
while(v.size() > 1){
kur(sum / (ll)v.size());
reduce(v, sum);
}
ans[v[0]] = sum;
}
for(int i = v[0];i < n;i++){
if(ans[i] == -1){
kur(ans[i - 1] - 1);
break;
}
}
}
void buy_souvenirs(int _n, long long P0) {
n = _n;
memset(ans, -1, sizeof ans);
ans[0] = P0;
kur(P0 - 1);
for(int i = 1;i < n;i++){
for(int j = 0;j < i - cnt[i];j++)transaction(ans[i]);
}
}
