4250. Low Complexity Tree

单点时限: 1.0 sec

内存限制: 512 MB

机房中有一棵高度为 $h$ 的满二叉树(包含 $2^h$ 个叶结点),传说是某 i 姓同学被吊打过的地方。

在这棵树上,我们将所有叶子结点从左往右依次编号为 $1,\ldots,2^h$。

其中有 $m$ 个叶子结点称为 关键结点,它们的编号依次为 $t_1,\ldots,t_m$。

这棵树上的每个 非叶结点 上有一个开关,开关有左右两种状态。

接下来执行如下的投球过程:一个球从根结点出发,每次走到当前结点开关指向的那个儿子处,直到走到叶结点,此时该球将会计入该叶结点的 球数 中,然后,这个球经过的所有结点的开关状态将 取反(左变右,右变左)。

你可以设置每个开关最初的位置,然后连续投下 $n$ 个球,你需要使得最终所有关键结点的 球数之和 最大,只需要输出这个最大值。

输入格式

第一行:三个整数 $h,m,n$,分别表示二叉树的深度,关键结点的数量以及投球数。

第二行:$m$ 个整数 $t_{1\ldots m}$,表示关键结点的编号。

输出格式

输出一行一个整数,表示所有关键结点的球数之和的最大值。

样例

Input
2 3 3
1 2 3
Output
3

提示

本题采用捆绑测试。

对于 $100\%$ 的数据:$1\leq h\leq 60,\ \ 1\leq m\leq \min(2^h,10^5),\ \ 1\leq n\leq 10^{18},\ \ 1\leq t_i\leq 2^h$ 且 $t_i$ 两两不等。

$\text{Subtask 1}$:$h\leq 4,\ \ n\leq 100$,分值 $10$。

$\text{Subtask 2}$:$h\leq 10,\ \ n\leq 10^5$,分值 $20$。

$\text{Subtask 3}$:$h\leq 20$,分值 $10$。

$\text{Subtask 4}$:$h\leq 60,\ \ m=1$,分值 $10$。

$\text{Subtask 5}$:$h\leq 60,\ \ m\leq 20$,分值 $20$。

$\text{Subtask 6}$:$h\leq 60$,分值 $30$。

21 人解决,102 人已尝试。

35 份提交通过,共有 884 份提交。

7.5 EMB 奖励。

创建: 6 月,1 周前.

修改: 6 月,1 周前.

最后提交: 3 月,3 周前.

来源: N/A

题目标签