Cabala Subtask 4

Aiuto
1

come posso rendere il codice più veloce per poter superare l’ultimo subtask del problema?

#include <stdio.h>
#include <assert.h>
#include <iostream>

using namespace std;

bool is_valid(string str){
    if(str.size() > 1 && (str[0] == '3' || str[0] == '6' || str[0] == '9'))
        for(int i = 0; i < str.size()-1; i++)
            if(str[i] == str[i+1] || (str[i+1] != '3' && str[i+1] != '6' && str[i+1] != '9'))
                return false;
    else if(str[0] != '3' && str[0] != '6' && str[0] != '9')
        return false;
    return true;
}

long long occulta(int N, int M) {
    long long max = 0;
    long long res = 0;
    for(long long i = 0, j = 1; i < N; i++, j*=10)
        res+=9*j;
    string str = to_string(res);
    while(str != ""){
        if(is_valid(str) && max < stoll(str)%M)
            max = stoll(str)%M;
        int j;
        for(j = str.size()-1; j >= 0; j--){
            str[j]-=3;
            if(str[j]!='0')
                break;
        }
        if(str[0]=='0')
            str.erase(0,1);
        for(j=j+1 ; j < str.size(); j++){
            str[j] += 9;
        }
    }
    return max;
}


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

Hint: la funzione che genera tutti i numeri viene eseguita per ogni testcase
Consiglio risolutivo: Per quanto il mio aiuto non sia molto utile dato che hai faticosamente gia’ scritto tutto il codice, consiglio di scrivere una funzione che genera tutti i numeri validi da 0 fino a 10^18 una sola volta (sono tanti ma non abbastanza da mandarti fuori tempo) e poi in ogni testcase andare a controllare il modulo nei valori plausibili (esempio: se hai n = 4, i numeri fino a 9696)

3

Il metodo più veloce è generare i numeri in modo ricorsivo invece che provando tutti quelli composti da cifre 3, 6 e 9. Infatti quella soluzione controlla 3^N numeri mentre se li cerchi ricorsivamente ogni volta che aggiungi una cifra hai solo 2 possibilità e quindi generi “solo” circa 2^N possibilità (che sono tutte corrette, quindi non devi neanche controllarle).

4

ho provato ad implementare il consiglio, ora il codice appare cosi:

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

using namespace std;

bool is_valid(string str){
    if(str.size() > 1)
        for(int i = 0; i < str.size()-1; i++)
            if(str[i] == str[i+1])
                return false;
    return true;
}

long long occulta(int N, int M, vector<string>&v) {
    long long max = 0;
    string str;
    for(int i = 0; i < v.size()-1 && v[i].size() <= N; i++)
        if(is_valid(v[i]) && max < stoll(v[i])%M)
            max = stoll(v[i])%M;
    str = v[v.size()-1];   
    while(str.size() < N+1){
        cout << str << endl;
        if(is_valid(str) && max < stoll(str)%M)
            max = stoll(str)%M;
        int j;
        for(j = str.size()-1; j >=0; j--){
            str[j]+=3;
            if(str[j]!='<')
                break;
        }
        if(str[0]=='<'){
            str[0] = '3';
            str += '3';
        }
        for(j=j+1 ; j < str.size(); j++){
            str[j] = '3';
        }
        v.push_back(str);
    }
    return max;
}


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));

    vector<string> v;
    v.push_back("3");

    for (i=0; i<T; i++) {
        assert(2 == fscanf(fr, "%d %d", &N, &M));
        fprintf(fw, "%lld ", occulta(N, M, v));
    }

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

Il problema è che il risultato è lo stesso, rimango a 70/100. Ho sbagliato qualcosa?

5

Non ho ben capito quello che intendi, potresti spiegarmelo in altro modo?

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 due volte aggiungendo al numero con cui è stata chiamata un’altra cifra, è così via finchè non si raggiunge la lunghezza massima.
Ad esempio nel caso N=2 M=68 (secondo esempio di input/output nel testo):
recursion(0, 0, 0) calcola il modulo 0%68 e chiama:
— recursion(3, 3, 1) che calcola il modulo 3%68 e chiama:
— — recursion(6, 63, 2) che calcola il modulo 63%68 e si ferma
— — recursion(9, 93, 2) che calcola il modulo 93%68 e si ferma
— — recursion(3, 33 2) non viene chiamata perché avrebbe due cifre adiacenti uguali
— recursion(6, 6, 1) che calcola il modulo 6%68 e chiama …
— recursion(9, 9, 1) che calcola il modulo 9%68 e chiama …

Se serve mando il codice

7

Salvare l’ultima cifra è solo un’ottimizzazione per non doverla calcolare tutte le volte convertendo il numero in stringa.

8

forse ho capito il ragionamento, riesci a mandarmi lo stesso il codice?

9

Ho risolto implementando la funzione come me l’hai descritta tu, grazie mille!

11

Di niente!