XTUOJ-1286 Contest

题目描述

有n名选手参加比赛，从1∼n编号。每场比赛由两位选手对决，失败的被淘汰。为了增加比赛的观赏性，举办方并不想比赛双方实力相差太大的，所以决定，每场比赛的两位选手，之前胜场次数之差不能超过1。同时，鸡贼的举办方又不想冠军选手比赛太少了（严重影响比赛收入），希望冠军选手比赛场次越多越好。作为选手的你，当然不希望夺冠路上比赛场次太多，请问在这个赛制下，冠军最多比赛多少场？

输入

存在不超过10000组样例。每行一个整数n(1≤n≤1018)。

输出

每行输出一个样例的结果，为一个整数。

样例输入

1
2
3
10
1000000000000000000

样例输出

0
1
2
4
85

样例解释

我们假定冠军是1号。
第3个样例，1号依次击败2和3号。
第4个样例，其中一种比赛路线是1击败2，3击败4，1击败3，5击败6，1击败5，7击败8，9击败10，7击败9，1击败7。

思路

我第一次做的时候，作为一名光荣的星际玩家，华丽丽地没有看见样例解释。

思考了两分钟，随便手模了一下，认为这应该是让我们求 $$log_{2} X$$。

毕竟两两 PK ，有轮空的也满足题目之前胜场次数之差不能超过 1 的规定。

然后本地就 WA 了。

后来细细思考，发现之前胜场次数之差不能超过 1 的话，我那种方法浪费了很多次冠军出场的机会。

于是重开。

|胜场次数|需要淘汰人数|
|0|0|
|1|1|
|2|1 + 1 = 2|
|3|2 + 1 = 3|
|4|3 + 2 = 5|
|…|…|

胜利 X 场的人，需要淘汰胜利 X - 1 场的人晋级。

于是显然了，斐波那契数列。