#include "souvenirs.h"
#include <cassert>
#include <climits>
#include <utility>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ret = pair<vector<int>, long long>;
using ll = long long;
#define reste second
vector<long long> cnt(100, 0), val(100, 0);
int n;
ret query(ll m){
auto r = transaction(m);
for(auto p:r.first)cnt[p]++;
return r;
}
pair<ll, int> get_down(ret r, ll montant){
ll m_unknowm = montant - r.reste, nbuk = 0;
int id = -1;
for(int p:r.first){
nbuk += !(bool)val[p];
m_unknowm -= val[p];
if(val[p]==0)id=p;
}
return {(nbuk == 0 ? -1 : m_unknowm / nbuk), nbuk};
}
void solve(ll montant){
ret re_p = query(montant);
int nv = -1;
if(get_down(re_p, montant).second == 1){
if(montant==8)cerr<<"yep"<<endl;
for(int p:re_p.first)if(val[p]==0)nv=p;
val[nv] = get_down(re_p, montant).first;
}else{
if(montant==8)cerr<<"not confused "<< get_down(re_p, montant).second <<endl;
auto gd = get_down(re_p, montant);
while( gd.second > 1){
cerr << "in while" << endl;
assert(gd.first > 0);
solve(gd.first);
gd = get_down(re_p, montant);
}
for(int p:re_p.first)if(val[p]==0)nv=p;
val[nv] = gd.first;
}
if(nv == -1)return;
if(nv < n-1 && val[nv]>0 && val[nv+1]==0)
solve(val[nv]-1);
cerr << montant<<" nv : "<<nv << " " << val[nv]<<" "<<val[nv+1]<<endl;
assert(nv == n-1 || (val[nv] && val[nv+1]));
}
void buy_souvenirs(int N, long long P0) {
fill(cnt.begin(), cnt.end(),0);
fill(val.begin(), val.end(),0);
val[0] = P0;
n = N;
solve(P0-1);
for(int i = 0; i < n ; i++){
assert(cnt[i]<=i);
while(i-cnt[i])query(val[i]);
}
for(int i = 0 ; i < n ; i++)cerr << val[i] << ' ' ;
cerr << endl;
return;
}
