#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
vector<int> costs;
vector<int> luate;
int n;
void buy(int pret) {
auto x = transaction(pret);
int cost = pret - x.second;
for (auto i : x.first)
luate[i] ++;
vector<int> suv;
for (auto i : x.first) {
if (costs[i] != -1)
pret -= costs[i];
else
suv.push_back(i);
}
while ((int)suv.size() > 1) {
int ncost = cost / (int)suv.size();
for (int i = n - 2; i >= 0; i --) {
if (costs[i] != -1 && costs[i + 1] == -1)
ncost = min(ncost, costs[i] - 1);
}
buy(ncost);
vector<int> nsuv;
for (auto i : suv) {
if (costs[i] != -1)
pret -= costs[i];
else
nsuv.push_back(i);
}
suv = nsuv;
}
if ((int)suv.size() == 1)
costs[suv[0]] = cost;
}
void buy_souvenirs(signed N, int p0) {
n = N;
costs.assign(n, -1);
luate.assign(n, 0);
costs[0] = p0;
while (1) {
for (int i = 1; i < n; i ++) {
if (costs[i] == -1)
buy(i - 1);
}
}
for (int i = 1; i < n; i ++)
while (luate[i] < i) {
luate[i] ++;
transaction(costs[i]);
}
}
