codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```