Aiuto con ois cabala

Aiuto
1

non riesco ad ottimizzare il programma, molti testcase superano il secondo, consigli?

#include <stdio.h>
#include <assert.h>
#include <cmath>
#include <vector>

long long occulta(int N, int M) {
    long long int n = 0;
    long long int mr = -1, j;
    for (j = 0; j<=N ; j += 2){
        n += pow(10,N-j-1)*9;
    }
    for (j = 1; j<=N ; j += 2){
        n += pow(10,N-j-1)*6;
    }

    for (j = 0; j < n; j += 3) {
        long long int num = j, nump = -1;
        std::vector<int> cifra;
        bool ok = true;
        int cn = N-1;
        while (num > 0) {
            cifra.push_back(num % 10);
            num /= 10;
        }
        for (int x = cifra.size() - 1; x >= 0; x--) {
            if (cifra[x] == 0 || cifra[x] % 3 != 0 || cifra[x] == nump) {
                ok = false;
                break;
            }else{
                nump = cifra[x];
            }
        }

        if (ok) {
            int r = j % M;
            if (r > mr) {
                mr = r;
            }
        }
    }
    return mr;
}

int main() {
    FILE *fr, *fw;
    int T, M, N, 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;
}
1 Mi Piace
2

Quello che penso tu stia facendo sia cercare il numero perfetto, che e’ giusto ma molto lento. Se invece provi a costruirlo? Tramite la ricorsione aggiungendo sempre una cifra diversa e’ molto efficente.

3

già ho pensato di usare la ricorsione, ma mi risulta molto difficile da comprendere, soprattutto in un contesto del genere, quindi ho optato per cercarlo, sperando che andasse bene, a quanto pare no, ma ora proverò a capire come usarla per bene, grazie comunque

4

Anche senza ricorsione si riesce a prendere 100. Il punto è che generando tutti i numeri stai provando circa 10^N numeri ma in realtà i numeri validi sono molti di meno (in particolare un semplice conto mostra che sono 3 \cdot 2^{N-1}. Ora per migliorare il codice dovresti provare a generare direttamente solo questi numeri; un modo comodo (ma non il solo) di farlo è appunto mediante ricorsione.