#include <bits/stdc++.h>
#include "souvenirs.h"
using namespace std;
#define ll long long
int N;
ll prices[105];
ll cnt[105];
map<ll, pair<vector<int>,ll>> cache;
pair<vector<int>,ll> query(ll x){
//returns the unknown types and their sum of costs
vector<int> bought;
ll change;
bool cached = false;
if (cache.count(x)){
tie(bought, change) = cache[x];
cached = true;
}
else{
tie(bought, change) = transaction(x);
cache[x] = make_pair(bought, change);
}
ll paid = x - change;
vector<int> ret;
for (auto u: bought){
if (!cached) cnt[u]--;
if (prices[u] != -1){
paid -= prices[u];
} else{
ret.emplace_back(u);
}
}
return make_pair(ret, paid);
}
void solve(ll x){
vector<int> bought; ll total;
tie(bought, total) = query(x);
while (bought.size() > 1){
solve(total/bought.size());
tie(bought, total) = query(x);
}
if (bought.size() == 1){
ll idx = bought[0];
prices[idx] = total;
if (idx != N - 1 && prices[idx + 1] == -1){
solve(total - 1);
}
}
}
void buy_souvenirs(int n, ll p0){
memset(prices,-1,sizeof(prices));
for (int i=0;i<n;i++) cnt[i] = i;
prices[0] = p0;
N = n;
solve(p0 - 1);
for (int i=1;i<n;i++){
while (cnt[i]--){
transaction(prices[i]);
}
}
}
