#include "souvenirs.h"
#include <utility>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
long long solved[1000];
long long equations [1000][1000];
long long br[1000];
void update(int N){
for(int i=1;i<N;i++){
if(equations[N][i]==1){
equations[0][i] -= solved[N];
}
}
}
long long neweq (int i,int nums){
if(nums==1){
return equations[0][i]-1;
}else{
return equations[0][i]/nums;
}
}
void solve(int N,long long P0){
if(N==1){return;}
while(equations[N][N]!=1){
int i = N-1;
while(equations[i][i]!=1){
i=i-1;
}
int nums =0;
for(int j=i;j<=N;j++){
if(equations[j][i]==1){
nums++;
}
}
long long x;
pair<vector<int>,long long> s;
if(i!=0){
s = transaction(neweq(i,nums));
x = neweq(i,nums);
}else{
s = transaction(P0-1);
x = P0-1;
}
//cout<<x<<" amogus "<<nums<<endl;
long long newe=s.first[0]+1;
equations[0][newe] = x - s.second;
for(int t = 0;t<s.first.size();t++){
equations[s.first[t]+1][newe] = 1;
br[s.first[t]]++;
}
}
/*for(int i = 1; i <= N; i++) {
for(int j = 0; j <= N; j++) {
cout << equations[j][i] << " ";
}
cout << endl;
}
cout<<endl;*/
solved[N] = equations[0][N];
update(N);
solve(N-1,P0);
}
void buy_souvenirs(int N, long long P0) {
for(int i=0;i<1000;i++){
solved[i]=0;
br[i]=0;
for(int j=0;j<1000;j++){
equations[i][j]=0;
}
}
equations[0][0] = 1;
solve(N,P0);
for(int i=0;i<N;i++){
for(int j =0;j<i-br[i];j++){
transaction(solved[i+1]);
}
}
return;
}
