#include"souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const long long inf = 1e9;
long long n,last,p[105],cn[105];
long long hitung(int s, int k){
s += k*(k-1)/2+k-1;
return s/k;
}
void fin(long long initial_money) {
vector<long long> money_stack;
vector<vector<int>> v_stack;
vector<long long> sum_stack;
vector<int> stage_stack;
money_stack.push_back(initial_money);
v_stack.emplace_back();
sum_stack.push_back(0);
stage_stack.push_back(0);
while (!money_stack.empty()) {
int d = money_stack.size() - 1;
if (stage_stack[d] == 0) {
auto [v, remain] = transaction(money_stack[d]);
long long sum = money_stack[d] - remain;
if (!v.empty() && v[0] < last) {
while (!v.empty() && v.back() >= last) {
sum -= p[v.back()];
v.pop_back();
}
}
v_stack[d] = v;
sum_stack[d] = sum;
for (int i : v) cn[i]++;
if (!v.empty() && v[0] < last && v[0] + 1 != last) {
long long new_money = hitung(sum, v.size()) - 1;
money_stack.push_back(new_money);
v_stack.emplace_back();
sum_stack.push_back(0);
stage_stack.push_back(0);
continue;
}
stage_stack[d] = 1;
}
if (stage_stack[d] == 1) {
if (!v_stack[d].empty()) {
int idx = v_stack[d][0];
p[idx] = sum_stack[d];
last = idx;
}
money_stack.pop_back();
v_stack.pop_back();
sum_stack.pop_back();
stage_stack.pop_back();
}
}
}
void buy_souvenirs(int N, long long p0){
memset(cn, 0, sizeof(cn));
memset(p, 0, sizeof(p));
p[0] = p0, n = N;
fin(p0-1);
for(int i = 1; i < N; i++){
while(cn[i] < i){
transaction(p[i]);
cn[i]++;
}
}
}
