当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2370:Convert Kilometers to Miles

题目描述
This year, Bruce Force spends his vacation in Flagstaff, Arizona, where he wants to practice for his next half marathon (a race over 21 km). At his first training he runs to his friend Greedy Gonzales' home which is 21 miles away from Flagstaff.

Arriving there, he is very tired and realizes that 21 miles are much more than 21 km. Greedy Gonzales tells him that 21 km equals 13 miles. 21, 13? Bruce realizes immediately that there must be a deeper relation! Both, 13 and 21 are Fibonacci numbers!

Fibonacci numbers can be defined as follows:

F1 = 1
F2 = 2
Fn+1 = Fn+Fn-1 for n>1.

Bruce has just learned about the Fibonacci number system at his university. Each positive integer x can be written as the sum of different Fibonacci numbers, so this means that there exists numbers k and b1, b2, ..., bk such that x = ∑i=1..k bi * Fi, where bk = 1 and bi (1 ≤ i < k) is either 0 or 1. In short, we can write the representation as: b(x) = (bk, bk-1, ..., b1). To make the representation unique, we require that bi * bi-1 = 0 for all i > 1.

For example 21 can be represented as (1,0,0,0,0,0,0) and 13 as (1,0,0,0,0,0) in the Fibonacci system. Bruce notices that one can convert a distance x in kilometers into a corresponding distance y to miles as follows: First, write down x in its Fibonacci system representation b(x). Second, shift the bits of b(x) one position to the right (the last bit is deleted) and get b(y). Third, calculate y from b(y) by evaluating the sum given above.

For example, the number 42 written in the Fibonacci system is (1,0,0,1,0,0,0,0). In step two we would shift the bits one position to the right and get (1,0,0,1,0,0,0). In the third step, we would calculate 0*1 + 0*2 + 0*3 + 1*5 + 0*8 + 0*13 + 1*21 = 26.

Now it's your turn to write a program for Bruce that converts kilometers into miles according to Bruce's algorithm.
输入解释
The first line of the input contains t, the number of distances Bruce wants to convert from kilometers to miles (0<t<25000). Each of the next t lines contains an integer distance x (2 < x < 25000) in kilometers.
输出解释
For each distance x in kilometers output the distance y in miles calculated according to Bruce's algorithm.
输入样例
5
42
100
180
300
360
输出样例
26
62
111
185
222
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-2370

最后修改于 2020-10-25T22:52:51+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000/1000MS(Java/Others) 32768/32768K(Java/Others)