#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> p;
vector<int> num;
vector<pair<set<int>, ll>> res;
void buy(ll m){
auto [items, coins] = transaction(m);
coins = m-coins;
set<int> s;
for (int item : items){
num[item]++;
if (p[item] != -1) coins -= p[item];
else s.insert(item);
}
res.push_back({s, coins});
}
void buy_souvenirs(int N, ll P0) {
int n = N;
res.clear();
p.assign(n, -1);
p[0] = P0;
num.assign(n, 0);
while (true){
if (res.empty()){
int gap = false;
for (int i=n-1; i>=0; i--){
if (p[i] == -1) gap = true;
else if (gap){
buy(p[i]-1);
break;
}
}
if (!gap) break;
}
else {
if (res.back().first.size() == 0) res.pop_back();
else if (res.back().first.size() == 1){
int i = *res.back().first.begin();
p[i] = res.back().second;
res.pop_back();
for (int j=0; j<res.size(); j++){
if (res[j].first.find(i) != res[j].first.end()){
res[j].first.erase(i);
res[j].second -= p[i];
}
}
if (i < n-1 && p[i+1] == -1) buy(p[i]-1);
}
else buy(res.back().second/(ll)res.back().first.size());
}
}
for (int i=0; i<n; i++){
while (num[i] != i){
transaction(p[i]);
num[i]++;
}
}
return;
}
