//testing AI Code
#include "souvenirs.h"
#include <vector>
#include <algorithm>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<long long> P(N);
P[0] = P0;
// Discover all prices
// Start by finding P[N-1] using binary search
long long low = 1, high = P0 - 1;
// Find P[N-1] - the minimum price
while (low < high) {
long long mid = (low + high) / 2;
auto result = transaction(mid);
if (result.first.empty()) {
// mid < P[N-1]
low = mid + 1;
} else {
// mid >= P[N-1]
high = mid;
}
}
P[N-1] = low;
// Discover other prices from top to bottom
for (int i = 1; i < N - 1; i++) {
// Find P[i] by testing values between P[i-1]-1 and P[N-1]
low = P[N-1];
high = P[i-1] - 1;
while (low < high) {
long long mid = (low + high + 1) / 2;
auto result = transaction(mid);
// Check if we bought type i
bool bought_i = false;
for (int t : result.first) {
if (t == i) {
bought_i = true;
break;
}
}
if (bought_i) {
// mid >= P[i]
low = mid;
} else {
// mid < P[i]
high = mid - 1;
}
}
P[i] = low;
}
// Now we know all prices, buy the required souvenirs
// For type i, we need i souvenirs
vector<int> remaining(N);
for (int i = 0; i < N; i++) {
remaining[i] = i;
}
// Buy souvenirs optimally
while (true) {
bool done = true;
for (int i = 1; i < N; i++) {
if (remaining[i] > 0) {
done = false;
break;
}
}
if (done) break;
// Calculate optimal amount to spend
long long amount = 0;
for (int i = 1; i < N; i++) {
if (remaining[i] > 0) {
amount += P[i];
}
}
// Make sure amount is valid (< P[0] and >= P[N-1])
if (amount >= P[0]) {
// Buy one at a time for remaining types
for (int i = 1; i < N; i++) {
while (remaining[i] > 0) {
auto result = transaction(P[i]);
for (int t : result.first) {
remaining[t]--;
}
}
}
break;
}
auto result = transaction(amount);
for (int t : result.first) {
remaining[t]--;
}
}
}
