#include <bits/stdc++.h>
#include "souvenirs.h"
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
constexpr int maxn = 105;
ll need[maxn];
ll prices[maxn];
//std::pair<std::vector<int>, long long> transaction(long long M)
bool checkIfSolved(int n)
{
bool ret=true;
for(int i=0;i<n;i++)
ret&=prices[i]>0;
return ret;
}
void buy_souvenirs(int N, long long P0) {
for(int i=0;i<N;i++)
prices[i]=0;
for(int i=0;i<N;i++)
need[i]=i;
prices[0]=P0;
vector<pair<vector<int>,ll>> multisets;
std::pair<std::vector<int>, long long> res;
while(!checkIfSolved(N))
{
bool solvedOne=true;
while(solvedOne)
{
solvedOne=false;
vector<pair<vector<int>,ll>> newMultisets;
for(auto pa:multisets)
{
vector<int> indices=pa.first;
int cost=pa.second;
vector<int> leftover;
for(auto idx:indices)
{
if(prices[idx]>0)
{
cost-=prices[idx];
}
else
{
leftover.push_back(idx);
}
}
if(leftover.size()==0)
continue;
if(leftover.size()==1)
{
prices[leftover[0]]=cost;
solvedOne=true;
}
else
{
newMultisets.push_back({leftover,cost});
}
}
multisets=newMultisets;
}
if(checkIfSolved(N))
break;
/*
for(int i=0;i<N;i++)
cout << need[i] << ' ';
cout << endl;
for(int i=0;i<N;i++)
cout << prices[i] << ' ';
cout << endl;
*/
int curr;
int needToSolve;
curr=N-1;
while(prices[curr]>0)
curr--;
needToSolve=curr;
while(prices[curr]==0)
curr--;
vector<int> arr;
vector<int> barr;
int used;
ll x;
x=prices[curr]-1;
while(prices[needToSolve]==0)
{
/*
for(int i=0;i<N;i++)
cout << need[i] << ' ';
cout << endl;
for(int i=0;i<N;i++)
cout << prices[i] << ' ';
cout << endl;
cout << x << endl;
*/
res=transaction(x);
arr=res.first;
vector<int>().swap(barr);
used=x-res.second;
for(auto num:arr)
{
need[num]-=1;
if(prices[num]>0)
{
used-=prices[num];
}
else
{
barr.push_back(num);
}
}
if(barr.size()==1)
{
prices[barr[0]]=used;
x=used-1;
}
else
{
x=used/barr.size();
multisets.push_back({barr,used});
}
}
}
for(int i=0;i<N;i++)
{
while(need[i]>0)
{
transaction(prices[i]);
need[i]-=1;
}
}
return;
}
