A. Tennis Championship
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Famous Brazil city Rio de Janeiro holds a tennis tournament and Ostap Bender doesn’t want to miss this event. There will be n players participating, and the tournament will follow knockout rules from the very first game. That means, that if someone loses a game he leaves the tournament immediately.
Organizers are still arranging tournament grid (i.e. the order games will happen and who is going to play with whom) but they have already fixed one rule: two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played. Of course, both players had to win all their games in order to continue participating in the tournament.
Tournament hasn’t started yet so the audience is a bit bored. Ostap decided to find out what is the maximum number of games the winner of the tournament can take part in (assuming the rule above is used). However, it is unlikely he can deal with this problem without your help.
Input
The only line of the input contains a single integer n (2 ≤ n ≤ 1018) — the number of players to participate in the tournament.
Output
Print the maximum number of games in which the winner of the tournament can take part.
Examples
input
2
output
1
input
3
output
2
input
4
output
2
input
10
output
4
Note
In all samples we consider that player number 1 is the winner.
In the first sample, there would be only one game so the answer is 1.
In the second sample, player 1 can consequently beat players 2 and 3.
In the third sample, player 1 can’t play with each other player as after he plays with players 2 and 3 he can’t play against player 4, as he has 0 games played, while player 1 already played 2. Thus, the answer is 2 and to achieve we make pairs (1, 2) and (3, 4) and then clash the winners.
题意：有n个人打比赛，问最后赢的人最多要打多少场比赛，参加比赛场次相差不过1的两人才能比赛
题解：如果赢了1场比赛，那么至少可能有2个人，如果最后赢了2场比赛，那么至少有3个人比赛，依次类推。数组的序号表示最后一共赢的比赛场次，数组中存的数表示赢那么多场次至少有几人参加比赛。得到类似斐波那契的递推式，如果赢了3场比赛，相当于，在总人数为2人的局中赢了1场，加上在3人局中赢了两场。因此赢3场的情况出现在至少5人局中 依次推算，当赢100场左右时，总人数就会超过1e18，在递推数组中用upper_bound找到n小于某个总人数的位置即是在那个人数下要赢的场次。因为upper_bound找到的是第一个大于n的位置，因此这个位置要-1才是小于等于n的获胜场数
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
long long n,a[556];
a[1]=2;
a[2]=3;
int i=2;
while(a[i]<=1e18)
{
a[++i]=a[i-1]+a[i-2];
}
// for(i=1;i<=100;i++)printf("%d %lld
",i,a[i]);
while(scanf("%lld",&n)!=EOF)
{
int pos=upper_bound(a,a+i+1,n)-a;
printf("%d
",pos-1);
}
}