问题描述

小R正在组织一个比赛，比赛中有n支队伍参赛。比赛遵循以下独特的赛制：

• 如果当前队伍数为偶数，那么每支队伍都会与另一支队伍配对。总共进行n / 2场比赛，且产生n / 2支队伍进入下一轮。
• 如果当前队伍数为奇数，那么将会随机轮空并晋级一支队伍，其余的队伍配对。总共进行(n - 1) / 2场比赛，且产生(n - 1) / 2 + 1支队伍进入下一轮。

小R想知道在比赛中进行的总比赛场次（即所有轮次比赛场次之和），直到决出唯一的获胜队伍为止。

输入格式

• 输入为一个整数n（1 ≤ n ≤ 10^6），表示初始队伍数量。

输出格式

• 输出一个整数，表示比赛的总场次。

测试样例

样例1

输入：7输出：6

解释：

• 第一轮：7 支队伍（奇数），进行 (7-1)/2 = 3 场比赛，晋级 3 + 1 = 4 支队伍。
• 第二轮：4 支队伍（偶数），进行 4/2 = 2 场比赛，晋级 2 支队伍。
• 第三轮：2 支队伍（偶数），进行 2/2 = 1 场比赛，晋级 1 支队伍（冠军）。 总比赛场次 = 3 + 2 + 1 = 6。

样例2

输入：14输出：13

解释：

• 第一轮：14 支队伍（偶数），进行 14/2 = 7 场比赛，晋级 7 支队伍。
• 第二轮：7 支队伍（奇数），进行 (7-1)/2 = 3 场比赛，晋级 3 + 1 = 4 支队伍。
• 第三轮：4 支队伍（偶数），进行 4/2 = 2 场比赛，晋级 2 支队伍。
• 第四轮：2 支队伍（偶数），进行 2/2 = 1 场比赛，晋级 1 支队伍（冠军）。 总比赛场次 = 7 + 3 + 2 + 1 = 13。

样例3

输入：1输出：0

解释：

• 只有 1 支队伍，无需比赛，直接晋级，总比赛场次为 0。

约束条件

• 1 ≤ n ≤ 10^6

程序代码

#include <stdio.h>

int totalMatches(int n) {

// 每场比赛淘汰1支队伍，淘汰 n-1 支队伍需要 n-1 场比赛

return n - 1;

}

int main() {

int n;

scanf("%d", &n);

printf("%d\n", totalMatches(n));

return 0;

}

#include <stdio.h> int totalMatches(int n) { // 每场比赛淘汰1支队伍，淘汰 n-1 支队伍需要 n-1 场比赛 return n - 1; } int main() { int n; scanf("%d", &n); printf("%d\n", totalMatches(n)); return 0; }

运行结果