#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);
void check(vi s, ll m) {
if (s.size() == 1) {
p[s[0]] = m;
return;
}
ll avg = m/s.size();
auto [s2, r2] = transaction(avg);
for (ll i : s2) cnt[i]++;
ll costr = avg-r2;
check(s2, costr);
set<int> st(s.begin(), s.end());
for (int i : s2) st.erase(i);
vi s3(st.begin(), st.end());
ll costl = m-costr;
check(s3, costl);
}
void buy_souvenirs(int N, long long P0) {
p[0] = P0;
for (int i = 1; i < N; i++) if (!p[i]) {
auto [s, r] = transaction(p[i-1]-1);
ll m = p[i-1]-1-r;
check(s, m);
}
for (int i = 0; i < N; i++) while (cnt[i]+1 < i) transaction(p[i]), cnt[i]++;
//for (int i = 0; i < N; i++) cout << p[i] << " "; cout << endl;
return;
}
