#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;
const int max_n = 107;
int ile[max_n];
ll c[max_n];
void get_c(int n, ll val){
//cout << "\nget_c, val: " << val << '\n';
pair<vi,ll> v = transaction(val);
for(auto x:v.st) ile[x]++;
ll whole_cost = val-v.nd;
//cout << "whole_cost: " << whole_cost << " v.st: ";
//for(auto x:v.st) cout << x << ' ';
//cout << '\n';
if(v.st.size() == 1){
//cout << "size = 1\n";
c[v.st[0]] = whole_cost;
if(!c[v.st[0]+1] && v.st[0] != n-1) get_c(n,whole_cost-1);
return;
}
//dopoki nie mamy kolejnego kosztu!
while(!c[v.st[1]]){
ll s = 0; ll new_val = whole_cost;
for(auto x:v.st){
if(c[x]) new_val -= c[x];
else s++;
}
//cout << "\npetla dla val: " << val << " s: " << s << " new_val: " << new_val << '\n';
ll max_a = ((new_val+s*(s-1)/2)/s);
//cout << "max_a: " << max_a << '\n';
get_c(n,max_a-1); //nie wiadomo czy ten -1 dziala!
}
for(auto x:v.st) whole_cost -= c[x];
c[v.st[0]] = whole_cost;
//cout << "\ndla val: " << val << " ustawiamy c od: " << v.st[0] << " na " << whole_cost << '\n';
if(!c[v.st[0]+1] && v.st[0] != n-1) get_c(n,c[v.st[0]]-1);
return;
}
void buy_souvenirs(int n, ll p0){
get_c(n,p0-1);
rep(i,1,n-1){
//cout << "i: " << i << " c: " << c[i] << '\n';
while(ile[i] < i){
ile[i]++;
transaction(c[i]);
}
}
}
