#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
struct Equation {
vector<int> L; // indices of bought types
long long sum; // M - R = Σ_{i∈L} P[i]
};
void buy_souvenirs(int N, long long P0) {
// ------------------------------------------------------------
// data
vector<long long> price(N, -1); // unknown -> -1, price[0] known
price[0] = P0;
vector<int> need(N, 0); // need[i] = i
for (int i = 0; i < N; ++i) need[i] = i;
vector<int> have(N, 0); // already bought copies
vector<Equation> eqs; // all equations obtained
long long UB = P0 - 1; // safe upper bound for the cheapest unknown
// ------------------------------------------------------------
// Phase A – discover all prices
while (true) {
bool allKnown = true;
for (int i = 1; i < N; ++i)
if (price[i] == -1) { allKnown = false; break; }
if (allKnown) break; // finished
// ----- perform a safe transaction -----
auto res = transaction(UB);
const vector<int> &L = res.first;
long long R = res.second;
// update bought counters
for (int idx : L) {
// type 0 must never appear, but we ignore it if it does
if (idx == 0) continue;
++have[idx];
}
long long sum = UB - R; // Σ P[i] of the bought types
eqs.push_back({L, sum});
// ----- try to deduce new prices -----
bool changed = true;
while (changed) {
changed = false;
for (auto &e : eqs) {
long long knownSum = 0;
int unknownCnt = 0;
int unknownIdx = -1;
for (int idx : e.L) {
if (price[idx] != -1) knownSum += price[idx];
else {
++unknownCnt;
unknownIdx = idx;
}
}
if (unknownCnt == 1) {
long long val = e.sum - knownSum;
if (price[unknownIdx] == -1) {
price[unknownIdx] = val;
changed = true;
}
}
}
}
// ----- compute a new safe upper bound -----
long long newUB = P0 - 1; // start with a trivial bound
// from equations (average of still unknown part)
for (const auto &e : eqs) {
long long knownSum = 0;
int unknownCnt = 0;
for (int idx : e.L) {
if (price[idx] != -1) knownSum += price[idx];
else ++unknownCnt;
}
if (unknownCnt > 0) {
long long cand = (e.sum - knownSum) / unknownCnt;
if (cand < newUB) newUB = cand;
}
}
// from already known, more expensive prices
int maxUnknown = -1; // largest index still unknown
for (int i = N - 1; i >= 1; --i)
if (price[i] == -1) { maxUnknown = i; break; }
if (maxUnknown != -1) {
for (int i = 1; i < maxUnknown; ++i) // more expensive known prices
if (price[i] != -1) {
long long cand = price[i] - 1;
if (cand < newUB) newUB = cand;
}
}
if (newUB < 1) newUB = 1; // never zero
UB = newUB;
}
// ------------------------------------------------------------
// Phase B – buy the remaining copies (now all prices are known)
for (int i = 1; i < N; ++i) {
while (have[i] < need[i]) {
// one copy of type i
transaction(price[i]); // the returned list must be {i}, R = 0
++have[i];
}
}
}
