#include "souvenirs.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 111;
int n;
int cnt[N];
ll P[N];
bool flag[N];
map<ll, pair<vector<int>, ll>> mem;
pair<vector<int>, ll> buy(ll M) {
pair<vector<int>, ll> res;
if (mem.count(M)) res = mem[M];
else mem[M] = res = transaction(M);
ll used = M - res.second;
vector<int> v;
for (auto& x : res.first) {
if (P[x]) used -= P[x];
else v.push_back(x);
}
return make_pair(v, used);
}
void play(ll p) {
if (mem.count(p)) return;
auto now = buy(p);
if ((int)now.first.size() > 1) {
flag[now.first[0]] = 1;
ll sum = now.second;
for (auto& x : now.first) {
cnt[x]++;
}
play(sum / (int)(now.first.size()));
now = buy(p);
}
if ((int)now.first.size() == 1) {
int nxt = now.first[0];
cnt[nxt]++;
P[nxt] = now.second;
if (nxt != n - 1 && !flag[nxt + 1]) play(P[nxt] - 1);
}
}
void buy_souvenirs(int _N, ll P0) {
n = _N;
P[0] = P0;
flag[1] = 1;
play(P[0] - 1);
for (int i = 0;i < n;i++) {
// cerr << P[i] << " \n"[i == n - 1];
while (cnt[i] < i) transaction(P[i]), cnt[i]++;
}
return;
}
