#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;
}
void kur(int x){
pair<vector<int>, ll> res = transaction(x);
vector<int> v = res.first;
for(auto u: v)cnt[u]++;
ll sum = x - res.second;
reduce(v, sum);
if(v.size() == 0)return;
while(v.size() > 1){
kur(sum / (v.size()));
reduce(v, sum);
}
ans[v[0]] = sum;
}
void buy_souvenirs(int n, long long P0) {
memset(ans, -1, sizeof ans);
ans[0] = P0;
while(1){
bool b = 1;
for(int i = 1;i < n;i++){
if(ans[i] == -1){
kur(ans[i - 1] - 1);
b = 0;
break;
}
}
if(b)break;
}
for(int i = 1;i < n;i++){
for(int j = 0;j < i - cnt[i];j++)transaction(ans[i]);
}
}
