#include "souvenirs.h"
#include <bits/stdc++.h>
#include <utility>
#include <vector>
using ll=long long;
using namespace std;
#define vi vector<int>
#define vl vector<ll>
using call= pair<vi,ll>;
#define pi pair<ll,ll>
pi eval(call &c , vl & sol){
auto &[v,sum]=c;
int count=0;
for(int i:v){
if(sol[i]){
sum-=sol[i];
}
else count++;
}
return {sum,count};
}
pair<vi, ll >TRANSACTION(ll M, vi & bought ){
auto [v,l]=transaction(M);
for(int i:v)bought[i]++;
return {v,l};
}
void buy_souvenirs(int N, long long P0) {
vector<ll> sol(N);
sol[0]=P0;
stack<call>s;
vi bought(N);
s.push({vi{0},P0});
while(!s.empty()){
auto c=s.top();
auto [sum,count]=eval(c,sol);
int mean;
if(!count){
int i=c.first[0];
if(i<N-1 && !sol[i+1]){
mean=sol[i]-1;
}
else {
s.pop();
continue;
}
}
else mean=sum/count;
if(count==1){
for(int i:c.first){
if(!sol[i])sol[i]=sum;
}
continue;
}
auto [v,l]=TRANSACTION(mean,bought);
s.push({v,mean-l});
}
for(int i=0;i<N;i++){
while(bought[i]<i){
TRANSACTION(sol[i],bought);
}
}
return;
}
