#include "souvenirs.h"
#include <utility>
#include <vector>
#include <stack>
int count[111];
bool isfirst[111];
long long price[111];
std::pair<std::vector<int>, long long> transaction2(long long M)
{
std::pair<std::vector<int>, long long> res = transaction(M);
for (int i = 0; i < res.first.size(); i++)
{
count[res.first[i]]++;
}
isfirst[res.first[0]] = true;
res.second = M - res.second;
return res;
}
void buy_souvenirs(int N, long long P0)
{
std::pair<std::vector<int>, long long> res;
if (N == 2)
{
res = transaction(P0 - 1);
}
else if (N == 3)
{
res = transaction(P0 - 1);
if (res.first.size() == 1)
{
long long p1 = P0 - 1 - res.second;
res = transaction(p1 - 1);
res = transaction(p1 - 1);
}
else
{
long long half = (P0 - 1 - res.second) / 2;
res = transaction(half);
}
}
else if (P0 == N)
{
for (int i = 1; i < N; i++)
{
for (int j = 1; j <= N - i; j++)
{
res = transaction(i);
}
}
}
else
{
std::fill(count, count + N, 0);
std::fill(price, price + N, 0);
std::fill(isfirst, isfirst + N, false);
std::stack<std::pair<std::vector<int>, long long>> st;
st.push(transaction2(P0 - 1));
while (st.size() > 0)
{
res = st.top();
if (res.first.size() == 1)
{
price[res.first[0]] = res.second;
st.pop();
bool all = true;
for (int i = res.first[0]; i < N; i++)
{
if (price[i] == 0)
{
all = false;
break;
}
}
if (!all)
{
st.push(transaction2(res.second - 1));
}
}
else
{
long long sum = res.second;
int count = 0;
for (int i = 0; i < res.first.size(); i++)
{
if (price[res.first[i]] != 0)
{
sum -= price[res.first[i]];
}
else
{
count++;
}
}
if (count == 0)
{
st.pop();
}
else if (count == 1)
{
for (int i = 0; i < res.first.size(); i++)
{
if (price[res.first[i]] == 0)
{
price[res.first[i]] = sum;
break;
}
}
st.pop();
}
else
{
st.push(transaction2(sum / count));
}
}
for (int i = N - 2; i > 0; i--)
{
if (price[i] != 0 && price[i + 1] == 0 && !isfirst[i + 1])
{
st.push(transaction2(price[i] - 1));
break;
}
}
}
for (int i = 1; i < N; i++)
{
while (count[i] < i)
transaction2(price[i]);
}
}
}
