|
|
|
|
描述 Description |
|
|
|
延绵的山(mountain)
在Prascles世界里,有一座绵延的山,有10^1000个山峰.每个山峰的高度不尽相同.经地理学家和数学家研究发现,这座山的山峰高度符合下面的规律:
1.如果把若干个(包括一个)相邻山峰的高度序列看作一个片段的话,就没有两个相邻的片段是完全相同的,如1,2,1,2是不允许的.
2.在满足条件1的前提下,每个山峰高度取最小正整数.
3.满足编号小的山峰高度最小总是比满足编号大的山峰高度最小优先.如前4个山峰的高度为1,2,1,3而不是1,2,3,1.
事实上,从1号山峰开始,各山峰的高度分别为
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,...
但是这么多山峰,10^1000个耶,列出所有山峰的高度是不可能的.现在Prascles世界的人就聘请高级程序师----你来帮助他们,已知山峰编号,求它的高度. |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
只有一行,为山峰编号m.(1<=m<=10^1000)
输入数据没有前导零和多余的空格.
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
只有一行,为山峰高度h. |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
所有数据时限一秒。 |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1558 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
