#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; }