Cabala execution timed out

Aiuto
1

Sto provando a risolvere il problema cabala ma non riesco in nessun modo a completare l’ultimo subtask. Questo è il mio codice:

long long check(long long n) {

    std::string str = std::to_string(n);
    for (int i = 1; i < str.size(); i++) {
        if (str[i] == str[i - 1]) return -1;
    }
    return n;

}

long long ex(int N, long long n, int it, long long max, int M) {

    long long num = check(n);
    if (num == -1) return max;
    if (num % M > max % M) max = num;

    if (it == N) return max;

    long long n1 = ex(N, n * 10 + 3, it + 1, max, M);
    long long n2 = ex(N, n * 10 + 6, it + 1, max, M);
    long long n3 = ex(N, n * 10 + 9, it + 1, max, M);

    if (n1 % M > max % M) max = n1;
    if (n2 % M > max % M) max = n2;
    if (n3 % M > max % M) max = n3;

    return max;

}

long long occulta(int N, int M) {
    
    long long max = ex(N, 3, 1, 0, M);
    long long n1 = ex(N, 6, 1, 0, M);
    long long n2 = ex(N, 9, 1, 0, M);

    if (n1 % M > max % M) max = n1;
    if (n2 % M > max % M) max = n2;

    return max % M;

}

int main() {
    FILE *fr, *fw;
    int T, N, M, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(1 == fscanf(fr, "%d", &T));
    for (i=0; i<T; i++) {
        assert(2 == fscanf(fr, "%d %d", &N, &M));
        fprintf(fw, "%lld ", occulta(N, M));
    }

    fprintf(fw, "\n");
    fclose(fr);
    fclose(fw);
    return 0;
}

Qualcuno ha qualche idea per ottimizzarlo?

2

Hint 1: C’e’ piu’ di 1 testcase
Hint 2: I numeri sono sempre gli stessi
Soluzione: Chiama soltanto una volta la funzione che genera tutti i palindromi validi e salvali (io l’ho fatto in una matrice in cui una coordinata e’ il numero di cifre, ma puoi anche usare un vettore monodimensionale, sortare e poi fare una ricerca binaria con 10^n)

3
4

Grazie, sono riuscito a prendere 100/100

5

ciao, puoi spiegarmi perfavore come fai a generare i palindromi validi, non riesco a capire la tecnica

6

Un metodo brutale e non efficiente ma funzionante al 100% e’ instanziare 2 stringhe uguali chiamando to_string sul numero e successivamente chiamando reverse su una delle 2: se le stringhe sono uguali allora il numero e’ palindromo
La seconda soluzione parte sempre dal convertire il numero in stringa con to_string, e poi iterare con 2 puntatori numerici che partono dal fondo e dall’inizio della stringa e si incontrano a meta’.
Formalmente la stringa s e’ palindroma se s_i = s_{n-i-1} per ogni i
In pratica si traduce con

int n = s.size();
for (int i = 0; i <= n/2; i++) {
    if (s[i] != s[n-i-1]) {
        ... non palindromo
        break
    }
}
... palindromo