#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
void buy_souvenirs(int N, long long P0) {
int n = N;
vector<ll> p(N, -1);
p[0] = P0;
vector<int> amount_needed(N);
for(int i = 0; i < n; i++) amount_needed[i] = i;
for(int i = 1; i < n; i++){
if(amount_needed[i] == 0) continue;
// the difference from the last one is at most 2:
// p[i] = p[i - 1] - 1 or p[i - 1] - 2
pair<vector<int>, ll> buy = transaction(p[i - 1] - 1);
vector<int> items = buy.first;
ll change = buy.second;
// if we just buy type i
if(items.size() == 1){
amount_needed[i]--;
p[i] = (p[i - 1] - 1) - change;
}
// if we also manage to buy the next type for 1 coin
if(items.size() == 2){
amount_needed[i]--;
amount_needed[n - 1]--;
p[i] = p[i - 1] - 1;
p[n - 1] = 1;
}
}
// go through and buy what we need
for(int i = 0; i < n; i++){
for(int j = 0; j < amount_needed[i]; j++){
transaction(p[i]);
}
}
return;
}
