#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
/**
* Simulate what the grader does when you hand it M coins,
* given a candidate price‐vector P.
*/
static vector<int> simulate(const vector<long long>& P, long long M) {
vector<int> bought;
long long R = M;
int N = (int)P.size();
for (int i = 0; i < N; i++) {
if (R >= P[i]) {
R -= P[i];
bought.push_back(i);
}
}
return bought;
}
void buy_souvenirs(int N, long long P0) {
// 1) Observe the seller's response for every 1 <= M < P0:
vector<vector<int>> obs(P0);
for (long long M = 1; M < P0; M++) {
auto resp = transaction(M);
obs[M] = resp.first;
}
// 2) Brute‐force all decreasing sequences
// P[1] > P[2] > ... > P[N-1] drawn from {1,...,P0-1}.
vector<int> pool;
for (int x = 1; x < P0; x++)
pool.push_back(x);
vector<long long> P(N);
P[0] = P0;
// We'll generate all size-(N-1) permutations of pool
// then keep only those whose sorted order is strictly decreasing.
bool found = false;
vector<int> idx(pool.size());
fill(idx.begin(), idx.begin() + (N-1), 1);
// next_permutation on a 0/1 mask to choose subsets of size N-1
do {
// collect chosen elements
vector<int> cand;
for (int i = 0; i < (int)pool.size(); i++)
if (idx[i])
cand.push_back(pool[i]);
// sort in decreasing order
sort(cand.begin(), cand.end(), greater<int>());
// build full price‐vector
for (int i = 1; i < N; i++)
P[i] = cand[i-1];
// test this P against every M
bool ok = true;
for (long long M = 1; M < P0 && ok; M++) {
if (simulate(P, M) != obs[M])
ok = false;
}
if (ok) {
found = true;
break;
}
} while (prev_permutation(idx.begin(), idx.end()) && !found);
assert(found && "Exactly one price‐vector must match");
// 3) We now know P[1..N-1]. To get i copies of type i,
// simply pay M = P[i] exactly (which buys one type-i souvenir),
// and repeat that i times.
for (int i = 1; i < N; i++) {
for (int cnt = 0; cnt < i; cnt++) {
transaction(P[i]);
}
}
}
