#include <bits/stdc++.h>
#include "souvenirs.h"
#include <utility>
#include <vector>
using namespace std;
long long LIM;
long long p[105];
long long cnt[105];
long long last = 1000;
void solve(long long x) {
auto [v,res] = transaction(x);
for (auto y:v) cnt[y]++;
long long c = x - res;
long long n = v.size();
while (v.back() >= last) {
c -= p[v.back()];
n--;
v.pop_back();
}
while (n > 1) {
solve(c/n);
while (v.back() >= last) {
n--;
c -= p[v.back()];
v.pop_back();
}
}
p[v.back()] = c;
if (c > 1 && v.back() + 1< last && v.back() < LIM) solve(c-1);
last = v.back();
}
void buy_souvenirs(int N, long long P0) {
LIM = N-1;
p[0] = P0;
solve(P0-1);
for (int i = 0; i < N; i++) {
while (cnt[i] < i) cnt[i]++,transaction(p[i]);
}
return;
}
