CSES - Lukujono
- Time limit: 4.00 s
- Memory limit: 128 MB
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.
Rajat
- 1≤n≤105
- Voit olettaa, että Un on enintään 109.
Esimerkki
Syöte:
10
Tuloste:
13
Selitys:
- U1=1
- U2=U1=1
- U3=U1+U1=2
- U5=U2+U1+U1+U1=4
- U10=U5+U3+U2+U2+U1+U1+U1+U1+U1=13