C. Tennis Championship
time limit per test
memory limit per test
input
output
n
differs by no more than one
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
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
假设num[i]表示最后的赢家赢i场需要的最少的参赛人数，那么num[i] = num[i-1] + num[i-2]是斐波那契数列，把long long 范围内的斐波那契数全部找出，根据n找到最大num[i]并且num[i] <= n那么i就是答案
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll num[105];
int main(){
num[0] = 1;
num[1] = 2;
for(int i = 2; i <= 90; i++){
num[i] = num[i-1] + num[i-2];
}
ll n;
scanf("%I64d", &n);
int d = upper_bound(num, num + 91, n) - num;
printf("%d\n", d - 1);
return 0;
}