Pagini recente » Monitorul de evaluare | Diferente pentru runda/1323/clasament intre reviziile 2 si 1 | Istoria paginii utilizator/amina2002 | Monitorul de evaluare | Diferente pentru deque-si-aplicatii intre reviziile 61 si 60
Nu exista diferente intre titluri.
Diferente intre continut:
Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}Y)$.
p=. !deque-si-aplicatii?sir.png 60%!
Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cuprins între $i - Y$ şi $i - X$ care îndeplineşte optimul. Ce proprietăţi are $j$?
* $i - Y ≤ j ≤ i - X$ şi $MAX - MIN ≤ Z$;
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.