#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
extern pair<vector<int>, ll> transaction(ll M); // INTERACTIVE!
int N;
ll P0;
vector<ll> price; // Giá của từng loại (từ 0 đến N-1)
void buy_souvenirs(int _N, ll _P0) {
N = _N;
P0 = _P0;
price.resize(N);
price[0] = P0;
// Tìm P[1] đến P[N-1]
for (int i = 1; i < N; ++i) {
ll low = 1, high = price[i - 1] - 1, res = -1;
while (low <= high) {
ll mid = (low + high) / 2;
auto [items, change] = transaction(mid);
if (!items.empty()) {
// Mua được ít nhất 1 món
res = mid - change;
high = mid - 1;
} else {
low = mid + 1;
}
}
price[i] = res;
}
// Mua đúng i món loại i (với i >= 1)
vector<int> count(N, 0);
while (true) {
bool done = true;
ll money = 0;
for (int i = 1; i < N; ++i) {
if (count[i] < i) {
money += price[i];
done = false;
}
}
if (done) break;
if (money >= price[0]) money = price[0] - 1; // Không mua loại 0
auto [items, change] = transaction(money);
for (int x : items) {
count[x]++;
}
}
}
