#include <vector>
#include <algorithm>
#include <map>
#include <functional>
#include <numeric>
using namespace std;
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
int N = P.size();
// Handle empty case
if (N == 0) return {};
// For small N, use bitmask DP
if (N <= 20) {
map<pair<int, int>, pair<int, vector<int>>> dp;
function<pair<int, vector<int>>(int, int)> solve = [&](int tokens, int mask) -> pair<int, vector<int>> {
auto state = make_pair(tokens, mask);
if (dp.count(state)) return dp[state];
pair<int, vector<int>> best = {0, {}};
for (int i = 0; i < N; i++) {
if (!(mask & (1 << i)) && tokens >= P[i]) {
int new_tokens = (tokens - P[i]) * T[i];
int new_mask = mask | (1 << i);
auto sub = solve(new_tokens, new_mask);
if (sub.first + 1 > best.first) {
best = {sub.first + 1, sub.second};
best.second.insert(best.second.begin(), i);
}
}
}
return dp[state] = best;
};
return solve(A, 0).second;
}
// For larger N, try multiple greedy strategies
vector<vector<int>> strategies;
// Strategy 1: Sort by price ascending
{
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return P[a] < P[b];
});
strategies.push_back(order);
}
// Strategy 2: Sort by multiplier descending, then price ascending
{
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (T[a] != T[b]) return T[a] > T[b];
return P[a] < P[b];
});
strategies.push_back(order);
}
// Strategy 3: Sort by ratio (T[i] - 1) / P[i] descending
{
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
double ratio_a = (double)(T[a] - 1) / P[a];
double ratio_b = (double)(T[b] - 1) / P[b];
if (abs(ratio_a - ratio_b) > 1e-9) return ratio_a > ratio_b;
return P[a] < P[b];
});
strategies.push_back(order);
}
// Strategy 4: High multipliers first, then by price
{
vector<int> high, low;
for (int i = 0; i < N; i++) {
if (T[i] >= 3) high.push_back(i);
else low.push_back(i);
}
sort(high.begin(), high.end(), [&](int a, int b) {
if (T[a] != T[b]) return T[a] > T[b];
return P[a] < P[b];
});
sort(low.begin(), low.end(), [&](int a, int b) {
return P[a] < P[b];
});
vector<int> order;
for (int x : high) order.push_back(x);
for (int x : low) order.push_back(x);
strategies.push_back(order);
}
// For very small N, try all permutations
if (N <= 8) {
vector<int> perm(N);
iota(perm.begin(), perm.end(), 0);
do {
strategies.push_back(perm);
} while (next_permutation(perm.begin(), perm.end()));
}
vector<int> best_result;
// Try each strategy
for (const auto& order : strategies) {
vector<bool> bought(N, false);
vector<int> result;
int tokens = A;
// Keep trying to buy coupons until no progress
bool progress = true;
while (progress) {
progress = false;
for (int i : order) {
if (!bought[i] && tokens >= P[i]) {
bought[i] = true;
result.push_back(i);
tokens = (tokens - P[i]) * T[i];
progress = true;
}
}
}
if (result.size() > best_result.size()) {
best_result = result;
}
// Early termination if we bought all coupons
if (result.size() == N) break;
}
return best_result;
}
