Ciao, sto cercando di risolvere lotteria, ma non riesco a capire come mai la mia soluzione non funziona.
Premetto che ho dato solo una rapida occhiata alla soluzione ufficiale, tralasciandone diverse parti, dunque ne ho appena una vaga idea.
Comunque, la mia soluzione (che dovrebbe essere O(n*m)) si basa sostanzialmente su una funzione calcola(n,m) (definita per n,m > 0), la quale restituisce il numero di sequenze che ci interessano di lunghezza n e aventi i termini <= m, definita per ricorrenza come segue:
calcola(n,m) =
- 1 se n = 1
- 0 se m < 2^(n-1)
- somma per i che varia da 2^(n-1) a m di calcola(n-1,[i/2])
dove [x] è la parte intera di x.
Ora, non solo totalizza 0 punti, ma la cosa strana è che non risolve neppure un’istanza del Subtask 2, mentre ne prende alcune dei Subtask 3 e 4. Eppure ho fatto decine di test in locale e sembra che per valori non troppo alti funzioni…