Aiuto con ois cabala

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

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.

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

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.