//testing AI CODe
#include "souvenirs.h"
#include <vector>
#include <algorithm>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<long long> prices(N);
prices[0] = P0;
vector<int> bought(N, 0);
// Strategy: Discover prices by binary search, then buy exact amounts needed
// Step 1: Find P[N-1] (the cheapest item)
long long lo = 1, hi = P0 - 1;
while (lo < hi) {
long long mid = (lo + hi) / 2;
auto result = transaction(mid);
// Update bought counts
for (int item : result.first) {
bought[item]++;
}
if (result.first.empty() || result.first.back() < N - 1) {
// Didn't buy item N-1, so mid < P[N-1]
lo = mid + 1;
} else {
// Bought item N-1, so mid >= P[N-1]
hi = mid;
}
}
prices[N - 1] = lo;
// Step 2: Find other prices by testing specific amounts
// Key insight: If we pay exactly sum of prices from i to N-1,
// we buy exactly items i through N-1
for (int i = N - 2; i >= 1; i--) {
// Binary search for P[i]
lo = prices[N - 1];
hi = (i == 1) ? (P0 - 1) : prices[i - 1] - 1;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
// Test: pay mid + (sum of prices from i+1 to N-1)
long long test_amount = mid;
for (int j = i + 1; j < N; j++) {
test_amount += prices[j];
}
// Make sure test_amount is valid
if (test_amount >= P0) {
// Just test mid alone
auto result = transaction(mid);
for (int item : result.first) {
bought[item]++;
}
// Check if item i was bought
bool bought_i = false;
for (int item : result.first) {
if (item == i) {
bought_i = true;
break;
}
}
if (bought_i) {
lo = mid;
} else {
hi = mid - 1;
}
} else {
auto result = transaction(test_amount);
for (int item : result.first) {
bought[item]++;
}
// If we bought item i, then mid >= P[i]
bool bought_i = false;
for (int item : result.first) {
if (item == i) {
bought_i = true;
break;
}
}
if (bought_i) {
// We can deduce the price from what was bought
long long total_spent = test_amount - result.second;
long long known_sum = 0;
for (int item : result.first) {
if (item > i) {
known_sum += prices[item];
}
}
prices[i] = total_spent - known_sum;
break;
} else {
hi = mid - 1;
}
}
}
if (prices[i] == 0) {
prices[i] = lo;
}
}
// Step 3: Buy remaining souvenirs to meet quotas
// We need exactly i souvenirs of type i
for (int i = 1; i < N; i++) {
while (bought[i] < i) {
auto result = transaction(prices[i]);
for (int item : result.first) {
bought[item]++;
}
}
}
}
