#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
/*
P[i + 2] * 2 <= P[i + 1] + P[i + 2] <= P[i] <= 2 * P[i + 1]
So for a given value, P[i] (highest) cannot be < val / 3
*/
void buy_souvenirs(int N, long long P0) {
vector<int> cnt(N, 0);
vector<long long> lowest_price_for_which_highest(N + 1, -1);
lowest_price_for_which_highest[0] = P0;
iota(cnt.begin(), cnt.end(), 0);
long long cur_val = P0 - 1;
std::pair<std::vector<int>, long long> res = transaction(cur_val);
lowest_price_for_which_highest[1] = cur_val - res.second;
for(int x: res.first) {
cnt[x] -= 1;
}
bool omk = false, cntt = true;
while(true) {
int sum = accumulate(cnt.begin(), cnt.end(), 0LL);
// cout << "omk = " << omk << ", cntt = " << cntt << endl;
if(sum == 0) break;
if(!cntt) {
for(int i = N - 1; i >= 0; i--) {
if(lowest_price_for_which_highest[i] == -1) {
// cout << "coming here for i = " << i << endl;
lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 1] * 2;
cur_val = lowest_price_for_which_highest[i];
omk = true;
cntt = true;
break;
}
}
if(!omk || !cntt) {
for(int i = 1; i < N; i++) {
if(cnt[i] != 0) {
// cout << "i = " << i << ", cnt[i] = " << cnt[i] << endl;
cur_val = lowest_price_for_which_highest[i];
omk = true;
cntt = true;
break;
}
}
}
}
else if(res.first.size() == 1) {
lowest_price_for_which_highest[res.first[0]] = cur_val - res.second;
lowest_price_for_which_highest[res.first[0] + 1] = cur_val - res.second - 1;
for(int i = N - 1; i >= 0; i--) {
if(lowest_price_for_which_highest[i] == -1) {
// cout << "coming here for i = " << i << ", and 2" << endl;
lowest_price_for_which_highest[i] = lowest_price_for_which_highest[i + 1] * 2;
cur_val = lowest_price_for_which_highest[i];
omk = true;
cntt = true;
break;
}
}
if(!omk || !cntt) {
for(int i = 1; i < N; i++) {
if(cnt[i] != 0) {
// cout << "i = " << i << ", cnt[i] = " << cnt[i] << endl;
cur_val = lowest_price_for_which_highest[i];
omk = true;
cntt = true;
break;
}
}
}
}
else if(res.first.size() >= 3) {
cur_val = (cur_val - res.second) / 3;
}
else {
cur_val = (cur_val - res.second) / 2;
}
if(!omk || cntt) {
res = transaction(cur_val);
for(int x: res.first) {
cnt[x] -= 1;
}
long long ok = res.first.size();
lowest_price_for_which_highest[res.first[0]] = cur_val - res.second - (ok * (ok - 1)) / 2;
if(omk) cntt = false;
}
}
// std::pair<std::vector<int>, long long> res = transaction(3);
return;
}
