#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>
#define ll long long int
#define mp make_pair
using namespace std;
vector<pair<ll,vector<ll> > > v;
vector<ll> provvisorio;
vector<ll> calls;
vector<ll> definitivo;
void solve(ll index, long long x, ll N, ll P0) {
pair<vector<int>, long long> pt =transaction(x);
x-=pt.second;
v[index].first=x;
for(auto el : pt.first) {
v[index].second.push_back(el);
}
// v[index].second=pt.first;
// cout<<index<<": ";
// for(auto el : pt.first) {
// cout<<el<<" ";
// }
// cout<<"\n\n\n";
for(auto el : pt.first) {
calls[el]++;
}
ll a = 1, b = P0-N+1;
ll minsol = b;
while(a<=b) {
ll k = (a+b)/2;
ll somma = 0;
for(auto el : pt.first) {
somma+=k+N-el-1;
}
if(somma>=x) {
b=k-1;
minsol=min(minsol,k);
} else {
a=k+1;
}
}
provvisorio[index]=minsol+N-index-1;
}
void buy_souvenirs(int N, long long P0) {
v.resize(N);
calls.resize(N);
provvisorio.resize(N);
provvisorio[0]=P0;
for(ll i=1;i<N;i++) {
solve(i,provvisorio[i-1]-1,N,P0);
}
definitivo.resize(N);
definitivo[0]=P0;
for(ll i=N-1;i>=1;i--) {
ll thsomma = v[i].first;
for(auto el : v[i].second) {
if(el==i)
continue;
thsomma-=definitivo[el];
}
definitivo[i]=thsomma;
}
// // for(ll i=0;i<N;i++) {
// // cout<<calls[i]<<" ";
// // }
// for(ll i=1;i<N;i++) {
// while(calls[i]<i) {
// calls[i]++;
// transaction(definitivo[i]);
// }
// }
return;
}
