#include <bits/stdc++.h>
#define TASK "sourvenirs"
#include "souvenirs.h"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
struct equation{
bitset<100> c;
ll sum = 0;
equation() {}
equation(pair<vector<int>,ll> x, ll X)
{
for (auto i:x.fi) c[i] = 1;
sum = X-x.se;
}
};
ll a[105];
int t[105], n;
vector<equation> f;
bool check()
{
FOR(i, 1, n-1) if (!a[i]) return true;
return false;
}
bool cmp(const equation &x, const equation &y)
{
int cx = n, cy = n;
FOR(i, 1, n-1) if (x.c[i])
{
cx = i; break;
}
FOR(i, 1, n-1) if (y.c[i])
{
cy = i; break;
}
return cx<cy;
}
void process(int pos)
{
FOR(i, 1, n-1) if (f[pos].c[i] && a[i]>0)
{
f[pos].c[i] = 0; f[pos].sum -= a[i];
}
while (f[pos].c.count()>0)
{
if (f[pos].c.count()==1)
{
int id = 0;
FOR(i, 1, n-1) if (f[pos].c[i])
{
id = i; break;
}
a[id] = f[pos].sum;
int cnt = 0;
FOR(i, id+1, n-1) if (!a[i]) cnt++;
if (cnt>0)
{
f.pb(equation(transaction(a[id]-1),a[id]-1));
FOR(i, 1, n-1) if (f.back().c[i]) t[i]++;
process((int)f.size()-1);
}
}
else
{
ll nx = f[pos].sum/f[pos].c.count();
f.pb(equation(transaction(nx), nx));
FOR(i, 1, n-1) if (f.back().c[i]) t[i]++;
process((int)f.size()-1);
}
FOR(i, 1, n-1) if (f[pos].c[i] && a[i]>0)
{
f[pos].c[i] = 0; f[pos].sum -= a[i];
}
}
}
void buy_souvenirs(int N, long long P0)
{
n = N;
a[0] = P0;
f.pb(equation(transaction(P0-1), P0-1));
FOR(i, 1, n-1) if (f[0].c[i]) t[i]++;
process(0);
FOR(i, 1, n-1)
{
FOR(j, t[i]+1, i) transaction(a[i]);
}
return;
}
