# Cabala execution timed out

**URL:** <https://forum.olinfo.it/t/cabala-execution-timed-out/7574>\
**Category:** Aiuto\
**Created:** [15 Luglio 2022, 2:00pm UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574 "2022-07-15T14:00:36Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![DanieleSahebi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/3da27b/32.png) [@DanieleSahebi](https://forum.olinfo.it/u/DanieleSahebi)\
**Post date:** [15 Luglio 2022, 2:00pm UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/1 "2022-07-15T14:00:36Z")

</div>

Sto provando a risolvere il problema [cabala](https://training.olinfo.it/#/task/ois_cabala/statement) ma non riesco in nessun modo a completare l’ultimo subtask. Questo è il mio codice:

```auto
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?

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [15 Luglio 2022, 5:39pm UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/2 "2022-07-15T17:39:58Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![BestCrazyNoob](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7cd45c/32.png) [@BestCrazyNoob](https://forum.olinfo.it/u/BestCrazyNoob)\
**Post date:** [16 Luglio 2022, 9:37am UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/3 "2022-07-16T09:37:04Z")

</div>

> [@Cabala Subtask 4](https://forum.olinfo.it/t/cabala-subtask-4/7420/6):
>
> Io ho fatto così: ho creato una funzione void recursion(char last\_d, int curr, char len) dove last\_d è la cifra più significativa del numero, curr è il numero, len è la lunghezza del numero (in decimale). All’inizio del programma chiamo recursion(0, 0, 0), ossia il caso in cui il numero è 0 (non conta in teoria, ma alla fine non cambia niente). Ogni volta che viene chiamata la funzione calcola il modulo e si segna in una variabile globale il modulo massimo che trova, poi si chiama di nuovo d…

---

<div class="post-metadata">

**Author:** ![DanieleSahebi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/3da27b/32.png) [@DanieleSahebi](https://forum.olinfo.it/u/DanieleSahebi)\
**Post date:** [16 Luglio 2022, 10:55am UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/4 "2022-07-16T10:55:14Z")

</div>

Grazie, sono riuscito a prendere 100/100

---

<div class="post-metadata">

**Author:** ![danieledellef](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/c0e974/32.png) [@danieledellef](https://forum.olinfo.it/u/danieledellef)\
**Post date:** [16 Luglio 2022, 12:47pm UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/5 "2022-07-16T12:47:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\
**Post date:** [16 Luglio 2022, 5:37pm UTC](https://forum.olinfo.it/t/cabala-execution-timed-out/7574/6 "2022-07-16T17:37:04Z")

</div>

Un metodo brutale e non efficiente ma funzionante al 100% e’ instanziare 2 stringhe uguali chiamando [to\_string](https://cplusplus.com/reference/string/to_string/) sul numero e successivamente chiamando [reverse](https://en.cppreference.com/w/cpp/algorithm/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

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

```