【17.76%】【codeforces round 382C】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 * the winners.

题目链接:http://codeforces.com/contest/735/problem/C

【题解】



类斐波那契数列，找规律.

列个表;

n ans
2 1
3 2
4 2
5 3
6 3
7 3
8 4
9 4
10 4
11 4
12 4
13 5

n=x的情况可以转化为max(ans(n=a),ans(n=b))+1其中a+b==x;

选择的a和b的ans要为相邻的即abs(ans(a)-ans(b))<=1;

这就相当于两个人都击败了若干个对手，然后再在一起打一场;

比如上面的表;

n=9 = max(ans(n=4),ans(n=5))+1=max(2,3)+1==4;

考虑第一次出现ans=1的位置为n=2;

第一次出现ans=2的位置为n=3;

则第一次出现ans=3的位置为n=5;

且3,4的ans都为2；

即

n***2 3 4 5

ans 1 2 2 3

考虑第一次出现ans=2的位置为n==3;

第一次出现ans = 3的位置为n==5;

则则第一次出现ans=max(2,3)+1==4的位置为n==8;

且n=5,6,7的时候ans==3;因为6=3+3,7=3+4;

即

n***2 3 4 5 6 7 8

ans 1 2 2 3 3 3 4

同理

第一次出现ans = 3的位置为n==5;

第一次出现ans =4的位置为n=8;

则第一次出现ans=max(3,4)+1==5的位置为n==13;

且n=8,9,10,11,12时,ans=4；因为8=5+3,9 = 5+4,10=5+5,11=5+6,12=5+7

即

n***2 3 4 5 6 7 8 9 10 11 12 13

ans 1 2 2 3 3 3 4 4 *4 **4 *4 *5

由此可以写出程序

(注意开LONG LONG)

    cin >> n;
    ans[2] = 1;ans[3] = 2;//n<=3的情况直接写出来;
    if (n>3)
    {
        LL a = 2,b = 3,c=a+b;
        LL now = 2;
        while (c <=n)//如果n大于等于a+b,则表示ans可以再增大
        {
            a = b;b = c;//a变成now-1第一次出现的位置,b变成now第一次出现的位置
            c = a+b;//则c就变成now+1第一次出现的位置了;
            now++;//所代表的ans递增;
        }
        cout << now << end;
    }
    else
        cout << ans[n];     

【完整代码】

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

void rel(LL &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t) && t!='-') t = getchar();
    LL sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

void rei(int &r)
{
    r = 0;
    char t = getchar();
    while (!isdigit(t)&&t!='-') t = getchar();
    int sign = 1;
    if (t == '-')sign = -1;
    while (!isdigit(t)) t = getchar();
    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
    r = r*sign;
}

//const int MAXN = x;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
int ans[5];
LL n,now = 0;

int main()
{
    while (cin>>n)
    {
        ans[2] = 1;ans[3] = 2;
        if (n>3)
        {
            LL a = 2,b = 3,c=a+b;
            now = 2;
            while (c <=n)
            {
                a = b;b = c;
                c = a+b;
                now++;
            }
            cout << now << endl;
        }
        else
            cout << ans[n]<<endl;
    }
    return 0;
}