#include "souvenirs.h"
#include <vector>
#include <algorithm>
#include <functional> // <-- THÊM DÒNG NÀY
using namespace std;
void buy_souvenirs(int N, long long P0) {
// Sinh tất cả dãy P khả dĩ
vector<vector<int>> candidates;
vector<int> cur = { (int)P0 };
// Đổi tên từ 'generate' → 'gen' để tránh xung đột
function<void()> gen = [&]() {
if ((int)cur.size() == N) {
candidates.push_back(cur);
return;
}
int last = cur.back();
for (int x = last - 1; x >= 1; --x) {
cur.push_back(x);
gen(); // gọi đệ quy chính nó
cur.pop_back();
}
};
gen(); // khởi chạy
vector<int> total_bought(N, 0);
// Lọc dần các candidate bằng truy vấn
while (candidates.size() > 1) {
bool found_M = false;
for (long long M = 1; M < P0; ++M) {
// Mô phỏng transaction(M) trên tất cả candidate
vector<vector<int>> results;
for (auto& cand : candidates) {
long long coins = M;
vector<int> bought;
for (int i = 0; i < N; ++i) {
if (coins >= cand[i]) {
coins -= cand[i];
bought.push_back(i);
}
}
results.push_back(bought);
}
// Kiểm tra có phân biệt được không
bool all_same = true;
for (int i = 1; i < (int)results.size(); ++i) {
if (results[i] != results[0]) {
all_same = false;
break;
}
}
if (!all_same) {
// Gọi transaction thật
auto real_res = transaction(M);
const vector<int>& real_bought = real_res.first;
for (int t : real_bought) {
total_bought[t]++;
}
// Lọc candidate khớp với kết quả thật
vector<vector<int>> new_candidates;
for (int i = 0; i < (int)candidates.size(); ++i) {
if (results[i] == real_bought) {
new_candidates.push_back(candidates[i]);
}
}
candidates = new_candidates;
found_M = true;
break;
}
}
if (!found_M) break; // không còn M nào phân biệt được
}
// Mua đủ số lượng còn thiếu
vector<int> P = candidates[0];
for (int i = 1; i < N; ++i) {
int need = i - total_bought[i];
for (int j = 0; j < need; ++j) {
transaction(P[i]);
}
}
}
