#3951
Function
Avem o funcție F
definită pe numere naturale. \(F(x) = \begin{cases} Y, x = 0 \\ \sum_{i=0}^{x-1} F(i) \end{cases}\). Primim Q
interogări de tipul st dr
, pentru fiecare interogare trebuie să spunem cât este \(\sum_{i=st}^{dr}F(i)\) modulo \(10^9+7\).
idee proprie
Problema | Function | Operații I/O |
![]() |
---|---|---|---|
Limita timp | 0.3 secunde | Limita memorie |
Total: 1 MB
/
Stivă 1 MB
|
Id soluție | #51470494 | Utilizator | |
Fișier | function.cpp | Dimensiune | 1.34 KB |
Data încărcării | 23 Iunie 2024, 12:14 | Scor / rezultat | Eroare de compilare |
function.cpp:2:1: error: stray '\304' in program Problema cu acest cod este complexitatea algoritmică a funcției f. Aceasta funcție este recursivă și are o complexitate exponențială, deoarece pentru fiecare apel recursiv, ea apelează din nou f de mai multe ori. ^ function.cpp:2:1: error: stray '\203' in program function.cpp:2:1: error: stray '\310' in program function.cpp:2:1: error: stray '\233' in program function.cpp:2:1: error: stray '\310' in program function.cpp:2:1: error: stray '\233' in program function.cpp:2:1: error: stray '\304' in program function.cpp:2:1: error: stray '\203' in program function.cpp:2:1: error: stray '\310' in program function.cpp:2:1: error: stray '\231' in program function.cpp:2:1: error: stray '\310' in program function.cpp:2:1: error: stray '\233' in program function.cpp:2:1: error: stray '\304' in program function.cpp:2:1: error: stray '\203' in program function.cpp:2:1: error: stray '\304' in program function.cpp:2:1: error: stray '\203' in program function.cpp:4:1: error: stray '\304' in program Să analizăm ce se întâmplă în funcția f. La fiecare apel pentru f(x), ai un ciclu for care apelează f(i) de la 0 la x-1. Asta înseamnă că pentru f(x), numărul de apeluri recursive crește exponențial, ceea ce face ca timpul de execuție să crească foarte repede chiar și pentru valori mici ale lui x. ^ function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\303' in program function.cpp:4:1: error: stray '\256' in program function.cpp:4:1: error: stray '\303' in program function.cpp:4:1: error: stray '\242' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\303' in program function.cpp:4:1: error: stray '\256' in program function.cpp:4:1: error: stray '\310' in program function.cpp:4:1: error: stray '\233' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\303' in program function.cpp:4:1: error: stray '\256' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\310' in program function.cpp:4:1: error: stray '\231' in program function.cpp:4:1: error: stray '\310' in program function.cpp:4:1: error: stray '\233' in program function.cpp:4:1: error: stray '\310' in program function.cpp:4:1: error: stray '\233' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\304' in program function.cpp:4:1: error: stray '\203' in program function.cpp:4:1: error: stray '\310' in program function.cpp:4:1: error: stray '\231' in program function.cpp:6:1: error: stray '\304' in program Pentru a remedia această problemă, putem utiliza memoizare, o tehnică prin care salvăm rezultatele intermediare ale funcțiilor într-un tabel pentru a evita recalcularea acestora. ^ function.cpp:6:1: error: stray '\203' in program function.cpp:6:1: error: stray '\304' in program function.cpp:6:1: error: stray '\203' in program function.cpp:6:1: error: stray '\304' in program function.cpp:6:1: error: stray '\203' in program function.cpp:6:1: error: stray '\304' in program function.cpp:6:1: error: stray '\203' in program function.cpp:6:1: error: stray '\310' in program function.cpp:6:1: error: stray '\233' in program function.cpp:6:1: error: stray '\303' in program function.cpp:6:1: error: stray '\256' in program function.cpp:8:1: error: stray '\304' in program Iată cum poți modifica codul pentru a include memoizarea: ^ function.cpp:8:1: error: stray '\203' in program function.cpp:8:1: error: stray '\310' in program function.cpp:8:1: error: stray '\233' in program function.cpp:2:1: error: 'Problema' does not name a type Problema cu acest cod este complexitatea algoritmică a funcției f. Aceasta funcție este recursivă și are o complexitate exponențială, deoarece pentru fiecare apel recursiv, ea apelează din nou f de mai multe ori. ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Function face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.