h2. Clasele 9-10

Primele $5$ locuri din clasamentull de la $9-10$ arata astfel:

Primele $5$ locuri din clasamentul de la $9-10$ arata astfel:

==Rankings(rounds="preoni51a" display_entries="6" pager_style="none")==

O prima rezolvare, si cea mai simpla, este implementarea directa a relatiei de recurenta si conduce la o complexitate $O(N)$ pe set de date. Aceasta abordare ar fi obtinut {$50p$}.In continuare voi descrie o rezolvare $O(lg N)$ care foloseste matrici. Se construieste matricea:
p(pre).

    [0 1 0]

    [0 1 0]

M = [0 0 1]

    [C B A]

    [C B A]

care sta la baza relatiei:
p(pre).

    [I{~0~}]   [I{~1~}]

    [I{~0~}]   [I{~1~}]

M * [I{~1~}] = [I{~2~}]

    [I{~2~}]   [I{~3~}]

    [I{~2~}]   [I{~3~}]

Din asta se deduce: