# Cabala Subtask 4

**URL:** <https://forum.olinfo.it/t/cabala-subtask-4/7420>\
**Category:** Aiuto\
**Created:** [13 Giugno 2022, 12:39pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420 "2022-06-13T12:39:09Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Sixes](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/54ee81/32.png) [@Sixes](https://forum.olinfo.it/u/Sixes)\
**Post date:** [13 Giugno 2022, 12:39pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/1 "2022-06-13T12:39:09Z")

</div>

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

```auto
#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;
}

```

---

<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:** [13 Giugno 2022, 1:54pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/2 "2022-06-13T13:54:37Z")

</div>

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)

---

<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:** [13 Giugno 2022, 2:04pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/3 "2022-06-13T14:04:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sixes](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/54ee81/32.png) [@Sixes](https://forum.olinfo.it/u/Sixes)\
**Post date:** [13 Giugno 2022, 3:12pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/4 "2022-06-13T15:12:13Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![Sixes](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/54ee81/32.png) [@Sixes](https://forum.olinfo.it/u/Sixes)\
**Post date:** [13 Giugno 2022, 3:13pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/5 "2022-06-13T15:13:10Z")

</div>

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

---

<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:** [13 Giugno 2022, 4:59pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/6 "2022-06-13T16:59:38Z")

</div>

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

---

<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:** [13 Giugno 2022, 5:03pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/7 "2022-06-13T17:03:00Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sixes](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/54ee81/32.png) [@Sixes](https://forum.olinfo.it/u/Sixes)\
**Post date:** [13 Giugno 2022, 5:12pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/8 "2022-06-13T17:12:57Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Sixes](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/54ee81/32.png) [@Sixes](https://forum.olinfo.it/u/Sixes)\
**Post date:** [13 Giugno 2022, 6:03pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/9 "2022-06-13T18:03:10Z")

</div>

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

---

<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:** [13 Giugno 2022, 6:05pm UTC](https://forum.olinfo.it/t/cabala-subtask-4/7420/11 "2022-06-13T18:05:07Z")

</div>

Di niente!