309981: CF1767D. Playoff
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Playoff
题意翻译
有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下： 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。 我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。 给定一个长度为 $n$ 的 01 串 $s$，含义如下： 1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。 2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。 你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。题目描述
$ 2^n $ teams participate in a playoff tournament. The tournament consists of $ 2^n - 1 $ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $ 1 $ plays against team $ 2 $ , team $ 3 $ plays against team $ 4 $ , and so on (so, $ 2^{n-1} $ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $ 2^{n-1} $ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $ 2^{n-2} $ games are played: in the first one of them, the winner of the game " $ 1 $ vs $ 2 $ " plays against the winner of the game " $ 3 $ vs $ 4 $ ", then the winner of the game " $ 5 $ vs $ 6 $ " plays against the winner of the game " $ 7 $ vs $ 8 $ ", and so on. This process repeats until only one team remains. The skill level of the $ i $ -th team is $ p_i $ , where $ p $ is a permutation of integers $ 1 $ , $ 2 $ , ..., $ 2^n $ (a permutation is an array where each element from $ 1 $ to $ 2^n $ occurs exactly once). You are given a string $ s $ which consists of $ n $ characters. These characters denote the results of games in each phase of the tournament as follows: - if $ s_i $ is equal to 0, then during the $ i $ -th phase (the phase with $ 2^{n-i} $ games), in each match, the team with the lower skill level wins; - if $ s_i $ is equal to 1, then during the $ i $ -th phase (the phase with $ 2^{n-i} $ games), in each match, the team with the higher skill level wins. Let's say that an integer $ x $ is winning if it is possible to find a permutation $ p $ such that the team with skill $ x $ wins the tournament. Find all winning integers.输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 1 \le n \le 18 $ ). The second line contains the string $ s $ of length $ n $ consisting of the characters 0 and/or 1.
输出格式
Print all the winning integers $ x $ in ascending order.
输入输出样例
输入样例 #1
3
101输出样例 #1
4 5 6 7输入样例 #2
1
1输出样例 #2
2输入样例 #3
2
01输出样例 #3
2 3Input
题意翻译
有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下： 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。 我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。 给定一个长度为 $n$ 的 01 串 $s$，含义如下： 1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。 2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。 你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。Output
**标题：季后赛**
**题意翻译：**
有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下：
- 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。
- 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。
- 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。
我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。
给定一个长度为 $n$ 的 01 串 $s$，含义如下：
1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。
2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。
你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。
**题目描述：**
$2^n$ teams participate in a playoff tournament. The tournament consists of $2^n - 1$ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$, and so on (so, $2^{n-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{n-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $2^{n-2}$ games are played: in the first one of them, the winner of the game "1 vs 2" plays against the winner of the game "3 vs 4", then the winner of the game "5 vs 6" plays against the winner of the game "7 vs 8", and so on. This process repeats until only one team remains.
The skill level of the $i$-th team is $p_i$, where $p$ is a permutation of integers $1$, $2$, ..., $2^n$ (a permutation is an array where each element from $1$ to $2^n$ occurs exactly once).
You are given a string $s$ which consists of $n$ characters. These characters denote the results of games in each phase of the tournament as follows:
- if $s_i$ is equal to 0, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the lower skill level wins;
- if $s_i$ is equal to 1, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the higher skill level wins.
Let's say that an integer $x$ is winning if it is possible to find a permutation $p$ such that the team with skill $x$ wins the tournament. Find all winning integers.
**输入输出格式：**
**输入格式：**
- 第一行包含一个整数 $n$（$1 \le n \le 18$）。
- 第二行包含一个由字符 0 和/或 1 组成的长度为 $n$ 的字符串 $s$。
**输出格式：**
- 按升序打印所有获胜整数 $x$。
**输入输出样例：**
**输入样例 #1：**
```
3
101
```
**输出样例 #1：**
```
4 5 6 7
```
**输入样例 #2：**
```
1
1
```
**输出样例 #2：**
```
2
```
**输入样例 #3：**
```
2
01
```
**输出样例 #3：**
```
2 3
```**标题：季后赛** **题意翻译：** 有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下： - 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。 - 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。 - 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。 我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。 给定一个长度为 $n$ 的 01 串 $s$，含义如下： 1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。 2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。 你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。 **题目描述：** $2^n$ teams participate in a playoff tournament. The tournament consists of $2^n - 1$ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$, and so on (so, $2^{n-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{n-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $2^{n-2}$ games are played: in the first one of them, the winner of the game "1 vs 2" plays against the winner of the game "3 vs 4", then the winner of the game "5 vs 6" plays against the winner of the game "7 vs 8", and so on. This process repeats until only one team remains. The skill level of the $i$-th team is $p_i$, where $p$ is a permutation of integers $1$, $2$, ..., $2^n$ (a permutation is an array where each element from $1$ to $2^n$ occurs exactly once). You are given a string $s$ which consists of $n$ characters. These characters denote the results of games in each phase of the tournament as follows: - if $s_i$ is equal to 0, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the lower skill level wins; - if $s_i$ is equal to 1, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the higher skill level wins. Let's say that an integer $x$ is winning if it is possible to find a permutation $p$ such that the team with skill $x$ wins the tournament. Find all winning integers. **输入输出格式：** **输入格式：** - 第一行包含一个整数 $n$（$1 \le n \le 18$）。 - 第二行包含一个由字符 0 和/或 1 组成的长度为 $n$ 的字符串 $s$。 **输出格式：** - 按升序打印所有获胜整数 $x$。 **输入输出样例：** **输入样例 #1：** ``` 3 101 ``` **输出样例 #1：** ``` 4 5 6 7 ``` **输入样例 #2：** ``` 1 1 ``` **输出样例 #2：** ``` 2 ``` **输入样例 #3：** ``` 2 01 ``` **输出样例 #3：** ``` 2 3 ```
**题意翻译：**
有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下：
- 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。
- 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。
- 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。
我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。
给定一个长度为 $n$ 的 01 串 $s$，含义如下：
1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。
2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。
你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。
**题目描述：**
$2^n$ teams participate in a playoff tournament. The tournament consists of $2^n - 1$ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$, and so on (so, $2^{n-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{n-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $2^{n-2}$ games are played: in the first one of them, the winner of the game "1 vs 2" plays against the winner of the game "3 vs 4", then the winner of the game "5 vs 6" plays against the winner of the game "7 vs 8", and so on. This process repeats until only one team remains.
The skill level of the $i$-th team is $p_i$, where $p$ is a permutation of integers $1$, $2$, ..., $2^n$ (a permutation is an array where each element from $1$ to $2^n$ occurs exactly once).
You are given a string $s$ which consists of $n$ characters. These characters denote the results of games in each phase of the tournament as follows:
- if $s_i$ is equal to 0, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the lower skill level wins;
- if $s_i$ is equal to 1, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the higher skill level wins.
Let's say that an integer $x$ is winning if it is possible to find a permutation $p$ such that the team with skill $x$ wins the tournament. Find all winning integers.
**输入输出格式：**
**输入格式：**
- 第一行包含一个整数 $n$（$1 \le n \le 18$）。
- 第二行包含一个由字符 0 和/或 1 组成的长度为 $n$ 的字符串 $s$。
**输出格式：**
- 按升序打印所有获胜整数 $x$。
**输入输出样例：**
**输入样例 #1：**
```
3
101
```
**输出样例 #1：**
```
4 5 6 7
```
**输入样例 #2：**
```
1
1
```
**输出样例 #2：**
```
2
```
**输入样例 #3：**
```
2
01
```
**输出样例 #3：**
```
2 3
```**标题：季后赛** **题意翻译：** 有 $2^n$ 个队伍要通过 $n$ 轮比赛决出胜负，总共有 $2^n-1$ 次两两对决。规则如下： - 在第 $1$ 轮比赛中，第 $1$ 队和第 $2$ 队对决，第 $3$ 队和第 $4$ 队对决，以此类推，第 $2^n-1$ 队和第 $2^n$ 队对决。每场对决没有平局，输的队伍就直接淘汰。所以这轮比赛后只剩下 $2^{n-1}$ 个队伍。 - 在第 $2$ 轮比赛中，我们将第 $1$ 轮剩下的队伍编号为 $1,2,\dots ,2^{n-1}$，继续像第 $1$ 轮那样两两对决。所以这轮比赛后只剩下 $2^{n-2}$ 个队伍。 - 以此类推，直到第 $n$ 轮比赛，只剩下 $1$ 个队伍，比赛结束。 我们设第 $i$ 个队伍的技巧值为 $p_i$，其中 $p$ 是一个 $1\sim 2^n$ 的排列。 给定一个长度为 $n$ 的 01 串 $s$，含义如下： 1. 若 $s_i=0$，则在第 $i$ 轮比赛中，技巧值低的队伍获胜。 2. 若 $s_i=1$，则在第 $i$ 轮比赛中，技巧值高的队伍获胜。 你要找到所有的整数 $x\in[1,2^n]$，使得存在一个排列 $p$，让技巧值为 $x$ 的队伍获胜。 **题目描述：** $2^n$ teams participate in a playoff tournament. The tournament consists of $2^n - 1$ games. They are held as follows: in the first phase of the tournament, the teams are split into pairs: team $1$ plays against team $2$, team $3$ plays against team $4$, and so on (so, $2^{n-1}$ games are played in that phase). When a team loses a game, it is eliminated, and each game results in elimination of one team (there are no ties). After that, only $2^{n-1}$ teams remain. If only one team remains, it is declared the champion; otherwise, the second phase begins, where $2^{n-2}$ games are played: in the first one of them, the winner of the game "1 vs 2" plays against the winner of the game "3 vs 4", then the winner of the game "5 vs 6" plays against the winner of the game "7 vs 8", and so on. This process repeats until only one team remains. The skill level of the $i$-th team is $p_i$, where $p$ is a permutation of integers $1$, $2$, ..., $2^n$ (a permutation is an array where each element from $1$ to $2^n$ occurs exactly once). You are given a string $s$ which consists of $n$ characters. These characters denote the results of games in each phase of the tournament as follows: - if $s_i$ is equal to 0, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the lower skill level wins; - if $s_i$ is equal to 1, then during the $i$-th phase (the phase with $2^{n-i}$ games), in each match, the team with the higher skill level wins. Let's say that an integer $x$ is winning if it is possible to find a permutation $p$ such that the team with skill $x$ wins the tournament. Find all winning integers. **输入输出格式：** **输入格式：** - 第一行包含一个整数 $n$（$1 \le n \le 18$）。 - 第二行包含一个由字符 0 和/或 1 组成的长度为 $n$ 的字符串 $s$。 **输出格式：** - 按升序打印所有获胜整数 $x$。 **输入输出样例：** **输入样例 #1：** ``` 3 101 ``` **输出样例 #1：** ``` 4 5 6 7 ``` **输入样例 #2：** ``` 1 1 ``` **输出样例 #2：** ``` 2 ``` **输入样例 #3：** ``` 2 01 ``` **输出样例 #3：** ``` 2 3 ```