#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
#define rep(i, k, n) for (int i = k; i < n; i++)
#define cerr if (0) cerr
v<set<int>> sets;
v<ll> sums;
v<ll> val;
v<bool> beg;
v<int> am;
int remaining;
int deduce() {
int N = sums.size();
int cnt=0;
rep(i, 0, N) {
cerr << i << endl;
set<int> aux = sets[i];
for (auto y : sets[i]) {
if (val[y] != -1) {
aux.erase(y);
sums[i] -= val[y];
}
}
sets[i] = aux;
}
rep(i, 0, N) {
if (sets[i].size() == 1) {
val[i] = sums[i];
cnt++;
}
}
remaining -= cnt;
return cnt;
}
void buy_souvenirs(int N, long long P0) {
remaining = N-1;
sets.resize(N);
val.assign(N, -1);
sums.assign(N, -1);
beg.assign(N, false);
am.assign(N, 0);
beg[0] = true;
val[0] = P0;
sums[0] = P0;
while (remaining > 0) {
while(1) {
if (!deduce()) break;
}
ll last = P0-1;
rep(i, 1, N) {
bool enter = false;
cerr << i << endl;
if (beg[i] == false && val[i] == -1 && val[i-1] != -1) {
enter = true;
ll last = val[i-1]-1;
int ni;
while (true) {
auto aux = transaction(last);
ni = aux.first[0];
cerr << ni << " " << aux.first.size() << endl;
beg[ni] = true;
set<int> s;
for (auto x : aux.first) {
s.insert(x);
am[x]++;
}
cerr << "DEBUG" << endl;
sets[ni] = s;
sums[ni] = last-aux.second;
last = (sums[ni]/aux.first.size());
if (aux.first.size() == 1) break;
}
}
if (enter) break;
}
}
rep(i, 0, N) {
while (am[i] < i) {
transaction(val[i]);
am[i]++;
}
}
}
