1020 - Sequence

Time Limit : 4 Second

Memory Limit : 128 MB

Submission: 210

Solved: 22

Description
You must have known the sequence define as follows:
a[1]=1;
for every i=1,2,3,...
a[2*i]=a[i];
a[2*i+1]=a[i]+a[i+1];
You can easily prove that every postive number will appear in this sequence.
Now give you a postive number n,your task is to determine the first position n appears.
Input
Only one number n (0<n<400000).
Output
The first position n appears.The answer won't exceed 263-1
sample input
1
2
3
4
sample output
1
3
5
9
hint
64位整型数,用long long定义,输出用%lld。
source
cjq
© 2015 HUST ACMICPC TEAM. All Right Reserved.