#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++;
sets[i].clear();
}
}
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) {
cerr << remaining << endl;
while(1) {
if (!deduce()) break;
}
if (remaining == 0) break;
bool havetoguess = false;
for (int i = N-1; i >= 0; i--) {
cerr << i << " " << havetoguess << endl;
if (val[i] == -1) havetoguess = true;
if (val[i] != -1 && havetoguess) {
auto aux = transaction(val[i]-1);
set<int> s;
for (auto x : aux.first) {
s.insert(x);
am[x]++;
}
sums[i+1] = (val[i]-1) - aux.second;
sets[i+1] = s;
break;
}
if (sets[i].size()) {
ll x = sums[i] / (int)sets[i].size();
auto aux = transaction(x);
set<int> s;
for (auto x : aux.first) {
am[x]++;
s.insert(x);
}
int k = aux.first[0];
sets[k] = s;
sums[k] = x-aux.second;
break;
}
}
}
rep(i, 0, N) {
while (am[i] < i) {
transaction(val[i]);
am[i]++;
}
}
}
