#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void buy_souvenirs(int N, long long P0) {
pair<vector<int>, long long> res;
if (N == 2) {
res = transaction(P0-1);
return;
} else if (N == 3) {
res = transaction(P0-1);
if (res.first.size() == 1) {
ll a = P0 - res.second;
transaction(a-2);
transaction(a-2);
} else {
ll a = P0 - res.second-1;
transaction(a/2);
}
return;
}
vector<int> ret(N, 0);
vector<int> prices(N, -1);
prices[0] = P0;
for (int i = 1; i < N; ++i) {
res = transaction(prices[i-1]-1);
if (res.first.size() == 1 && res.second == 0) {
prices[i] = prices[i-1]-1;
} else {
prices[i] = prices[i-1]-2;
}
for (int j : res.first) {
++ret[j];
}
while (ret[i] < i)
{
transaction(prices[i]);
++ret[i];
}
}
return;
}
