#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
void buy_souvenirs(int N, long long P0) {
vector<vector<int>> transactions(N);
vector<int> bought(N, 0);
vector<long long> sent(N, 0);
// phase 1: buy until last is reached
long long M = P0 - 1;
int at = 1;
while(at + 1 < N) {
auto res = transaction(M);
vector<int> souv = res.first;
long long rem = res.second;
long long total_cost = M - rem;
sort(souv.begin(), souv.end());
long long min_cost = 0;
for(int i = 0; i < (int)souv.size(); ++i) {
bought[souv[i]]++;
min_cost += N - souv[i];
}
transactions[at] = souv;
sent[at] = total_cost;
long long min_val_of_left = N - at;
long long amt = N - at;
total_cost -= min_cost;
min_val_of_left += (total_cost + amt - 1) / amt;
M = min_val_of_left - 1;
at++;
}
// phase 2: find price of last
auto res = transaction(M);
vector<int> souv = res.first;
long long rem = res.second;
assert(souv.size() == 1);
vector<long long> prices(N, 0);
prices[N - 1] = M - rem;
bought[N - 1]++;
// phase 3: backtrack until all are bought
for(int i = N - 1; i >= 1; --i) {
if(prices[i] == 0) {
for(int b : transactions[i]) {
if(b != i) {
sent[i] -= prices[b];
}
}
prices[i] = sent[i];
}
while(bought[i] < i) {
transaction(prices[i]);
bought[i]++;
}
}
prices[0] = P0;
//~ cout << "PRICES\n";
//~ for(int i = 0; i < N; ++i) {
//~ cout << prices[i] << " ";
//~ }
//~ cout << "\n-----------\n";
return;
}
