#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
void buy_souvenirs(int N, long long P0) {
// price[0] is known, other prices will be discovered
vector<long long> price(N);
price[0] = P0;
// need[i] = how many copies of type i we still have to obtain
vector<int> need(N, 0);
for (int i = 0; i < N; ++i) need[i] = i; // type 0 should stay at 0
/* --------------------------------------------------------------
1. Determine the prices for indices 1 .. N-2.
For each i we issue a "probe" transaction with
M = price[i-1] - 2 (always >= cheapest price)
The transaction will buy either type i (if the gap is 2)
or some later type (if the gap is 1). From the first bought
type we can infer the exact gap, thus price[i].
While probing we also count the souvenirs that were bought.
-------------------------------------------------------------- */
for (int i = 1; i <= N - 2; ++i) {
long long M = price[i - 1] - 2; // safe and valid
auto res = transaction(M);
const vector<int> &L = res.first;
// we have bought one souvenir for each type in L
for (int t : L) {
// each purchase should still be needed
--need[t];
}
// decide the gap (1 or 2) and fix price[i]
int gap = 1; // default: gap = 1
if (!L.empty() && L[0] == i) gap = 2; // bought i -> gap = 2
price[i] = price[i - 1] - gap;
// buy the remaining copies of type i (if any)
int remaining = need[i]; // may be zero or positive
for (int k = 0; k < remaining; ++k) {
long long M2 = price[i]; // exactly price[i]; buys only i
auto res2 = transaction(M2);
for (int t : res2.first) {
--need[t];
}
}
// after this, need[i] should be zero
}
/* --------------------------------------------------------------
2. Finally buy the remaining copies of the cheapest type (N-1).
We already know price[N-2]; set
M = price[N-2] - 1
This value is guaranteed to be >= price[N-1] and < price[N-2],
so each transaction buys exactly one souvenir of type N-1.
-------------------------------------------------------------- */
long long M_last = price[N - 2] - 1; // works also for N == 2
while (need[N - 1] > 0) {
auto res = transaction(M_last);
for (int t : res.first) {
--need[t];
}
}
// At this point all need[t] should be zero.
}
