Lotteria 2 casi sbagliati

Per svolgere lotteria ho provato ad implementare una semplice funzione che ricorsive che trova tutte le possibili combinazioni usando la memoizzazzione, ci sono comunque 2 casi che danno un output sbagliati ma non riesco a capire perché? C’è qualche errore?

    #include<fstream>
    #include<math.h>
    using namespace std;
    int n , m, mem[400000][20], jmax[20];
    int f(int i,  int k)
    {
    	if(k==n)		return 1;	
    	int somma=0;
    	if(mem[i][k]!=0)
    		return mem[i][k];
    	else	
    		for(int j=i*2;j<=jmax[k];j++)
    			{
    				int ris=f(j, k+1);
    				ris%=1000000007;
    				somma+=ris;
    				somma%= 1000000007;
    			}	
    	mem[i][k]=somma;
    	return somma;
    }
    int main()
    {
    	ifstream in("input.txt");
    	ofstream out("output.txt");
    	in>>n>>m;
    	jmax[n-1]=m;
    	for(int i=n-2;i>=0;i--)	jmax[i]=jmax[i+1]/2;
    	int somma=0;
    	for(int i=1;i<m;i++)
    	{
    		int ris=f(i, 1);
    		ris%= 1000000007;
    		somma+=ris;
    		somma%= 1000000007;
    	}
    	out<<somma;
    	
    }

Ok ho trovato l’errore era molto banale, ma ottengo un 70/100 anche utilizzando la memoizzazione.

Qualche consiglio per il 100?
Quello che mi chiedo è come possono alcuni codici sottoposti farlo anche in meno di 0.030 :sweat_smile:

1 Mi Piace

Ciao,
a prima vista nella tua soluzione hai N*M stati calcolati ciascuno in O(M), quindi la soluzione finale diventa O(N*M^2) che con M=200000 va un po’ fuori tempo. I tempi che vedi provengono da una soluzione in O(N*M).

2 Mi Piace

Sisi trovata grazie mille!!

1 Mi Piace