#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>
const int nmax=1e2+42;
long long known[nmax];
int seen[nmax];
std::vector< std::pair< std::vector<int>, long long> > known_sums;
void add_line(long long M)
{
std::pair< std::vector<int>, long long> outp=transaction(M);
outp.second=M-outp.second;
for(auto pos:outp.first)
seen[pos]++;
known_sums.push_back(outp);
bool change=1;
while(change)
{
change=0;
std::vector< std::pair< std::vector<int>, long long> > new_known_sums={};
for(auto line:known_sums)
{
long long new_sum=line.second;
std::vector<int> new_positions={};
for(auto pos:line.first)
if(known[pos])new_sum-=known[pos];
else new_positions.push_back(pos);
if(new_positions.size()!=line.first.size())change=1;
if(new_positions.size()==0)continue;
if(new_positions.size()==1)
{
known[new_positions[0]]=new_sum;
}
else
{
new_known_sums.push_back({new_positions,new_sum});
}
}
known_sums=new_known_sums;
}
}
int get_last_non_suffix(int N)
{
int pos=N-1;
while(known[pos])pos--;
while(known[pos]==0)pos--;
return pos;
}
void buy_souvenirs(int N, long long P0)
{
known[0]=P0;
for(int i=1;i<N;i++)
{
int pos=get_last_non_suffix(N);
if(known_sums.size()==0||known_sums.back().first[0]<pos)
{
add_line(known[pos]-1);
}
else
{
add_line(known_sums.back().second/known_sums.back().first.size());
}
}
for(int i=0;i<N;i++)
while(seen[i]<i)
{
add_line(known[i]);
}
}
