#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N;
ll price[105]; // price[i] = P[i], chưa biết thì = 0
int need[105]; // còn cần mua bao nhiêu món loại i
void solve_query(ll M) {
pair<vector<int>, ll> res = transaction(M);
vector<int> ids = res.first;
ll rem = res.second;
ll sum = M - rem; // tổng giá các món vừa mua
// Mỗi món vừa mua đều được tính vào số lượng đã mua
for (int x : ids) need[x]--;
// Nếu loại đầu tiên trong ids còn chưa biết giá
if (price[ids[0]] == 0) {
vector<int> unknown;
ll curSum = sum;
// bỏ các giá đã biết ra khỏi tổng
for (int x : ids) {
if (price[x] != 0) curSum -= price[x];
else unknown.push_back(x);
}
// nếu còn nhiều hơn 1 giá chưa biết
while ((int)unknown.size() > 1) {
solve_query(curSum / (ll)unknown.size());
// sau truy vấn con, có thể đã xác định được vài giá ở cuối
while (!unknown.empty() && price[unknown.back()] != 0) {
curSum -= price[unknown.back()];
unknown.pop_back();
}
}
// còn đúng 1 loại chưa biết => suy ra giá
price[unknown[0]] = curSum;
}
// Nếu đã biết liên tiếp từ ids[0] tới đâu đó,
// thử query giá nhỏ hơn 1 để "đẩy" sang loại chưa biết tiếp theo
int pos = ids[0];
while (pos + 1 < N && price[pos + 1] != 0) pos++;
if (pos + 1 < N) {
solve_query(price[pos] - 1);
}
}
void buy_souvenirs(int n, long long P0) {
N = n;
memset(price, 0, sizeof(price));
memset(need, 0, sizeof(need));
price[0] = P0;
// cần mua đúng i món loại i, với i >= 1
for (int i = 1; i < N; i++) need[i] = i;
// bắt đầu từ truy vấn lớn nhất hợp lệ
solve_query(P0 - 1);
// sau khi đã biết hết giá, mua bù cho đủ số lượng
for (int i = 1; i < N; i++) {
while (need[i] > 0) {
pair<vector<int>, ll> res = transaction(price[i]);
for (int x : res.first) need[x]--;
}
}
}
