#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void buy_souvenirs(int N, ll P0) {
vector<ll> price(N, -1); // price[i] = P[i]
vector<int> bought(N, 0); // đã mua bao nhiêu món loại i
vector<vector<int>> group(N); // group[s] = dãy loại mua được trong 1 query bắt đầu từ s
vector<ll> groupSum(N, 0); // tổng giá các loại CHƯA BIẾT trong group[s]
price[0] = P0;
group[0] = {0};
groupSum[0] = P0;
auto normalize = [&](int s) {
if (group[s].empty()) return;
vector<int> remain;
ll sum = groupSum[s];
for (int x : group[s]) {
if (price[x] != -1) sum -= price[x];
else remain.push_back(x);
}
group[s] = remain;
groupSum[s] = sum;
if ((int)group[s].size() == 1) {
int x = group[s][0];
price[x] = groupSum[s];
}
};
auto choose_coins = [&](int cnt, ll sum) -> ll {
if (cnt == 1) return sum - 1;
return sum / cnt;
};
int target = N - 1; // đang cần tìm giá lớn nhất có chỉ số lớn nhất mà chưa biết
int cur = 0;
while (target > 0) {
while (cur != target) {
ll M = choose_coins((int)group[cur].size(), groupSum[cur]);
auto res = transaction(M);
vector<int> vec = res.first;
ll rem = res.second;
for (int x : vec) bought[x]++;
int start = vec[0];
group[start] = vec;
groupSum[start] = M - rem;
normalize(start);
cur = start;
}
for (int i = N - 1; i >= 1; i--) {
if (!group[i].empty()) normalize(i);
}
while (target > 0 && price[target] != -1) target--;
cur = target;
while (cur > 0 && group[cur].empty()) cur--;
}
for (int i = 1; i < N; i++) {
while (bought[i] < i) {
transaction(price[i]);
bought[i]++;
}
}
}
