Lukujono |
| Time limit: | 4.00 s |
| Memory limit: | 128 MB |
|
Aikaraja: 4 s
Fibonaccin lukujono $(F_n)$ on erittäin tunnettu lukujono, ja se määritellään seuraavasti:
- $F_0 = 0$
- $F_1 = 1$
- $F_n = F_{n - 1} + F_{n - 2}$, jos $n \geq 2$.
Paljon vähemmälle huomiolle on jäänyt Uolevinaccin lukujono $(U_n)$, joka määritellään seuraavasti:
- $U_0 = 0$
- $U_1 = 1$
- $U_n = U_{\lfloor n/2\rfloor} + U_{\lfloor n/3\rfloor} + U_{\lfloor n/4\rfloor} + U_{\lfloor n/5\rfloor} + \ldots + U_{\lfloor n/n\rfloor}$, jos $n \geq 2$.
Merkintä $\lfloor x \rfloor$ tarkoittaa lukua $x$ pyöristettynä alaspäin kokonaisluvuksi.
Syöte
Syötteenä annetaan yksi kokonaisluku $n$.
Tuloste
Tulosteen tulee olla luku $U_n$.
Voit olettaa, että $U_n$ on enintään $10^{18}$.
Esimerkki
Syöte:
10
Tuloste:
13
Selitys: $U_{10} = U_5 + U_3 + U_2 + U_2 + U_1 + U_1 + U_1 + U_1 + U_1$.
Osatehtävä 1 (16 pistettä)
Osatehtävä 2 (34 pistettä)
Osatehtävä 3 (50 pistettä)
