//testing AI Code
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
// The provided interface for the interactive problem
std::pair<std::vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
// P_actual will store the determined prices P[1] through P[N-1].
// P_actual[i] will store P[i]. P[0] is already P0.
std::vector<long long> P_actual(N);
P_actual[0] = P0;
// A map to store the determined prices based on the single souvenir bought.
// Key: souvenir type index (i), Value: price P[i]
std::map<int, long long> single_price_map;
// --- Part 1: Determine the prices P[1] through P[N-1] ---
// Constraints on P[i] suggest that P[i] <= 10. Let's use the given P0.
// We only need to check M up to P0 - 1.
// The transaction(M) is guaranteed to buy at least one souvenir only if M >= P[N-1].
// To ensure we get all prices, we check all possible M up to P0 - 1.
// Note: M must be in [P[N-1], P[0] - 1]. Since P[N-1] is unknown, we check M >= 1.
// The problem states P[i] are distinct.
long long max_M = P0 - 1;
// We can try M from 1 up to a small limit, like 10, or P0-1.
// Since N <= 100, P[i] <= 10, then P0 <= 100 for N=100. Let's use P0-1.
for (long long M = 1; M <= max_M; ++M) {
std::pair<std::vector<int>, long long> result = transaction(M);
std::vector<int> L = result.first;
long long R = result.second;
// If only a single souvenir of type i is bought, then P[i] = M - R.
// This is a reliable way to find P[i] because:
// 1. M < P[0] ensures no type 0 is bought.
// 2. If L={i}, M must be < P[j] for all j < i (since they are checked first).
// 3. Since P[j] < P[i] for all j > i, L={i} and R=0 is the ideal case for M=P[i].
// However, if R>0, it means the remaining R coins were not enough to buy P[j] for j>i.
if (L.size() == 1) {
int i = L[0];
long long price = M - R;
// The constraint P[0] > M >= P[N - 1] must be met, but the *problem* is to
// find prices, so we must be able to call transaction(M).
// We only need to check M's that *could* be a single price.
// If P[i] is already found, this M must correspond to a new P[j].
// To be more robust, we should only trust the result if it uniquely identifies a price.
// P[i] = M - R is the price. Since prices are distinct, we can use the determined price.
bool already_found = false;
for(const auto& pair : single_price_map) {
if (pair.second == price) {
already_found = true;
break;
}
}
if (!already_found) {
single_price_map[i] = price;
}
}
}
// Since P[i] are distinct, we collect all found prices and sort them to assign.
std::vector<long long> determined_prices;
for (const auto& pair : single_price_map) {
determined_prices.push_back(pair.second);
}
// If not enough prices are found from the single-souvenir-purchase strategy, we might need
// to include the ones that weren't found. This would be necessary if all prices
// lead to multi-souvenir purchases. Let's assume the single-purchase strategy is enough
// because the distinct prices are small (<= 10).
// Sort in decreasing order to assign P[1], P[2], ...
std::sort(determined_prices.rbegin(), determined_prices.rend());
// Assign to P_actual[1], P_actual[2], ...
for (int i = 1; i < N; ++i) {
// determined_prices size must be N-1. If not, the simple strategy failed.
// With P[i] <= 10, P0 > P1 > ... > P[N-1], and N <= 100, P[i] will be in [1, 9].
// The distinctness forces N-1 prices. The problem constraints are generous.
if (i - 1 < determined_prices.size()) {
P_actual[i] = determined_prices[i - 1];
} else {
// This case should not happen based on constraints and test M=1 to 9.
// If it does, we must assume P[i] is a small number not found, but we can't guess.
// For a safe assumption in a contest, we could take the smallest available.
}
}
// The problem requires at least one souvenir and M >= P[N-1].
long long P_N_minus_1 = P_actual[N - 1];
if (P_N_minus_1 == 0) {
// If not found, a very unlikely scenario under the given constraints.
// We must ensure M >= P[N-1], so a safe M is P[0]-1 if P[N-1] is not 1.
// If P[N-1] = 1, then P_actual[N-1]=1.
// Let's assume P_actual[N-1] is correctly determined and is >= 1.
}
// --- Part 2: Buy the required souvenirs ---
// We need i souvenirs of type i for i = 1 to N-1.
// We will perform i transactions of M = P[i] for each type i.
// Transaction(P[i]) results in ({i}, 0) because P[i] is enough to buy P[i],
// but not P[j] for j < i (since P[i] < P[j]), and not P[j] for j > i (since C=0).
for (int i = 1; i < N; ++i) {
long long M = P_actual[i];
// Safety check: The constraints on M must be met: P[0] > M >= P[N - 1].
// Our M=P[i] is correct because:
// 1. P[0] > P[i] (by price order)
// 2. P[i] >= P[N-1] (by price order)
for (int k = 0; k < i; ++k) {
// Note: the problem does not require to minimize transactions.
transaction(M);
}
}
}
