#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_N = 100;
int bought[MAX_N];
ll price[MAX_N];
int N;
ll div_ceil(ll a, ll b) {
return (a + b - 1) / b;
}
pair<vector<int>, ll> my_transaction(ll T) {
auto [I, R] = transaction(T);
for(int i: I) {
bought[i] ++;
}
return {I, R};
}
// Transaction cost T
// Indices return I
// Remainder R
void solve(ll T, vector<int> I, ll R) {
if(I.size() == 1) {
price[I[0]] = T - R;
if(I[0] + 1 < N) {
T = price[I[0]] - 1;
auto [I, R] = my_transaction(T);
solve(T, I, R);
}
return;
}
ll rhs = T - R;
for(int i = I.size() - 1; i >= 1; i--) {
// Price already known
if(price[I[i]] > 0) {
rhs -= price[I[i]];
} else {
ll T1 = div_ceil(rhs, (i + 1)) - 1;
auto [I1, R1] = my_transaction(T1);
solve(T1, I1, R1);
// Now it should be known because we solved for that suffix
assert(price[I[i]] > 0);
rhs -= price[I[i]];
}
}
price[I[0]] = rhs;
// Now recursively solve for the remainder of the suffix
for(int k = I[0] + 1; k < N; k++) {
if(price[k] == 0) {
ll T1 = price[k - 1] - 1;
auto [I1, R1] = my_transaction(T1);
solve(T1, I1, R1);
break;
}
}
}
void buy_souvenirs(int _N, ll P0) {
N = _N;
price[0] = P0;
auto [I, R] = my_transaction(P0 - 1);
solve(P0 - 1, I, R);
for(int i = 0; i < N; i++) {
assert(price[i] > 0);
int rem = i - bought[i];
for(int j = 0; j < rem; j++) {
auto [I, R] = my_transaction(price[i]);
assert(R == 0);
assert(I.size() == 1);
assert(I[0] == i);
}
}
}
