<PREV Problem:
NEXT>
Solved by 553 users: ...
UserDateAttemptTimeCMSC
FordPerfect24 feb 2010C++2700.0245 
Vyshnya02 mar 2010C++4200.0245 
FordPerfect21 feb 2010C++2500.0246 
Vyshnya22 feb 2010C++3800.0246 
Vyshnya19 feb 2010C++2200.0249 
FordPerfect19 feb 2010C++2400.0249 
FordPerfect24 feb 2010C++2600.0249 
Vyshnya21 feb 2010C++2800.0249 
Vyshnya21 feb 2010C++2900.0249 
FordPerfect19 feb 2010C++2300.0251 
david_it2103 nov 2009Ruby202.4454 
shurik18 feb 2010Ruby506.7474 
Philip_PV09 jul 2008C300.0276 
faraaz10226 dec 2007C++600.0280 
tuzihao24 aug 2011C++200.0281 
old110 apr 2006C++200.0381 
sridhar8729 jun 2007C++500.0282 
faraaz10226 dec 2007C++500.0282 
SGi24 aug 2008FPC500.0284 
SGi24 aug 2008FPC600.0284 
Languages
C++
273
FPC
163
C
69
Java
23
Kylix
21
Ruby
5
Python
5
Perl
2
Lua
1
Scheme
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 200ms

SW soft NIX
ID = 3.235.30.155