#include <bits/stdc++.h>
#include "souvenirs.h"
typedef long long ll;
using namespace std;
void buy_souvenirs(int N, ll p0) {
vector<int> bought(N, 0);
vector<ll> known_price(N, 0);
vector<pair<vector<int>, ll>> completed_transactions;
vector<ll> money_unaccouted_for;
auto purchase = transaction(p0 - 1);
for (auto souvernir : purchase.first) {
bought[souvernir]++;
}
completed_transactions.push_back(purchase);
money_unaccouted_for.push_back(p0 - purchase.second);
while (completed_transactions.back().first[0] != N - 1) {
ll next_transaction = (money_unaccouted_for.back() - 1) /
completed_transactions.back().first.size();
purchase = transaction(next_transaction);
for (auto souvernir : purchase.first) {
bought[souvernir]++;
}
completed_transactions.push_back(purchase);
money_unaccouted_for.push_back(next_transaction - purchase.second);
}
known_price[N - 1] = money_unaccouted_for.back();
completed_transactions.pop_back();
money_unaccouted_for.pop_back();
int next_price_to_find = N - 2;
while (next_price_to_find != 0) {
auto &last_price = money_unaccouted_for.back();
auto &last_souvernirs = completed_transactions.back().first;
// removes knwon prices
for (int i = last_souvernirs.size(); i >= 0; i--) {
auto souvernir = last_souvernirs[i];
if (known_price[souvernir] != 0) {
last_price -= known_price[souvernir];
last_souvernirs.pop_back();
} else {
break;
}
}
// checks if the first element is the next price to find
// this means that the size must be 1
// and the only one left is next price to find
if (last_souvernirs[0] != next_price_to_find) {
ll next_transaction = (money_unaccouted_for.back() - 1) /
completed_transactions.back().first.size();
purchase = transaction(next_transaction);
for (auto souvernir : purchase.first) {
bought[souvernir]++;
}
completed_transactions.push_back(purchase);
money_unaccouted_for.push_back(next_transaction - purchase.second);
} else {
known_price[next_price_to_find] = money_unaccouted_for.back();
completed_transactions.pop_back();
money_unaccouted_for.pop_back();
}
}
// completes remaining purchaces
for (int i = 0; i < N; i++) {
while (bought[i] < i) {
transaction(known_price[i]);
}
}
}
