Ciao, sto cercando di risolvere il problema “cabala”, il codice sembrerebbe corretto ma negli ultimi test case supera il tempo massimo di esecuzione (facendomi totalizzare 70/100). Qualcuno può darmi qualche indicazione su come potrei velocizzarlo? Grazie mille.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
long long max = 0;
FILE *fr, *fw;
int controlloCifreVicine(char seq[], long long N) {
/*Questa funzione verifica che il numero (sottoforrma di array di char,
dove i numeri sono codificati in ASCII) non contenga numeri uguai
in posizioni adiacenti, restituendo 1 oppure 0*/
int flag = 0, i; /*i flag serve per iniziare il controllo una
volta trovata la prima cifra diversa da zero partendo da sinistra*/
if (atoll(seq) == 0) {
return 1; //in caso il numero fosse zero restituisco 1
}
for (i = 0; i < N - 1; i++) {
if (!flag && seq[i] == 48) {
if (seq[i] != 48) {
flag++;
}
} else {
if (seq[i] == seq[i + 1]) {
return 1; /*in caso abbia trovato due numeri
vicini uguali restituisco 1*/
}
}
}
return 0; /*se ho finito l'iterazione e non ho trovato
numeri uguali adiacenti posso restituire zero*/
}
void rec(char num[], long long N, long long M, int pos) {
int i, j;
long long cab;
/*la funzione genera tutti i numeri costituiti da combinazioni di 3, 6 e 9
in maniera ricorsiva: iterando i tre numeri su ciascuna posizione più a destra
di quella data come parametro*/
if (pos == N - 1) { //CONDIZIONE DI STOP: sono arrivato alla cifra piu' a destra
for (i = 3; i < 10; i += 3) {
num[N - 1] = i + 48; // inserisco il valore ASCII del numero interessato
if (controlloCifreVicine(num, N) == 0) { //controllo
cab = atoll(num); /*se il numero rispetta le condizioni lo converto
da array di char ad un long long con funzione di libreria atoll()*/
if (cab % M > max) { //calcolo il modulo e memorizzo il massimo
max = cab % M;
}
}
}
return;
} else {
for (i = 3; i < 10; i += 3) {
num[pos] = i + 48; /*tento i tre valori (in ASCII perche' l'array e' di char)
sulla posizione intereasata*/
rec(num, N, M, pos + 1); //chiamata ricorsiva per le posizioni piuì a destra
}
return;
}
}
long long occulta(long long N, long long M) {
char C[N + 1];
int i;
C[N] = 0;
for (i = 0; i < N; i++) {
C[i] = 48; //inizializzo un vettore che conterra' i numeri della Cabala
}
for (i = N - 1; i >= 0; i--) {
rec(C, N, M, i); /*chiamo la funzione ricorsiva per ciascuna cifra,
partendo dalla meno significativa*/
}
return max;
}
int main() {
long long T, N, M, i;
fr = fopen("input.txt", "r");
fw = fopen("output.txt", "w");
assert(1 == fscanf(fr, "%lld", &T));
for (i=0; i<T; i++) {
assert(2 == fscanf(fr, "%lld %lld", &N, &M));
fprintf(fw,"%lld ", occulta(N, M)); //chiamata alla funzione risolvente
max = 0;
}
fprintf(fw, "\n");
fclose(fr);
fclose(fw);
return 0;
}
