#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define ll long long
int n;
ll price[105];
int uses[105];
int solve(int right, ll spend)
{
pair<vector<int>, ll> result = transaction(spend);
for (int x: result.first) {
uses[x]++;
}
int left = result.first[0];
ll amt_spent = spend - result.second;
while (result.first.back() > right) {
amt_spent -= price[result.first.back()];
result.first.pop_back();
}
if (left < right) {
while (true) {
int left2 = solve(right, (amt_spent - 1LL) / (ll)(result.first.size()));
while (result.first.back() >= left2) {
amt_spent -= price[result.first.back()];
result.first.pop_back();
}
if (left2 == left + 1) break;
right = left2 - 1;
}
}
price[left] = amt_spent;
return left;
}
void buy_souvenirs(int N, ll P0) {
n = N;
solve(n - 1, P0 - 1);
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i - uses[i]; j++) {
transaction(price[i]);
}
}
}
