#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
vl p(105), cnt(105);
int n;
void check(ll m) {
auto [s, r] = transaction(m);
for (int i : s) cnt[i]++;
ll cost = m-r;
if (!p[s[0]]) {
vi s2;
for (int i : s) {
if (p[i]) cost -= p[i];
else s2.push_back(i);
}
while (s2.size() > 1) {
check(cost/s2.size());
while (s2.size() && p[s2.back()]) cost -= p[s2.back()], s2.pop_back();
}
p[s[0]] = cost;
}
for (int i = s[0]; i < n-1; i++) if (!p[i+1]) {
check(p[i]-1);
break;
}
}
void buy_souvenirs(int N, long long P0) {
p[0] = P0;
n = N;
check(p[0]-1);
//cout << "p: "; for (int i = 0; i < N; i++) cout << p[i] << " "; cout << endl;
//cout << "c: "; for (int i = 0; i < N; i++) cout << cnt[i] << " "; cout << endl;
for (int i = 0; i < N; i++) while (cnt[i]+1 < i) transaction(p[i]), cnt[i]++;
return;
}
