← 返回题目列表

Codeforces · 1310/B

B. 双败淘汰制

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

年度最大赛事——Cota 2 世界锦标赛“The Innernational”即将到来。 $$$2^n$$$ 队伍将以双败淘汰赛的形式进行比赛(请仔细阅读问题陈述,即使你知道问题陈述是什么),以确定冠军。

队伍编号从 $$$1$$$ 到 $$$2^n$$$,并且将进行一对一的比赛。所有球队都从胜者组开始。

所有胜者组比赛将在尚未输掉任何比赛的球队之间进行。球队按球队编号分为比赛。比赛获胜者晋级下一轮胜者组,负者进入败者组。

败者组从输掉胜者组第一场比赛的 $$$2^{n-1}$$$ 队开始。每个败者组回合由两场比赛组成。在一轮 $$$2^k$$$ 的第一场比赛中,各队互相进行一场比赛(球队按球队编号分为几场比赛)。 $$$2^{k-1}$$$ 失败的球队将被淘汰出锦标赛,$$$2^{k-1}$$$ 获胜的球队将对阵在本轮胜者组中被淘汰的 $$$2^{k-1}$$$ 球队(同样,球队按照球队编号进行分组)。每轮比赛的结果是,胜者组和败者组都剩下 $$$2^{k-1}$$$ 队。请参阅示例注释以更好地理解。

胜者组剩下的一支球队与败者组剩下的一支球队在总决赛中进行比赛,以确定冠军得主。

您是编号为 $$$a_1、a_2、...、a_k$$$ 的球队的粉丝。您希望锦标赛与您最喜欢的球队进行尽可能多的比赛。幸运的是,您可以按照您想要的方式影响每场冠军赛的结果。包括您所粉丝的球队在内的冠军赛的最大可能场次是多少?

输入

第一输入行有两个整数 $$$n, k$$$ — $$$2^n$$$ 球队正在参加锦标赛。您是 $$$k$$$ 球队的粉丝 ($$$2 \le n \le 17; 0 \le k \le 2^n$$$)。

第二个输入行有 $$$k$$$ 不同的整数 $$$a_1, \ldots, a_k$$$ - 您所支持的球队数量 ($$$1 \le a_i \le 2^n$$$)。

输出

输出单个整数 - 包含您所喜爱的球队的冠军比赛的最大可能数量。

示例

输入 #1

3 1
6

输出 #1

6

输入 #2

3 3
1 7 8

输出 #2

11

输入 #3

3 4
1 3 5 7

输出 #3

14

注意

在图像上,锦标赛的每场比赛都用英文字母表示($$$a$$$ 到 $$$n$$$)。游戏$$$i$$$的获胜者表示为$$$Wi$$$,失败者表示为$$$Li$$$。您所关注的球队会以红色背景突出显示。

在第一个示例中,如果 $$$6$$$ 队输掉第一场胜者组比赛(比赛 $$$c$$$)并赢得所有胜者组比赛(比赛 $$$h, j, l, m$$$),则将参加 6 场比赛。

在第二个示例中,队伍 $$$7$$$ 和 $$$8$$$ 必须在胜者组的第一场比赛(比赛 $$$d$$$)中相互比赛。 $$$8$$$ 队可以赢得胜者组的所有剩余比赛,而 $$$1$$$ 和 $$$7$$$ 队将参加败者组比赛。

在第三个示例中,您最喜欢的球队可以参加锦标赛的所有比赛。