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 场的人晋级。

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

文章目录