Ho un problema con l’ultimo test case di “numero della cabala”, come scritto nel titolo, mi dà execution time error. Questo è il codice:
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long occulta(int N, int M, string n, int res) {
long long lim = pow(10, N-1);
long long l;
for (int i = 3; i < 10; i=i+3){
if ((n != "" ? n[n.size()-1] : '/') != char(i+48)){
if (stoll(n+char(i+48))%M > res)
res = stoll(n+char(i+48))%M;
if (stoll(n+char(i+48)) < lim){
l = occulta(N, M, n+char(i+48), res);
if (l > res)
res = l;
}
}
}
return res;
}
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, "%d ", occulta(N, M, "", 0));
}
fprintf(fw, "\n");
fclose(fr);
fclose(fw);
return 0;
}
Qualcuno sa qualche modo per ottimizzarlo?
Ciao, l’errore che ottieni è “Execution timed out”.
Banalmente, la tua soluzione va fuori tempo limite di esecuzione.
Non ho capito bene la tua logica per suggeriti cosa migliorare, puoi spiegarla ? Comunque si può evitare la funzione stoll.
Va bene, cercherò di spiegarla al meglio che posso:
Praticamente ad ogni ciclo vedo prima di tutto se n+i (n all’inizio è “” e i è un numero fra 3,6 e 9) , che è il numero della cabala corrente, se non ha cifre adiacenti uguale, se è cosi, vedo se quel numero della cabala modulo M è il massimo, e poi vedo se n+i+i è maggiore del limite (questo l’ho fatto semplicemente diminuendo di una potenza di 10 N, quindi se N=3, allora sarà 10^2), questo perché il numero della cabala corrente è N+i.
Spero di essermi spiegato bene, comunque come si può evitare la funzione stoll?
Perfetto. La logica è corretta, devi solo implementarla più efficientemente.
Per evitare la funzione stoll, ti basta moltiplicare il numero che stai valutando per 10 e addizionare la cifra che vuoi aggiungere.
Ti consiglio anche di evitare di calcolarti ogni volta la variabile lim attraverso pow, ha complessità lineare rispetto all’esponente. Cerca un modo più furbo di interrompere la ricorsione senza questo calcolo.
Innanzitutto grazie per i consigli, adesso il codice è diventato cosi:
#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long fast_atoi( const char * str )
{
long long val = 0;
while( *str ) {
val = val*10 + (*str++ - '0');
}
return val;
}
long long occulta(int N, int M, string n, int res) {
long long l;
for (int i = 3; i < 10; i=i+3){
if ((n != "" ? n[n.size()-1] : '/') != char(i+48)){
if ((((n != "" ? fast_atoi(n.c_str()) : 0)*10)+i)%M > res)
res = (((n != "" ? fast_atoi(n.c_str()) : 0)*10)+i)%M;
if ((n+char(i+48)).size() < N){
l = occulta(N, M, n+char(i+48), res);
if (l > res)
res = l;
}
}
}
return res;
}
Come puoi vedere non sono riuscito a togliere il fatto di convertire la stringa n in intero, ma sono riuscito a trovare un modo più furbo di interrompere la funzione, ma non va comunque, anzi, mentre tutti gli altri test case sono migliorati, l’ultimo è peggiorato:
Questo è quanto faceva prima dei miglioramenti.
Questo è quanto fa adesso, non so come potrei migliorarlo ancora
Comunque i tempi sono migliorati notevolmente (l’ultimo non fa testo).
Il tempo che leggi nei test case che vanno fuori tempo massimo non è il tempo di fine esecuzione di quel test case ma è solo il tempo, a partire dall’inizio delle elaborazioni, nel quale l’esecuzione del processo che si occupava di risolvere il testcase, è stato arrestato (un pò dopo il tempo massimo a disposizione).
Non intendevo proprio questo con il trucco di moltiplicare per 10 
int f(int n){
f(n * 10 + 3);
f(n * 10 + 6);
f(n * 10 + 9);
}
Intendevo una cosa simile, cosi non devi ogni volta convertire da stringa. Ricordati il modulo!
In questo modo dovrebbe risultare più facile capire quando fermare la ricorsione 
Hints:
-
Il numero di cifre è determinante .
-
Il numero di cifre è la profondità della funzione ricorsiva.
-
Ti basta aggiungere un parametro alla funzione che si incrementa con la profondità.
I numeri da trovare possono essere parecchi, non potrebbe essere il caso di trovarli una tantum per il massimo N invece di T volte?
Grazie per l’aiuto!, Adesso ho 100/100, Alla fine bastava cambiare il tipo di n a long long, e cambiare il tutto a sua volta