Cabala TLE 70/100

Aiuto
1

Buongiorno programmatori! Mi ritrovo costretto a chiedere aiuto, non riesco a capire come ottimizzare per non andare fuori tempo sull’ultimo subtask di cabala.

Ho cercato di rendere il codice più leggibile possibile, essenzialmente per evitare le cifre adiacenti controllo il resto per 10 del numero attualmente in esame e concateno i multipli di 3 diversi da quel numero (quindi se ho 639 faccio 639%10==9, di conseguenza ottengo 6393 e 6396)

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

using namespace std;
long int max = 0;

long int rec(long int cabala, int cifre, int N, int M){
    if(cabala==0){
        rec(3, cifre, N, M);
        rec(6, cifre, N, M);
        rec(9, cifre, N, M);    
    }
    if(cabala%M > max){
        max = cabala%M;
    }
    while(cifre < N){
        cifre++;
        if(cabala%10==3){
            rec(cabala*10+6, cifre, N, M);
            rec(cabala*10+9, cifre, N, M);
        } else if(cabala%10==6){
            rec(cabala*10+3, cifre, N, M);
            rec(cabala*10+9, cifre, N, M);
        } else if(cabala%10==9){
            rec(cabala*10+6, cifre, N, M);
            rec(cabala*10+3, cifre, N, M);
        }
    }
    return max;
}

long int occulta(int N, int M) {
    long int cabala = 0;
    max = 0;
    max = rec(cabala, 1, N, M);
    return max;
}
2

Salve, alla fine quello che fa il tuo algoritmo è iterare su tutti i possibili valori che rispettano i vincoli richiesti nel testo per poi prendere quello che massimizza il resto se diviso per M. Come puoi notare ci sono T testcases con T \leq 50, se tutti i 50 testcases avessero N=18 allora tu genereresti tutti i possibili numeri 50 volte. Nonostante sia vero che potenzialmente poi devi iterare comunque 50 volte su tali numeri è comunque inutile generarli più volte. Generali un’unica volta e memorizzali.

Inoltre, per migliorare l’efficienze, la generazione di tali numeri puoi farla iterativa. Supponi che cab[i] contenga i numeri validi con i cifre, puoi generare velocemente cab[i + 1]? (il ragionamento è identico a quello che hai applicato per la versione ricorsiva).

Infine, se proprio volessi minimizzare i tempi di esecuzione, puoi pre-calcolare una porzione dei cab[i], ma non dovresti avere miglioramenti drastici.

3

corretto

#include <limits.h>
#include <stdio.h>

long long maxMod = -1;

// Fast exponentiation O(log exp)
long long power(int base, int exp) {
	if (exp == 0) return 1;
	long long r = power(base, exp / 2);
	r = r * r;
	if (exp % 2 == 1) r = base * r;
	return r;
}

// We recurse through every single possible digit to find the one with the highest 
// number after modulo operation
void recursive(int N, int n, long long M, long long calculated, int lastDigit) {
	if (n == N) return;
	for (int i = 3; i <= 9; i+=3) {
		if (i == lastDigit) continue;
		long long newCalc = calculated + (i * power(10, n));
		if (newCalc % M > maxMod) maxMod = newCalc % M;
		recursive(N, n + 1, M, newCalc, i);
	}

}

long long occulta(int N, long long M) {
	recursive(N, 0, M, 0, 0);
	return maxMod;
}

int main() {
	int T;
	FILE *fr, *fw;
	fr = fopen("input.txt", "r");
	fw = fopen("output.txt", "w");

	// Read each testcase
	fscanf(fr, "%d", &T);
	for (int i = 0; i < T; i++) {
		maxMod = -1;
		int N;
		long long M;
		fscanf(fr, "%d %lld", &N, &M);
		fprintf(fw, "%lld ", occulta(N, M));
	}
	return 0;
}
4

Ciao @nico7475. Credevo di essere un buon cper, prima che tu ottenessi su training in due giorni i punti che ho fatto che ho fatto in un anno e mezzo.
Dunque ti chiedo aiuto e guida spirituale verso la suprema arte di usare fastexp per calcolare 10^{18}.
Per favore introducimi ai culti misterici e cabalistici che ti permettono di risolvere problemi di questa portata.
Ti ringrazio.

12 Mi Piace