← 返回题目列表

Codeforces · 1767/D

D. 季后赛

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

$$$2^n$$$ 队参加季后赛。锦标赛由 $$$2^n - 1$$$ 场比赛组成。它们的举行方式如下:在锦标赛的第一阶段,球队被分成两对:球队$$$1$$$对阵球队$$$2$$$,球队$$$3$$$对阵球队$$$4$$$,依此类推(因此,$$$2^{n-1}$$$比赛在该阶段进行)。当一支球队输掉一场比赛时,该球队就会被淘汰,每场比赛都会导致一支球队被淘汰(没有平局)。之后,只剩下 $$$2^{n-1}$$$ 队。如果只剩下一支球队,则宣布该球队为冠军;否则,第二阶段开始,进行 $$$2^{n-2}$$$ 游戏:在第一阶段中,游戏获胜者 "$$$1$$$ vs $$$2$$$" 与游戏获胜者 "$$$3$$$ vs $$$4$$$" 进行比赛,然后游戏获胜者 "$$$5$$$ vs $$$6$$$" 与游戏获胜者 "$$$7$$$ 进行比赛vs $$$8$$$",等等。重复此过程,直到只剩下一个团队。

第 $$$i$$$ 团队的技能水平为 $$$p_i$$$,其中 $$$p$$$ 是整数 $$$1$$$、$$$2$$$、...、$$$2^n$$$ 的排列(排列是一个数组,其中从 $$$1$$$ 到 $$$2^n$$$ 的每个元素恰好出现一次)。

给定一个字符串 $$$s$$$,它由 $$$n$$$ 个字符组成。这些字符表示锦标赛每个阶段的比赛结果,如下所示:

- 如果$$$s_i$$$等于0,则在第$$$i$$$阶段(有$$$2^{n-i}$$$比赛的阶段),每场比赛中技术水平较低的球队获胜;
- 如果$$$s_i$$$等于1,则在第$$$i$$$阶段(有$$$2^{n-i}$$$比赛的阶段),在每场比赛中,技术水平较高的球队获胜。

假设整数 $$$x$$$ 获胜,如果可以找到排列 $$$p$$$ 使得具有技能 $$$x$$$ 的团队赢得比赛。找出所有获胜的整数。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 18$$$)。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,由字符 0 和/或 1 组成。

输出

按升序打印所有获胜整数 $$$x$$$。

示例

输入 #1

3
101

输出 #1

4 5 6 7

输入 #2

1
1

输出 #2

2

输入 #3

2
01

输出 #3

2 3