#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC target("avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("devirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("Ofast,fast-math")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#define int long long
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define F first
#define S second
#define T third
#define FOR(i, x, y) for(ll i = x; i <= y; i++)
#define FORJ(i, x, y, j) for(ll i = x; i <= y; i += j)
#define FORD(i, x, y) for(ll i = y; i >= x; --i)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPF(i, n) for(ll i = 0; i + 1 < n; i++)
#define N 105
#define INF 100000000000000000
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define accu(a) accumulate(all(a), 0ll)
template<typename T> inline T gcd(T a,T b) { while (b != 0) swap(b, a %= b); return a; }
template<typename T> inline T lcm(T a, T b){ return (a / gcd(a, b)) * b;}
struct payment {
vector<int> items;
ll price;
};
payment leading[N];
ll price[N];
int cnt_bought[N];
int know_leading;
pair<vector<int>, ll> add_leading(ll curp) {
auto ret = transaction(curp);
sort(all(ret.F));
if (leading[ret.F[0]].price == 0) know_leading++;
leading[ret.F[0]] = {ret.F, curp - ret.S};
for (int i : ret.F) cnt_bought[i]++;
return ret;
}
void calc_price(int i) {
ll me = leading[i].price;
for (int j : leading[i].items) if (j != i) me -= price[j];
price[i] = me;
}
void buy_souvenirs(int n, ll P0) {
ll curp = P0 - 1;
REP(i, n) leading[i] = {vector<int>(), 0};
while (true) {
auto ret = add_leading(curp);
curp -= ret.S;
curp = curp / ret.F.size();
if (ret.F.size() == 1) curp--;
if (ret.F[0] == n - 1) break;
}
while (know_leading < n - 1) {
int unknown = n - 1;
while (leading[unknown].price) {
if (!price[unknown]) calc_price(unknown);
unknown--;
}
int known = unknown;
while (leading[known].price == 0) known--;
ll totp = leading[known].price;
int totn = leading[known].items.size();
for (int j : leading[known].items) {
if (j > unknown) {
if (!price[j]) calc_price(j);
totn--;
totp -= price[j];
}
}
if (totn == 1) totp--;
else totp /= totn;
auto ret = add_leading(totp);
int cnt_unknown = ret.F.size();
ll tot = totp - ret.S;
for (int i : ret.F) {
if (price[i]) {
tot -= price[i];
cnt_unknown--;
}
}
if (cnt_unknown == 1) {
price[ret.F[0]] = tot;
}
}
FORD(i, 0, n - 1) {
ll me = leading[i].price;
for (int j : leading[i].items) if (j != i) me -= price[j];
price[i] = me;
while (cnt_bought[i] < i) {
transaction(price[i]);
cnt_bought[i]++;
}
}
}
