#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stdio.h>
using namespace std;
void buy_souvenirs(int N, long long P0) {
// std::pair<std::vector<int>, long long> res = transaction(3);
// printf("hi\n");
vector<long long> bought(N, 0LL);
vector<long long> solved(N, 0LL);
vector<vector<long long> > eq;
vector<long long> first(N + 1, 0LL);
first[0] = 1;
first[N] = P0;
// printf("pushing stuff \n");
eq.push_back(first);
// solved[0] = P0;
// start by buying P0 - 1 then
while(eq.size() > 0){
// find the last equation
// printf("getting back\n");
vector<long long> cur = eq.back();
// printf("got back\n");
// first go through all the non zero ones and clean up the solves
for (int i = 0; i < N; i++){
if(cur[i] && solved[i]){
cur[i] = 0;
cur[N] -= solved[i];
}
}
// if its empty then skip
if (cur[N] == 0){
eq.pop_back();
continue;
}
// if theres only 1 bit then mark it as solved, clear it from all the predecessors
int count = 0;
int index = 0;
for(int i = 0; i < N; i++){
count += cur[i];
if(cur[i] > 0) index = i;
}
long long next = 0LL;
if (count == 1){
solved[index] = cur[N];
for(size_t j = 0; j < eq.size() - 1; j++){
if(eq[j][index]){
eq[j][index] = 0;
eq[j][N] -= solved[index];
}
}
if(index < N-1 && solved[index + 1] == 0){
next = solved[index] - 1;
}
eq.pop_back();
}else{
// now take the floor of the value divided by the count to get the next value
// this is guranteed to be not the biggest one
next = cur[N] / count;
}
if (!next) continue;
// do transaction now
// cout << "Doing transaction " << next << endl;
// printf("Doing transaction %lld\n", next);
std::pair<std::vector<int>, long long> res = transaction(next);
vector<long long> neweq(N + 1, 0LL);
for(int a : res.first){
neweq[a] = 1;
bought[a]++;
}
neweq[N] = next - res.second;
eq.push_back(neweq);
}
// make sure everythign is solved
for(int i = 0; i < N; i++){
if(!solved[i]){
// std::cout >> "Not solved!!! " << i << " " << solved[i];
return;
}
}
// do the remaining ones now
for(int i = 0; i < N; i++){
while(bought[i] < i){
std::pair<std::vector<int>, long long> res = transaction(solved[i]);
if (res.second != 0 || res.first.size() != 1) {
// std::cout >> "Not a perfect buy!! " << i << " " < <solved[i] << endl;
return;
}
bought[res.first[0]]++;
}
}
return;
}
