#include "souvenirs.h"
#include <vector>
#include <utility>
void buy_souvenirs(int N, long long P0) {
// N = 3 in the official tests.
// For completeness we also handle N = 1 and N = 2.
if (N == 1) {
// Need 0 souvenirs of type 0 → do nothing.
return;
}
if (N == 2) {
// Need exactly one souvenir of type 1.
// A single transaction with M = P0 - 1 always buys type 1
// (and never type 0 because M < P0).
long long M = P0 - 1;
transaction(M);
return;
}
// ----------- N == 3 ---------------------------------
// First transaction: M = P0 - 1.
// It always buys at least one souvenir of type 1.
long long M0 = P0 - 1;
auto first = transaction(M0);
std::vector<int> L0 = first.first; // types bought in this transaction
long long R0 = first.second; // coins returned
// Does the first transaction already give us a souvenir of type 2 ?
bool got_type2 = false;
for (int t : L0) if (t == 2) { got_type2 = true; break; }
if (got_type2) {
// We have bought 1 of type 1 and 1 of type 2.
// Need one more type 2. Compute P1 + P2.
long long sum0 = M0 - R0; // = P1 + P2
long long M2 = sum0 / 2; // floor((P1+P2)/2)
// M2 is < P1 and ≥ P2, therefore the seller will give us exactly one type 2.
transaction(M2);
// Now we have 1×type 1 and 2×type 2 → done.
} else {
// Only type 1 was bought. We need two type 2.
// From the first transaction we already know P1.
long long sum0 = M0 - R0; // = P1
long long P1 = sum0;
long long Mtype2 = P1 - 1; // ≥ P2 and < P1
// Buy type 2 twice.
transaction(Mtype2);
transaction(Mtype2);
// Now we have 1×type 1 and 2×type 2 → done.
}
}
