#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
using ll = long long;
/*
int costs[5] = {30,21,20,15,6};
pair<vector<int>, ll> transaction(ll m) {
vector<int> res;
for(int i=0;i<5;i++) {
if(costs[i]<=m) {
res.push_back(i);
m -= costs[i];
}
}
return {res, m};
}*/
int n;
void rec(vector<int>&cnt, vector<ll>&cost, int idx, ll cc) {
if(idx>=n) return;
if(~cost[idx]) return;
auto res = transaction(cc-1);
idx = res.first.front();
for(auto&e:res.first)cnt[e]++;
while(res.first.size() > 1) {
if(!(~cost[res.first.back()])) {
rec(cnt, cost, res.first.back(), (cc-1-res.second)/res.first.size()+1);
}
res.second += cost[res.first.back()];
res.first.pop_back();
}
//cout << idx << "->" << cc-1 << "\n";
cost[idx] = cc-1-res.second;
rec(cnt, cost, idx+1, cost[idx]);
}
void buy_souvenirs(int n, ll p0) {
::n=n;
vector<int> cnt(n);
vector<ll> cost(n, -1);
cost[0]=p0;
rec(cnt, cost, 1, p0);
for(int i=0;i<n;i++) {
//cout << cost[i] << " ";
while(cnt[i]<i) {
cnt[i]++;
transaction(cost[i]);
}
}
}
/*
int main() {
// your code goes here
buy_souvenirs(5, 30);
return 0;
}*/
