#include<bits/stdc++.h>
using namespace std;
//#define test
#ifndef test
#include "souvenirs.h"
#endif // test
#ifdef test
vector<long long> P = {100, 99, 98, 97, 60, 59, 58, 57, 20, 19, 18, 17, 4, 3, 2, 1};
int cntBought[101];
void quit(const char* message){
printf("%s\n", message);
exit(0);
}
pair<vector<int>, long long> transaction(long long M){
if(M >= P[0] || M < P.back())
quit("Invalid argument");
vector<int> ret;
for(int i = 1; i < P.size(); ++i)
if(P[i] <= M){
M -= P[i];
ret.push_back(i);
++cntBought[i];
}
return make_pair(ret, M);
}
#endif // test
void buy_souvenirs(int N, long long P0){
vector<long long> p(N, -1), sumUnknown(N, 0);
p[0] = P0;
set<int> s[N];
while(1){
bool unknown = false;
for(int i = N - 1; i >= 0; --i){
if(p[i] == -1)
unknown = true;
if(p[i] != -1 && unknown){
pair<vector<int>, long long> tmp = transaction(p[i] - 1);
sumUnknown[i + 1] = p[i] - 1 - tmp.second;
for(int j : tmp.first){
if(p[j] != -1)
sumUnknown[i + 1] -= p[j];
else
s[i + 1].insert(j);
}
break;
}
if(s[i].size() == 1){
p[i] = sumUnknown[i];
s[i].clear();
for(int j = 0; j < N; ++j){
auto pt = s[j].find(i);
if(pt != s[j].end()){
sumUnknown[j] -= p[i];
s[j].erase(pt);
}
}
break;
}
if(s[i].size()){
long long x = sumUnknown[i] / s[i].size();
pair<vector<int>, long long> tmp = transaction(x);
long long sum = x - tmp.second;
int lgs = N;
for(int j : tmp.first){
if(p[j] != -1)
sum -= p[j];
else{
if(lgs == N)
lgs = j, s[lgs].clear();
s[lgs].insert(j);
}
}
sumUnknown[lgs] = sum;
break;
}
}
if(!unknown)
break;
}
for(int i = 1; i < N; ++i)
while(cntBought[i] < i)
transaction(p[i]);
}
#ifdef test
int main(){
buy_souvenirs(P.size(), P[0]);
for(int i = 0; i < P.size(); ++i)
cout << cntBought[i] << " ";
}
#endif
