#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll price[100];
int cnt[100],n;
tuple<vector<bool>,ll,int,ll> buy(ll x){
auto [v,p]=transaction(x);
vector<bool>v1(n,false);
for(int i:v){cnt[i]++;v1[i]=true;}
return{v1,x-p,v.size(),v[0]};
}
void dfs(ll x){
auto [v,p,c,v0]=buy(x);
do{
for(int i=v0+1;i<n;i++){
if(price[i]!=-1&&v[i]){
v[i]=false;
p-=price[i];
c--;
}
}
if(c==1){
price[v0]=p;
bool flag=false;
for(int i=v0+1;i<n;i++){
if(price[i]==-1){flag=true;break;}
}
if(flag)dfs(p-1);
return;
}
dfs(p/c);
}while(c!=1);
}
void buy_souvenirs(int N, long long P0) {
n=N;
for(int i=0;i<n;i++){price[i]=-1;cnt[i]=0;}
price[0]=P0;
dfs(P0-1);
for(int i=1;i<n;i++){
for(int j=cnt[i];j<i;j++){
buy(price[i]);
}
}
}
