#include "souvenirs.h"
#include <set>
#include <utility>
#include <vector>
long long p[105];
int own[105];
void recurse(std::vector<int> items, long long price, int n) {
while (true) {
long long known_price = 0;
std::set<int> unknown(items.begin(), items.end());
for (int i : items) {
if (p[i]) {
known_price += p[i];
unknown.erase(i);
}
}
if (unknown.size() == 0) {
return;
}
if (unknown.size() == 1) {
p[*unknown.begin()] = price - known_price;
if (*unknown.begin() == n - 1) {
return;
}
}
const long long query = (price - known_price - 1) / unknown.size();
const auto& [received, change] = transaction(query);
for (int i : received) {
own[i]++;
}
recurse(received, query - change, n);
}
}
void buy_souvenirs(int n, long long p0) {
for (int i = 0; i < n; i++) {
p[i] = 0;
own[i] = 0;
}
recurse({0}, p0, n);
for (int i = 0; i < n; i++) {
while (own[i] != i) {
transaction(p[i]);
own[i]++;
}
}
}
