CSES - Datatähti 2015 loppu - Lukujono
- Time limit: 4.00 s
- Memory limit: 128 MB
Aikaraja: 4 s
Fibonaccin lukujono (Fn) on erittäin tunnettu lukujono, ja se määritellään seuraavasti:
- F0=0
- F1=1
- Fn=Fn−1+Fn−2, jos n≥2.
Paljon vähemmälle huomiolle on jäänyt Uolevinaccin lukujono (Un), joka määritellään seuraavasti:
- U0=0
- U1=1
- Un=U⌊n/2⌋+U⌊n/3⌋+U⌊n/4⌋+U⌊n/5⌋+…+U⌊n/n⌋, jos n≥2.
Merkintä ⌊x⌋ tarkoittaa lukua x pyöristettynä alaspäin kokonaisluvuksi.
Syöte
Syötteenä annetaan yksi kokonaisluku n.
Tuloste
Tulosteen tulee olla luku Un.
Voit olettaa, että Un on enintään 1018.
Esimerkki
Syöte:
10
Tuloste:
13
Selitys: U10=U5+U3+U2+U2+U1+U1+U1+U1+U1.
Osatehtävä 1 (16 pistettä)
- 1≤n≤103
Osatehtävä 2 (34 pistettä)
- 1≤n≤105
Osatehtävä 3 (50 pistettä)
- 1≤n≤108