<PREV Problem:
NEXT>
Solved by 553 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Self-describing sequence

Time limit = 2 seconds

Solomon Golomb's self-describing sequence is the only non-decreasing sequence of positive integers with the property that it contains exactly f(k) occurrences of k for each k. A few moments thought reveals that the sequence must begin as follows:

In this problem you are expected to write a program that calculates the value of f(n) given the value of n.

Input One line with an integer n (1 ≤ n ≤ 2 000 000 000 ).

Output Output the value of f(n).

Input#1
100

Output#1
21

Input#2
9999

Output#2
356

Input#3
123456
Output#3
1684

Author:
Miguel Revilla, Valladolid Programming Contest Site
http://acm.uva.es/p/v100/10049.html
6 September 2003

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 23.20.13.165