Alice 拥有一座迷宫,这座迷宫可以抽象成一棵拥有 2^n 个叶节点的满二叉树,总节点数目为 (2^{n+1} - 1),依次编号为 1 \sim (2^{n+1} - 1)。其中编号为 2^n \sim (2^{n+1} - 1) 的是叶节点,编号为 1 \sim (2^n - 1) 的是非叶节点,且非叶节点 1 \le u \le (2^n - 1) 的左儿子编号为 2u,右儿子编号为 (2u + 1)。
每个非叶节点都有一个石像守卫,初始时,所有石像守卫均在沉睡。唤醒 u 点的石像守卫需要 w_u 的魔力值。
每个叶节点都有一个符文,v 点的符文记作 $qv。**保证 q{2^n}, q{2^n+1},\cdots, q{2^{n+1}-1} 构成 1 \sim 2^n$ 的排列**。
探险者初始时持有空序列 Q,从节点 1 出发,按照如下规则行动:
- 到达叶节点 v 时,将 v 点的符文 q_v 添加到序列 Q 的末尾,然后返回父节点。
- 到达非叶节点 u 时:
- 若该点的石像守卫已被唤醒,则只能先前往左儿子,(从左儿子返回后)再前往右儿子,(从右儿子返回后)最后返回父节点。
- 若该点的石像守卫在沉睡,可以在以下二者中任选其一:
- 先前往左儿子,再前往右儿子,最后返回父节点。
- 先前往右儿子,再前往左儿子,最后返回父节点。
返回节点 1 时,探险结束。可以证明,探险者一定访问每个叶节点各一次,故此时 Q 的长度为 2^n。
探险者 Bob 准备进入迷宫,他希望探险结束时的 Q 的字典序越小越好,与之相对,Alice 希望 Q 的字典序越大越好。
在 Bob 出发之前,Alice 可以选择一些魔力值花费之和不超过 K 的石像守卫,并唤醒它们。Bob 出发时,他能够知道 Alice 唤醒了哪些神像。若双方都采取最优策略,求序列 Q 的最终取值。
对于两个长度为 2^n 的序列 Q_1,Q_2,称 Q_1 字典序小于 Q_2 当且仅当以下条件成立:
- \exist i \in [1, 2^n] 满足以下两个条件:
- $\forall 1 \le j < i,Q{1,j} = Q{2,j}$;
- $Q{1,i} < Q{2,i}$。