Aiuto con cabala

Aiuto
1

buongiorno, è da un pò di giorni che sto provando a risolvere il problema Numero della cabala(questo), mi chiedevo se qualcuno potesse aiutarmi.

#include <stdio.h>
#include <assert.h>
using namespace std;

long long int maxr, rest;

void solve(int N, int M, long long int cifre){
    if (N == 0){
        return;
    }

    if(3 == cifre%10){
        cifre *= 10;
        cifre += 6;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }
    if(6 == cifre%10){
        cifre *= 10;
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 6;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }
    if(9 == cifre%10){
        cifre *= 10;
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }

}

long long occulta(int N, int M) {
    maxr = 0, rest = 0;
    solve(N, M, 3);
    solve(N, M, 6);
    solve(N, M, 9);
    return maxr;
}


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;
}
2

Ciao, il problema del tuo codice è che quando tu controlli quale sia l’ultima cifra, hai 3 if in cascata, questo significa che, mettiamo caso che la cifra finale fosse 3, allora ricadrai nel primo caso che ti metterà prima un 6 che poi diventerà un 9, ma a questo punto la cifra finale sarà diventata 9 e quindi ricadrai anche nel terzo caso, finendo per aggiungere due cifre in un colpo solo. Quindi per risolvere dovrebbe essere sufficiente cambiare gli ultimi due if in else if.

In più un altro problema è che quando tu chiami solve per la prima volta, hai già inserito una cifra, quindi il numero di cifre da aggiungere non sarebbe N ma N-1. Infatti nel secondo caso d’esempio, il tuo codice genera numeri a tre cifre per il primo, a quattro per il secondo, e a cinque per il terzo, che sono sempre una in più di quelle richieste.

1 Mi Piace
3

grazie mille, ora fa 80/100!
tuttavia c’è ancora un problemino, il test 003 non riporta l’output corretto, hai qualche idea di quale il motivo possa essere?

#include <stdio.h>
#include <assert.h>
#include <algorithm>
using namespace std;

long long int maxr, rest;

void solve(int N, int M, long long int cifre){
    if (N-1 == 0){
        return;
    }

    if(3 == cifre%10){
        cifre *= 10;
        cifre += 6;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }else if(6 == cifre%10){
        cifre *= 10;
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 6;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }else if(9 == cifre%10){
        cifre *= 10;
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
        cifre += 3;
        rest = cifre%M;
        if(rest > maxr){
            maxr = rest;
        }
        solve(N-1, M, cifre);
    }

}

long long occulta(int N, int M) {
    if(N==1){
        return max({3%M, 6%M, 9%M});
    }
    maxr = 0, rest = 0;
    solve(N, M, 3);
    solve(N, M, 6);
    solve(N, M, 9);
    return maxr;
}


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;
}
4

Probabilmente è un caso in cui il modulo massimo è dato da un numero ad una sola cifra.

Infatti al momento cosideri i numeri con una sola cifra solo quando N = 1.

1 Mi Piace
5

ora funziona, grazie moltissimo :slight_smile: .