#include "souvenirs.h"
#include <utility>
#include <vector>
#define ll long long
#define f first
#define s second
using namespace std;
void findRec(ll num,pair<vector<int>, long long> res, vector <ll> &p, int N, int &knwn, vector <ll> &ws){
for(int i = 0; i < res.first.size(); i++){
ws[res.first[i]]++;
}
if(res.first.size() == 1){
p[res.first[0]] = num - res.second;
if(res.first[0] == knwn - 1){
knwn = res.first[0];
return;
}
findRec(num - res.second - 1,transaction(num - res.second - 1), p, N, knwn,ws);
knwn = res.first[0];
return;
}
while(true){
ll sum = 0;
for(int i = 0; i < res.first.size(); i++){
if(res.first[i] >= knwn){
sum += p[res.first[i]];
}
}
ll x = 0;
ll y = 0;
if(res.first[1] >= knwn){
y = num - sum - res.second;
p[res.first[0]] = y;
if(res.first[0] == res.first[1] - 1 || res.first[0] + 1 >= knwn){
knwn = res.first[0];
break;
}
x = y;
findRec(x,transaction(x - 1),p,N,knwn,ws);
knwn = res.first[0];
break;
}
x = (num - res.second - sum) / 2;
findRec(x,transaction(x),p,N,knwn,ws);
}
}
void buy_souvenirs(int N, long long P0) {
pair<vector<int>, long long> res = transaction(P0 - 1);
vector <ll> p(N + 1),ws(N + 1);
for(int i = 0; i <= N; i++){
p[i] = 0;
ws[i] = 0;
}
p[0] = P0;
findRec(P0 - 1,res,p,N,N,ws);
for(int i = 0; i < N; i++){
for(int j = 0; j <= i - ws[i]; j++){
transaction(p[i]);
}
}
return;
}
