#include<bits/stdc++.h> using namespace std; pair<vector<int>,long long> transaction(long long M); int cnt=0; pair<vector<int>,long long>c[105]; int k[105]; long long p1[105]; int let[105]; void remove(vector<int>v) { for(int i:v) { let[i]--; } } void buy_souvenirs(int N,long long p0) { for(int i=0;i<N;i++) { let[i]=i; } long long last=p0-1; while(true) { //cout<<last<<' '; auto [v,r]=transaction(last); remove(v); c[v[0]]={v,r}; k[v[0]]=last; long long sum=last-r; if(v.size()==1&&v.back()==N-1) { p1[N-1]=sum; break; } if(v.size()==1) { last=sum-1; } else { last=sum/long(v.size())-1; } } //cout<<'\n'; for(int i=N-2;i>=2;i--) { if(c[i].first.empty()) { //cout<<i<<' '<<2*p1[i+1]<<' '; auto [v,r]=transaction(2*p1[i+1]); remove(v); //cout<<2*p1[i+1]<<' '; p1[i]=2*p1[i+1]-r; for(int j=1;j<v.size();j++) { p1[i]-=p1[v[j]]; } //cout<<i<<' '<<p1[i]<<'3'<<'\n';; } else { auto [v,r]=c[i]; //cout<<i<<' '<<v.size()<<' '<<r<<' '<<k[i]<<'\n'; p1[i]=k[i]-r; //cout<<p1[i]<<' '; for(int j=1;j<v.size();j++) { //cout<<i<<' '; p1[i]-=p1[v[j]]; } //cout<<i<<' '<<p1[i]<<'\n'; //cout<<i<<' '<<p1[i]<<'\n';; } } //cout<<'\n'; for(int i=2;i<N;i++) {//cout<<i<<' '<<p1[i]<<'\n'; for(int j=0;j<let[i];j++) { transaction(p1[i]); } } }