A. Tennis Championship

Codeforces

IDCF736A

Time2000ms

Memory256MB

Difficulty—

combinatoricsconstructive algorithmsdfs and similardpmath

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[0] 场），而选手 #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[0] 场），而选手 #cf_span[1] 已经打了 #cf_span[2] 场。因此，答案是 #cf_span[2]，为了达到这个结果，我们先组成配对 #cf_span[(1, 2)] 和 #cf_span[(3, 4)]，然后让胜者对决。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of players, with $ 2 \leq n \leq 10^{18} $. **Constraints** - Tournament is single-elimination. - Two players may compete only if the absolute difference in the number of games each has already played is at most 1. **Objective** Find the maximum number of games the winner can play, under the constraint above. Let $ f(n) $ denote the maximum number of games the winner can participate in. Then: $$ f(n) = \max \left\{ k \in \mathbb{Z}_{\geq 1} \mid F_{k+2} \leq n \right\} $$ where $ F_i $ is the $ i $-th Fibonacci number with $ F_1 = 1, F_2 = 1, F_3 = 2, \dots $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "A. 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": "CF736A"
  },
  "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": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of players, with $ 2 \\leq n \\leq 10^{18} $.  \n\n**Constraints**  \n- Tournament is single-elimination.  \n- Two players may compete only if the ab...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments