#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 105;
int n, last_idx;
ll p[MAXN];
int cnt_visit[MAXN];
struct Frame {
ll money;
vector<int> v;
ll sum;
int stage;
};
ll calc_next(ll s, int k) {
s += (ll)k * (k - 1) / 2 + k - 1;
return s / k;
}
void build_iterative(ll initial_money) {
vector<Frame> stk;
stk.reserve(MAXN);
stk.push_back({initial_money, {}, 0, 0});
while (!stk.empty()) {
Frame &f = stk.back();
if (f.stage == 0) {
auto [v, remain] = transaction(f.money);
ll s = f.money - remain;
while (!v.empty() && v.back() >= last_idx) {
s -= p[v.back()];
v.pop_back();
}
f.v = move(v);
f.sum = s;
for (int idx : f.v) cnt_visit[idx]++;
if (!f.v.empty() && f.v[0] < last_idx && f.v[0] + 1 != last_idx) {
ll next_money = calc_next(f.sum, f.v.size()) - 1;
f.stage = 1;
stk.push_back({next_money, {}, 0, 0});
continue;
}
f.stage = 1;
} else {
if (!f.v.empty()) {
int idx = f.v[0];
p[idx] = f.sum;
last_idx = idx;
}
stk.pop_back();
}
}
}
void buy_souvenirs(int N, ll P0) {
n = N;
last_idx = N;
memset(p, 0, sizeof(p));
memset(cnt_visit, 0, sizeof(cnt_visit));
p[0] = P0;
build_iterative(P0 - 1);
for (int i = 1; i < n; ++i) {
while (cnt_visit[i] < i) {
transaction(p[i]);
cnt_visit[i]++;
}
}
}
