#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(ll x){
return (1ll * x * (x + 1)) / 2;
}
ll P[maxN];
int cnt[maxN];
vector<vll> T;
void transformer(vll &X){
vector<int> tmp;
for (int id : X.fi){
if (P[id] == 0){
tmp.push_back(id);
}
else{
X.se -= P[id];
}
}
X.fi = tmp;
}
void buy_souvenirs(int n , ll p0){
int total = 0;
set<ll> A , B;
P[0] = p0;
total++;
A.insert(P[0] - 1);
while (total < n){
while (total < n && sz(A) > 0){
ll val = *prev(A.end());
A.erase(prev(A.end()));
B.insert(val);
vll X = transaction(val);
for (int id : X.fi) cnt[id]++;
X.se = val - X.se;
transformer(X);
if (sz(X.fi) == 0) break;
T.push_back(X);
if (sz(X.fi) == 1){
int pos = X.fi[0];
P[pos] = X.se;
total++;
if (B.count(P[pos] - 1) == 0) A.insert(P[pos] - 1);
break;
}
else{
val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1;
if (B.count(val) == 0) A.insert(val);
}
}
for (int i = sz(T) - 1 ; i >= 0 ; i--){
transformer(T[i]);
vll X = T[i];
if (sz(X.fi) == 0) continue;
if (sz(X.fi) == 1){
int pos = X.fi[0];
P[pos] = X.se;
total++;
}
ll val = (X.se - f(sz(X.fi)) + sz(X.fi) - 1) / sz(X.fi) + sz(X.fi) - 1;
if (B.count(val) == 0) A.insert(val);
}
}
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < i - cnt[i] ; j++) transaction(P[i]);
}
// cout << "---------\n";
// cout << total << "\n";
// for (int i = 0 ; i < n ; i++) cout << (cnt[i] <= i) << " ";
// cout << "\n";
// for (int i = 0 ; i < n ; i++) cout << P[i] << " ";
}
// int main(){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("templete.inp" , "r" , stdin);
// cin >> n;
// for (int i = 0 ; i < n ; i++) cin >> p[i];
// buy_souvenirs(n , p[0]);
// return 0;
// }
