#include <algorithm>//chatgpt
#include <vector>
using namespace std;
namespace {
int extract_digit(int value, const vector<int>& block_size, const vector<int>& radix, int depth) {
const int zero_based = value - 1;
return (zero_based / block_size[depth]) % radix[depth];
}
} // namespace
vector<vector<int>> devise_strategy(int N) {
vector<long long> best_product(61, 0);
vector<int> previous_cost(61, -1);
vector<int> chosen_radix(61, -1);
best_product[0] = 1;
for (int cost = 0; cost <= 60; ++cost) {
if (best_product[cost] == 0) {
continue;
}
for (int radix = 2; radix <= 8; ++radix) {
int next_cost = cost + radix + 1;
if (next_cost > 60) {
continue;
}
long long next_product = best_product[cost] * radix;
if (next_product > best_product[next_cost]) {
best_product[next_cost] = next_product;
previous_cost[next_cost] = cost;
chosen_radix[next_cost] = radix;
}
}
}
int final_cost = -1;
for (int cost = 0; cost <= 60; ++cost) {
if (best_product[cost] >= N) {
final_cost = cost;
break;
}
}
if (final_cost == -1) {
return {};
}
vector<int> radix;
while (final_cost > 0) {
radix.push_back(chosen_radix[final_cost]);
final_cost = previous_cost[final_cost];
}
reverse(radix.begin(), radix.end());
const int levels = static_cast<int>(radix.size());
vector<int> block_size(levels, 1);
for (int i = levels - 2; i >= 0; --i) {
block_size[i] = block_size[i + 1] * radix[i + 1];
}
int state_count = levels;
vector<vector<int>> b_state(levels);
for (int depth = 0; depth < levels; ++depth) {
b_state[depth].resize(radix[depth]);
for (int digit = 0; digit < radix[depth]; ++digit) {
b_state[depth][digit] = state_count++;
}
}
vector<vector<int>> strategy(state_count, vector<int>(N + 1, 0));
for (int depth = 0; depth < levels; ++depth) {
strategy[depth][0] = 0;
for (int coins = 1; coins <= N; ++coins) {
int digit = extract_digit(coins, block_size, radix, depth);
strategy[depth][coins] = b_state[depth][digit];
}
}
for (int depth = 0; depth < levels; ++depth) {
for (int fixed_digit = 0; fixed_digit < radix[depth]; ++fixed_digit) {
int state = b_state[depth][fixed_digit];
strategy[state][0] = 1;
for (int coins = 1; coins <= N; ++coins) {
int digit = extract_digit(coins, block_size, radix, depth);
if (digit < fixed_digit) {
strategy[state][coins] = -2;
} else if (digit > fixed_digit) {
strategy[state][coins] = -1;
} else if (depth + 1 < levels) {
strategy[state][coins] = depth + 1;
} else {
strategy[state][coins] = 0;
}
}
}
}
return strategy;
}
