#include <bits/stdc++.h>
using namespace std;
int BASE = 3;
int SHIFT = (BASE - 1) + (BASE - 1);
int get_bit(int num, int digit) {
for (int i = 0; i < digit; i ++) {
num /= BASE;
}
return num % BASE;
}
int logbase(int N) {
// idk it doesn't work sometimes with log(n) / log(base)
int curr_pow = 1;
int pw = 0;
while (curr_pow <= N) {
curr_pow *= BASE;
pw ++;
}
return pw;
}
vector<vector<int>> devise_strategy(int N) {
int digits = logbase(N); // il log (n + 1) è solo perché non prende bene alcuni numeri xd
// cout << "digits : " << digits << '\n';
// VVV questo ma con base diversa da 2 per minimizzare X
// 3 * xxxxxx + y
// x = quale cifra sto guardando, sapendo che quelle più alte sono uguali
// y = 0 : sono in B e il bit di A è 0
// 1 : sono in B e il bit di A è 1
// 2 : sono in A e devo passare il bit di A in B
vector<vector<int>> s((BASE) * (digits + 1) - SHIFT, vector<int>(N + 1));
// shifta tutto di (B - 1) perché con digit == 0 c'è un solo caso (l'inizio), così risparmi numeri.
// also guardando l'ultima cifra, se è 2 è peffo più alta, se 0 più bassa, solo se è 1 ha senso pushare
for (int x = 0; x < (BASE) * (digits + 1) - SHIFT; x ++) {
int real_x = x + SHIFT;
// cout << "x , real_x -> " << x << " " << real_x << '\n';
int bit = real_x % BASE;
int digit = real_x / BASE;
if (digit == 1) bit = 1;
// cout << "bit, digit -> " << bit << " " << digit << '\n';
if (x == 0) {
// start, occupa un po' di casi ma è solo uno tho
int digit_next = digits;
s[x][0] = (digits + 1) % 2;
// // cout << "seleziono " << (digits + 1) % 2 << '\n';
// cout << "digits_next : " << digit_next << '\n';
for (int j = 1; j <= N; j ++) {
int bit_next = get_bit(j, digit_next - 1);
// cout << "j, bit_next : " << j << " " << bit_next << '\n';
if (digit_next == 1) {
// funziona con base 3
if (bit_next == 0) s[x][j] = -1;
else if (bit_next == 2) s[x][j] = -2;
else s[x][j] = 1;
}
else s[x][j] = (digit_next * BASE) + bit_next - SHIFT;
// cout << s[x][j] << '\n';
}
continue;
}
// // cout << "CASO DIGIT" << '\n';
s[x][0] = (digit % 2);
// // cout << "seleziono " << (digit % 2) << '\n';
int digit_next = digit;
// // cout << "digit_next -> " << digit_next << '\n';
for (int j = 1; j <= N; j ++) {
int bit_next = get_bit(j, digit_next - 1);
// // cout << "bit_next : " << bit_next << '\n';
if (bit_next < bit) s[x][j] = (digit % 2) ? -2 : -1;
if (bit < bit_next) s[x][j] = (digit % 2) ? -1 : -2;
}
digit_next -= 1;
if (digit_next == 0) continue;
// cout << "digit_next : " << digit_next << '\n';
for (int j = 1; j <= N; j ++) {
int bit_next = get_bit(j, digit_next - 1);
// cout << "j, bit_next : " << j << " " << bit_next << '\n';
if (digit_next == 1 && s[x][j] != -1 && s[x][j] != -2) { // && s[x][j] != -1 && s[x][j] != -2
// // cout << "vado dentro " << '\n';
// funziona con base 3
if (bit_next == 0) s[x][j] = ((digit) % 2) ? -2 : -1;
if (bit_next == 2) s[x][j] = ((digit) % 2) ? -1 : -2;
if (bit_next == 1) s[x][j] = 1;
}
if (digit_next > 1 && s[x][j] != -1 && s[x][j] != -2) {
s[x][j] = (digit_next * BASE) + bit_next - SHIFT;
}
// cout << s[x][j] << '\n';
}
}
// for (int x = 0; x < s.size(); x ++) {
// cout << x << " : ";
// for (int j = 1; j <= N; j ++) cout << s[x][j] << " ";
// cout << '\n';
// }
return s;
}
