#include "souvenirs.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) cerr << #array << " = "; for(int w = 0; w < array.size(); w++) cerr << array[w] << spc; cerr << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
int call = 0;
vl price, cnt;
void getPrice(vector<int> st, ll cost){
vi a;
while(st.size()>0){
for(auto x: st){
if(price[x]){
cost -= price[x];
}else{
a.push_back(x);
}
}
st = a;
a.clear();
if(st.size()<1){
return;
}else if(st.size()==1){
price[*st.begin()] = cost;
return;
}else{
ll newP = cost / st.size();
for(int i = st.back(); i >= 0; i--){
if(price[i]!=0 && price[i]<newP){
newP = price[i] - 1;
break;
}
}
auto [c, b] = transaction(newP);
call++;
for(auto x: c) cnt[x]++;
b = newP - b;
getPrice(c, b);
}
}
}
void buy_souvenirs(int N, long long P0) {
price.assign(N, 0);
price[0] = P0;
cnt.assign(N, 0);
int gottill = 1;
int id = 0;
while(gottill < N){
auto [a, b] = transaction(price[gottill-1]-1);
call++;
b = price[gottill-1]-1 - b;
for(auto x: a) cnt[x]++;
getPrice(a, b);
while(gottill < N && price[gottill]) gottill++;
id++;
}
debarr(cnt)
for(int i = 1; i < N; i++){
while(cnt[i]<i) transaction(price[i]), cnt[i]++;
}
deb(call)
return;
}
