#include "souvenirs.h"
#include <vector>
#include <cassert>
using namespace std;
typedef long long ll;
struct Row {
vector<int> present;
ll sum;
Row () { }
Row (int _n, vector<int> _items, ll _sum) : present(_n, 0), sum(_sum) {
for (int u : _items) {
present[u] = 1;
}
}
int count () {
int ans = 0;
for (int u : present)
ans += u;
return ans;
}
bool exists () {
return !present.empty();
}
void operator-= (const Row& other) {
for (int i = 0; i < (int) present.size(); i++)
present[i] -= other.present[i];
sum -= other.sum;
}
};
void reduce_and_insert (vector<Row> &lead, Row &row) {
int n = lead.size();
for (int j = 0; j < n; j++) {
if (lead[j].exists() && lead[j].count() == 1 && row.present[j]) {
row -= lead[j];
}
}
int nk = -1;
for (int j = 0; j < n; j++) {
if (row.present[j]) {
nk = j;
break;
}
}
assert(nk != -1);
assert(!lead[nk].exists());
lead[nk] = row;
}
pair<vector<int>, ll> transaction_wrap (ll m, vector<int> &bought) {
auto pr = transaction(m);
for (int u : pr.first)
bought[u]++;
return pr;
}
void buy_souvenirs (int n, ll p0) {
vector<Row> lead (n);
vector<int> bought (n, 0);
ll nxt = p0 - 1;
while (true) {
auto pr = transaction_wrap(nxt, bought);
Row row (n, pr.first, nxt - pr.second);
lead[pr.first[0]] = row;
if (pr.first.size() == 1) {
nxt = row.sum - 1;
} else {
nxt = row.sum / pr.first.size();
}
if (pr.first.size() == 1 && pr.first[0] == n - 1) {
break;
}
}
// initialization is complete
while (true) {
// pseudo-Gaussian elimination
for (int i = n - 1; i >= 0; i--) {
if (!lead[i].exists() || lead[i].count() != 1)
continue;
for (int j = i - 1; j >= 0; j--) {
if (lead[j].exists() && lead[j].present[i]) {
lead[j] -= lead[i];
}
}
}
// if everyone has a lead, then we are done
bool finished = true;
for (int i = 1; i < n; i++) {
if (!lead[i].exists())
finished = false;
}
if (finished)
break;
bool ee = false;
for (int i = n - 1; i >= 0; i--) {
if (!lead[i].exists())
ee = true;
if (lead[i].exists() && lead[i].count() > 1) {
ll ask = lead[i].sum / lead[i].count();
auto pr = transaction_wrap(ask, bought);
Row row (n, pr.first, ask - pr.second);
reduce_and_insert(lead, row);
break;
}
if (lead[i].exists() && lead[i].count() == 1 && ee) {
ll ask = lead[i].sum - 1;
auto pr = transaction_wrap(ask, bought);
Row row (n, pr.first, ask - pr.second);
reduce_and_insert(lead, row);
break;
}
}
}
for (int i = 0; i < n; i++) {
while (bought[i] < i) {
transaction_wrap(lead[i].sum, bought);
}
}
}
