#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
using ll = long long;
const int maxn = 105;
struct result {
vector<int> items;
ll price = 0;
};
result leading[maxn];
ll prices[maxn];
int bought[maxn];
int known_leading;
result add_leading(ll curp) {
auto [items, price] = transaction(curp);
sort(items.begin(), items.end());
if (leading[items[0]].price == 0) known_leading++;
leading[items[0]] = {items, curp - price};
for (int i : items) bought[i]++;
return {items, price};
}
void calc_price(int i) {
ll me = leading[i].price;
for (int j : leading[i].items) if (j != i) me -= prices[j];
prices[i] = me;
}
void buy_souvenirs(int n, ll P0) {
ll curp = P0 - 1;
fill(leading, leading+maxn, result());
// create equations
while (true) {
auto [items, price] = add_leading(curp);
int k = items.size();
curp -= price;
curp /= k;
if (k == 1) curp--;
if (items[0] == n-1) break;
}
// solve equations
while (known_leading < n-1) {
int unknown = n-1;
while (leading[unknown].price) {
if (!prices[unknown]) calc_price(unknown);
unknown--;
}
int known = unknown;
while (leading[known].price == 0) known--;
ll totalp = leading[known].price;
int totaln = leading[known].items.size();
for (int j : leading[known].items) {
if (j > unknown) {
if (!prices[j]) calc_price(j);
totaln--;
totalp -= prices[j];
}
}
totalp /= totaln;
if (totaln == 1) totalp--;
auto [items, price] = add_leading(totalp);
int cnt_unknown = items.size();
ll total = totalp - price;
for (int i : items) {
if (prices[i]) {
total -= prices[i];
cnt_unknown--;
}
}
if (cnt_unknown == 1) prices[items[0]] = total;
}
// make purchases
for (int i = n-1; i >= 0; i--) {
calc_price(i);
while (bought[i] < i) {
transaction(prices[i]);
bought[i]++;
}
}
}
