#include "souvenirs.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef pair<vector<int> , long long> vll;
const int maxN = 107;
const int maxM = 5007;
// int n;
// ll p[maxN];
// pair<vector<int> , ll> transaction(ll m){
// // cout << "start : " << m << "\n";
// vector<int> tmp;
// for (int i = 0 ; i < n ; i++){
// if (m >= p[i]){
// m -= p[i];
// tmp.push_back(i);
// }
// }
// // for (int x : tmp) cout << x << " ";
// // cout << "\n";
// // cout << m << "\n";
// // cout << "-------------------------\n";
// return {tmp , m};
// }
ll f(int x){
return (1ll * x * (x + 1)) / 2;
}
ll P[maxN];
int cnt[maxN];
vector<vll> T;
void buy_souvenirs(int n , ll p0){
P[0] = p0;
int total = 1;
while (total < n){
int pos = -1;
for (int i = 1 ; i < n ; i++){
if (P[i - 1] != 0 && P[i] == 0){
pos = i - 1;
break;
}
}
if (pos == -1) break;
ll val = P[pos] - 1;
if (pos != n - 1){
while (total < n){
vll tmp = transaction(val);
for (int id : tmp.fi) cnt[id]++;
val -= tmp.se; tmp.se = val;
vector<int> lis_id;
for (int id : tmp.fi){
if (P[id] == 0){
lis_id.push_back(id);
}
tmp.se -= P[id];
}
tmp.fi = lis_id;
val = tmp.se;
T.push_back(tmp);
if (sz(tmp.fi) == 1){
int nxt_pos = tmp.fi[0];
if (P[nxt_pos] == 0){
P[nxt_pos] = val;
val--;
total++;
if (nxt_pos == n - 1) break;
}
else{
break;
}
}
else{
val = (val - f(sz(tmp.fi)) + sz(tmp.fi) - 1) / sz(tmp.fi) + sz(tmp.fi) - 1;
}
}
}
for (int i = sz(T) - 1 ; i >= 0 ; i--){
vll tmp = T[i];
ll val = tmp.se;
int num = sz(tmp.fi);
int nxt_pos = -1;
for (int id : tmp.fi){
if (P[id] != 0){
num--;
val -= P[id];
}
else{
nxt_pos = id;
}
}
if (num == 1 && P[nxt_pos] == 0){
P[nxt_pos] = val;
total++;
}
}
}
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < i - cnt[i] ; j++) transaction(P[i]);
}
}
// int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// cin >> n;
// for (int i = 0 ; i < n ; i++) cin >> p[i];
// buy_souvenirs(n , p[0]);
// return 0;
// }
