#include <vector>
#include <utility>
// The signature from the grader
std::pair<std::vector<int>, long long> transaction(long long M);
int n;
long long p[105];
int cnt[105];
void solve(long long val) {
auto res = transaction(val);
std::vector<int> id = res.first;
long long returned_coins = res.second;
// Track what we bought so we don't over-buy in the cleanup phase
for (int x : id) {
cnt[x]--;
}
// Total coins actually spent in this transaction
long long spent = val - returned_coins;
// If the price of the first (most expensive) item bought is unknown
if (!p[id[0]]) {
std::vector<int> tp;
for (int x : id) {
// Subtract known prices to isolate the cost of unknown items
if (p[x]) {
spent -= p[x];
} else {
tp.push_back(x);
}
}
// Average search to isolate the most expensive unknown item
while (tp.size() > 1) {
// This average cleanly skips tp[0] and buys smaller items
solve(spent / tp.size());
// As we recursively discover smaller prices, subtract them out
while (!tp.empty() && p[tp.back()]) {
spent -= p[tp.back()];
tp.pop_back();
}
}
// The single remaining unknown price is exactly the remaining spent coins
p[id[0]] = spent;
}
// Sequentially kick off the search for the next unknown price in the chain
int pos = id[0];
while (pos < n - 1 && p[pos + 1]) {
pos++;
}
if (pos < n - 1) {
solve(p[pos] - 1);
}
}
void buy_souvenirs(int N, long long P0) {
n = N;
p[0] = P0;
for (int i = 1; i < n; i++) {
p[i] = 0;
cnt[i] = i;
}
// Start the discovery chain
solve(P0 - 1);
// Cleanup phase: sequentially buy any remaining exact quantities required
for (int i = 1; i < n; i++) {
while (cnt[i] > 0) {
transaction(p[i]);
cnt[i]--;
}
}
}
