1767D.md (2218B)
1 Source: https://codeforces.com/problemset/problem/1767/D 2 3 D. Playoff 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 $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. 22 23 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). 24 25 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: 26 27 * 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; 28 * 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. 29 30 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. 31 32 Input 33 34 The first line contains one integer $n$ ($1 \le n \le 18$). 35 36 The second line contains the string $s$ of length $n$ consisting of the characters 0 and/or 1. 37 38 Output 39 40 Print all the winning integers $x$ in ascending order. 41 42 Examples 43 44 Input 45 46 ``` 47 3 48 101 49 ``` 50 51 Output 52 53 ``` 54 4 5 6 7 55 ``` 56 57 Input 58 59 ``` 60 1 61 1 62 ``` 63 64 Output 65 66 ``` 67 2 68 ``` 69 70 Input 71 72 ``` 73 2 74 01 75 ``` 76 77 Output 78 79 ``` 80 2 3 81 ```