C. Tennis Championship dp递推 || 找规律

http://codeforces.com/contest/735/problem/C

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

output

input

output

input

output

input

output

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 2and 3 he can't play against player 4, as he has 0 games played, while player 1 already played2. Thus, the answer is 2 and to achieve we make pairs (1, 2) and (3, 4) and then clash the winners.

设dp[i]表示比赛了i局，最小需要的人数。

dp[1] = 2;

dp[2] = 3;

dp[3] = 5;

dp[i] = dp[i - 1] + dp[i -2]

这样是最优的。因为dp[i] = val表示最大那个人比赛了i句，需要的最小人数是val,那么比赛了i局的再和比赛了i - 1局的打，打赢它就能产生i + 1局的结果，由于都是最小人数，所以第i + 1局也是最小人数。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e6 + 20;
struct node {
    LL val;
    LL tim;
    node(LL A, LL B) : val(A), tim(B) {}
    node()  {}
    bool operator < (const struct node & rhs) const {
        return val < rhs.val;
    }
}a[maxn];
int lena;
void init() {
    a[++lena].val = 2;
    a[lena].tim = 1;

    a[++lena].val = 3;
    a[lena].tim = 2;

    a[++lena].val = 5;
    a[lena].tim = 3;

    a[++lena].val = 8;
    a[lena].tim = 4;

    a[++lena].val = 13;
    a[lena].tim = 5;
    LL pre = 8;
    LL last = 13;
    LL to = 6;
    const LL end = 1e18L;
    while (true) {
        if (pre + last < 0) break;
        if (pre + last > end) break;
        ++lena;
        a[lena].val = pre + last;
        a[lena].tim = to++;
        pre = last;
        last = a[lena].val;
//        cout << lena << endl;
//        cout << a[lena].val << endl;
    }
}
void work() {
    LL n;
    cin >> n;
    if (n >= a[lena].val) {
        cout << a[lena].tim << endl;
        return;
    }
    int pos = upper_bound(a + 1, a + 1 + lena, node(n, 0L)) - a;
//    cout << pos << endl;
    cout << a[pos - 1].tim << endl;
//    cout << lena << endl;
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    init();
    work();
    return 0;
}

View Code