#include "souvenirs.h"
#include <iostream>
using namespace std;
// Compile with:
// g++ -std=gnu++20 -O2 -o souvenir souvenirs.h souvenirs.cpp
// Can call:
// std::pair<std::vector<int>, long long> transaction(long long M)
long long price[101];
long long bought[101];
bool debug = false;
void recurse(int N, long long guess) {
pair<vector<int>, long long> ret = transaction(guess);
vector<int>& items = ret.first;
long long remainder = ret.second;
for (int i = 0; i < items.size(); i++) {
bought[items[i]]++;
}
if (debug) {
cout << "Transaction: " << guess << " returns (";
for (int i = 0; i < items.size(); i++) {
cout << items[i] << " ";
}
cout << ") and remainder " << remainder << endl;
}
if (items.size() == 1) {
// only hit one item
// we know it's exact value.
long long s = guess - remainder;
price[items[0]] = s;
if (debug) {
cout << "Deduced price[" << items[0] << "] = " << s << endl;
}
if (items[0] < N-1) {
// if there's more items to the right,
// we should recurse further
recurse(N, s-1);
}
}
else {
// hit multiple items
// Guess the average of them (this is guaranteed to be safe).
// While we don't know the price of all of our items, make "safe" guesses,
//
while (true) {
int known_items = 0;
int last_unknown_idx = 0;
long long s = guess - remainder;
for (int i = 0; i < items.size(); i++) {
if (price[items[i]] != 0) {
known_items += 1;
s -= price[items[i]];
}
else {
last_unknown_idx = i;
}
}
if (known_items == items.size()-1) {
price[items[last_unknown_idx]] = s;
if (debug) {
cout << "Deduced price[" << items[last_unknown_idx] << "] = " << s << endl;
}
known_items += 1;
}
if (known_items == items.size()) {
break;
}
long long unknown_items = items.size() - known_items;
if (debug) {
cout << "known_items = " << known_items << ", unknown_items = " << unknown_items << ", s = " << s << endl;
cout << "state transaction: " << guess << " returns (";
for (int i = 0; i < items.size(); i++) {
cout << items[i] << " ";
}
cout << ") and remainder " << remainder << endl;
for (int i = 0; i < N; i++) {
cout << "i = " << i << ", p = " << price[i] << ", b = " << bought[i] << endl;
}
// for (int i = 0; i < items.size(); i++) {
// cout << "item: " << items[i] << " " << price[items[i]] << endl;
// }
// cout << "Starting new recursion with " << s / unknown_items << endl;
}
recurse(N, s / unknown_items);
}
}
// Find the next smallest number that we don't know.
for (int i = N-1; i > items[0]; i--) {
if (price[i] == 0 && price[i-1] != 0) {
recurse(N, price[i-1] - 1);
}
}
}
void buy_souvenirs(int N, long long P0) {
long long x = P0;
for (int i = 0; i < N; i++) {
price[i] = 0;
bought[i] = 0;
}
price[0] = P0;
for (int i = 1; i < N; i++) {
if (price[i] == 0) {
if (debug) {
cout << "Top level call for " << i << endl;
}
recurse(N, price[i-1] - 1);
}
if (price[i] == 0) {
cout << "Failed to deduce " << i << endl;
return;
}
}
for (int i = 0; i < N; i++) {
while (bought[i] < i){
if (price[i] != 0) {
transaction(price[i]);
bought[i]++;
}
else {
cout << "Did not deduce price of " << i << endl;
break;
}
}
}
if (debug) {
cout << "Final answer: " << endl;
for (int i = 0; i < N; i++) {
cout << i << ": " << price[i] << ", " << bought[i] << endl;
}
}
}
