#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 104;
int pr[N];
int lf[N];
void buy(vector<signed> a, int price){
if (a.size() == 1){
pr[a[0]] = price; return;
}
if (pr[a.back()]){
price -= pr[a.back()]; a.pop_back();
return buy(a, price);
}
int m = a.size();
int am = price/m;
// for (int x: a) cout<<x<<' '; cout<<'\n';
for (int i=a[0]; i<a.back(); i++) if (pr[i]) am = pr[i]-1;
auto [v, r] = transaction(am);
for (auto x: v) lf[x]--;
buy(v, am - r);
buy(a, price);
}
void buy_souvenirs(signed N, long long P0) {
for (int i=0; i<N; i++) lf[i] = i;
int last = 0;
while (1){
auto [v, r] = transaction(P0-1);
for (auto x: v) lf[x]--;
buy(v, P0-1-r);
int fs = -1;
for (int i=last+2; i<N; i++) if (!pr[i]) {fs = i-1; break;}
if (fs == -1) break;
P0 = pr[fs]; last = fs;
}
for (int i=0; i<N; i++) while (lf[i]) transaction(pr[i]), lf[i]--;
}
