#include "souvenirs.h"
#include <utility>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <unordered_set>
#include <iostream>
#include <queue>
using namespace std;
void buy_souvenirs(int N, long long P0) {
unordered_set<long long> visited;
vector<pair<unordered_set<int>, long long>> sums;
int purchases[105] = {0,};
pair<vector<int>, long long> res = transaction(P0-1);
visited.insert(P0-1);
////cout<<.+
unordered_set<int> res2;
for (auto i:res.first) {res2.insert(i); purchases[i]++;}
// for (int i = 0; i < N; i++) {
// ////cout<<.+
// }
////cout<<.+
sums.push_back(make_pair(res2, P0-1-res.second));
////cout<<.+
// for (auto j:sums) {
// for (auto k:j.first) ////cout<<.+
// ////cout<<.+
// }
////cout<<.+
long long price = -1;
// for (int __ = 0; __ < 40; __++) {
unordered_set<int> visitedsums;
queue<int> transactions;
transactions.push(P0-1);
while (1) {
for (int i = sums.size()-1; i >= 0; i--) {
if (visitedsums.find(i) != visitedsums.end()) continue;
visitedsums.insert(i);
// ////cout<<.+
unordered_set<int> s;
for (auto i:sums) {
if (i.first.size() == 1) s.insert(*i.first.begin());
}
// for (int p = 0; p < N; p++) {
// //cout<<.+
// }
//cout<<.+
// //cout<<.+
// //cout<<.+
// //cout<<.+
//cout<<.+
if (s.size() >= N-1) break;
// flag = false;
// long long x = ceil((long double)sums[i].second/(long double)sums[i].first.size())-1;
long long x = ceil((long double)(2*sums[i].second+sums[i].first.size()*(sums[i].first.size()-1))/(long double)(sums[i].first.size()*2))-1;
if (price == -1) {
for (auto j:sums) {
// ////cout<<.+
if (j.first.size() == 1) {
// ////cout<<.+
if (*j.first.begin() == N-1) price = j.second;
}
}
}
// bool flag = true;
// for (int _ = 0; _ < 100; _++) {
while (visited.find(x) != visited.end()) x--;
// x--;
// }
// if (flag) {
// sums.erase(sums.begin()+i);
// }
// ////cout<<.+
// ////cout<<.+
if (x <= 0 || (price != -1 && x < price)) {
// if (purchases[N-1] >= N-1) continue;
long long a = transactions.front();
transactions.pop();
long long b = transactions.front();
transactions.pop();
//cout<<.+
x = ((a+b)/2+rand()%300000)%(P0-1);
}
// if (x <= 0) break;
pair<vector<int>, long long> res3 = transaction(x);
// if (x < 0) return;
visited.insert(x);
transactions.push(x);
////cout<<.+
////cout<<.+
unordered_set<int> res4;
for (auto j:res3.first) {res4.insert(j); purchases[j]++;}
sums.push_back(make_pair(res4, x-res3.second));
////cout<<.+
// for (auto j:sums) {
// if (j.first.size() == 0) continue;
// for (auto k:j.first) ////cout<<.+
// ////cout<<.+
// }
////cout<<.+
for (int j = 0; j < sums.size(); j++) {
for (int k = 0; k < sums.size(); k++) {
if (j == k) continue;
if (sums[j].first.size() == 1) continue;
bool flag2 = true;
for (auto l:sums[k].first) {
if (sums[j].first.find(l) == sums[j].first.end()) {
flag2 = false;
break;
}
}
if (flag2) {
for (auto l:sums[k].first) {
sums[j].first.erase(l);
}
sums[j].second -= sums[k].second;
}
}
}
// if (i == 0) {
// long long x = (sums.front().second+sums[1].second)/2;
// while (visited.find(x) != visited.end()) x--;
// // x--;
// // }
// // if (flag) {
// // sums.erase(sums.begin()+i);
// // }
// // ////cout<<.+
// // ////cout<<.+
// if (x <= 0) break;
// if (price != -1 && x < price) break;
// pair<vector<int>, long long> res3 = transaction(x);
// // if (x < 0) return;
// visited.insert(x);
// ////cout<<.+
// for (int j = 0; j < N; j++) {
// ////cout<<.+
// }
// ////cout<<.+
// unordered_set<int> res4;
// for (auto j:res3.first) {res4.insert(j); purchases[j]++;}
// sums.push_back(make_pair(res4, x-res3.second));
// }
}
bool flag3 = true;
for (int i = 1; i < N; i++) {
if (purchases[i] != i) {flag3 = false; break;}
}
if (flag3) return;
// break;
unordered_set<int> s;
for (auto i:sums) {
if (i.first.size() == 1) s.insert(*i.first.begin());
}
// ////cout<<.+
if (s.size() >= N-1) break;
}
//cout<<.+
////cout<<.+
////cout<<.+
// for (auto j:sums) {
// for (auto k:j.first) ////cout<<.+
// ////cout<<.+
// }
////cout<<.+
for (int i = 1; i < N; i++) {
////cout<<.+
if (purchases[i] == i) continue;
long long price;
////cout<<.+
for (auto j:sums) {
////cout<<.+
if (j.first.size() == 1) {
// ////cout<<.+
if (*j.first.begin() == i) price = j.second;
}
}
////cout<<.+
for (int _ = 0; _ < i-purchases[i]; _++) {
transaction(price);
////cout<<.+
}
}
////cout<<.+
return;
}
