C. Tennis Championship

Codeforces

IDCF735C

Time2000ms

Memory256MB

Difficulty—

combinatoricsconstructive algorithmsgreedymath

English · Original

Chinese · Translation

Formal · Original

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. [samples] ## 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.

著名的巴西城市里约热内卢举办了一场网球锦标赛，奥斯塔普·本德不想错过这一赛事。将有 #cf_span[n] 名选手参赛，锦标赛从第一场比赛开始就采用淘汰制，这意味着一旦某位选手输掉一场比赛，他将立即被淘汰。组织者仍在安排赛程（即比赛的顺序和对阵安排），但他们已经固定了一条规则：两名选手只有在他们已进行的比赛场数之差不超过一的情况下才能相互对阵。当然，两名选手都必须赢得所有之前的比赛才能继续参赛。锦标赛尚未开始，观众有些无聊。奥斯塔普决定找出冠军最多能参加多少场比赛（假设使用上述规则）。然而，他很可能无法在没有你帮助的情况下解决这个问题。输入仅包含一行，一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 1018]）——参赛选手的数量。请输出冠军最多能参加的比赛场数。在所有样例中，我们假设选手编号为 #cf_span[1] 的是冠军。在第一个样例中，仅有一场比赛，因此答案为 #cf_span[1]。在第二个样例中，选手 #cf_span[1] 可以依次击败选手 #cf_span[2] 和 #cf_span[3]。在第三个样例中，选手 #cf_span[1] 无法与每位其他选手比赛，因为在他击败了选手 #cf_span[2] 和 #cf_span[3] 之后，他无法与选手 #cf_span[4] 对阵，因为选手 #cf_span[4] 尚未进行任何比赛，而选手 #cf_span[1] 已经打了 #cf_span[2] 场。因此，答案是 #cf_span[2]，为了实现这一点，我们安排配对 #cf_span[(1, 2)] 和 #cf_span[(3, 4)]，然后让胜者对决。 ## Input 输入仅包含一行，一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 1018]）——参赛选手的数量。 ## Output 请输出冠军最多能参加的比赛场数。 [samples] ## Note 在所有样例中，我们假设选手编号为 #cf_span[1] 的是冠军。在第一个样例中，仅有一场比赛，因此答案为 #cf_span[1]。在第二个样例中，选手 #cf_span[1] 可以依次击败选手 #cf_span[2] 和 #cf_span[3]。在第三个样例中，选手 #cf_span[1] 无法与每位其他选手比赛，因为在他击败了选手 #cf_span[2] 和 #cf_span[3] 之后，他无法与选手 #cf_span[4] 对阵，因为选手 #cf_span[4] 尚未进行任何比赛，而选手 #cf_span[1] 已经打了 #cf_span[2] 场。因此，答案是 #cf_span[2]，为了实现这一点，我们安排配对 #cf_span[(1, 2)] 和 #cf_span[(3, 4)]，然后让胜者对决。

Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 10^{18} $ be the number of players. Define $ f(n) $ as the maximum number of games the winner can play under the constraint that two players may only compete if the number of games each has already played differs by at most one. **Objective**: Compute $ f(n) $, where $ f(n) $ satisfies the recurrence: $$ f(1) = 0, \quad f(2) = 1 $$ $$ f(n) = \max_{\substack{a + b = n \\ |f(a) - f(b)| \leq 1}} \left(1 + \max(f(a), f(b))\right) $$ Equivalently, $ f(n) $ is the largest integer $ k $ such that the $ k $-th Fibonacci number $ F_{k+2} \leq n $, i.e., $$ f(n) = \max \{ k \in \mathbb{N} \mid F_{k+2} \leq n \} $$ where $ F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, \dots $ is the Fibonacci sequence. **Output**: $ f(n) $

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "C. Tennis Championship",
    "description": {
      "content": "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 fro",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF735C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 fro...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "著名的巴西城市里约热内卢举办了一场网球锦标赛，奥斯塔普·本德不想错过这一赛事。将有 #cf_span[n] 名选手参赛，锦标赛从第一场比赛开始就采用淘汰制，这意味着一旦某位选手输掉一场比赛，他将立即被淘汰。\n\n组织者仍在安排赛程（即比赛的顺序和对阵安排），但他们已经固定了一条规则：两名选手只有在他们已进行的比赛场数之差不超过一的情况下才能相互对阵。当然，两名选手都必须赢得所有之前的比赛才能继续参赛...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^{18} $ be the number of players.\n\nDefine $ f(n) $ as the maximum number of games the winner can play under the constraint that two players may only com...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments