← 返回题目列表

Codeforces · 735/C

C. 网球锦标赛

中文机器翻译题面 查看原题

巴西著名城市里约热内卢举办网球锦标赛,Ostap Bender 不想错过这次赛事。共有n名选手参赛,比赛从第一场开始就实行淘汰赛规则。这意味着,如果有人输了一场比赛,他会立即退出比赛。

组织者仍在安排比赛网格(即比赛进行的顺序以及谁将与谁比赛),但他们已经确定了一项规则:只有当其中一名球员已经参加的比赛数量与另一名球员已经参加的比赛数量相差不超过一局时,两名球员才可以相互比赛。当然,两位选手都必须赢得所有比赛才能继续参加比赛。

比赛还没有开始,观众们有点无聊。 Ostap 决定找出锦标赛获胜者可以参加的最大比赛场数是多少(假设使用上述规则)。然而,如果没有你的帮助,他不太可能解决这个问题。

输入

输入的唯一行包含一个整数 n (2 ≤ n ≤ 1018) — 参加锦标赛的玩家数量。

输出

打印锦标赛获胜者可以参加的最大比赛数。

示例

输入 #1

2

输出 #1

1

输入 #2

3

输出 #2

2

输入 #3

4

输出 #3

2

输入#4

10

输出#4

4

注意

在所有样本中,我们认为 1 号玩家是获胜者。

在第一个示例中,只有一场游戏,因此答案为 1。

在第二个示例中,玩家 1 可以因此击败玩家 2 和 3。

在第三个示例中,玩家 1 无法与其他玩家一起玩,因为在与玩家 2 和 3 玩过之后,他无法与玩家 4 玩,因为他玩了 0 场比赛,而玩家 1 已经玩了 2 场。因此,答案是 2,为了实现这一目标,我们将 (1, 2) 和 (3, 4) 配对,然后与获胜者发生冲突。