codeforces-scrape

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

1884B.md (2496B)


      1 Source: https://codeforces.com/problemset/problem/1884/B
      2 
      3 B. Haunted House
      4 
      5 time limit per test
      6 
      7 1 second
      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 You are given a number in binary representation consisting of exactly $n$ bits, possibly, with leading zeroes. For example, for $n = 5$ the number $6$ will be given as $00110$, and for $n = 4$ the number $9$ will be given as $1001$.
     22 
     23 Let's fix some integer $i$ such that $1 \le i \le n$. In one operation you can swap any two adjacent bits in the binary representation. Your goal is to find the smallest number of operations you are required to perform to make the number divisible by $2^i$, or say that it is impossible.
     24 
     25 Please note that for each $1 \le i \le n$ you are solving the problem independently.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the binary representation of the number.
     32 
     33 The second line of each test case contains a string of length $n$, consisting of $0$ and $1$, — the binary representation of the number.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, for each $1 \le i \le n$ output the smallest number of operations required to make the number divisible by $2^i$, or output $-1$ if it is impossible.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 6
     47 
     48 1
     49 
     50 1
     51 
     52 2
     53 
     54 01
     55 
     56 3
     57 
     58 010
     59 
     60 5
     61 
     62 10101
     63 
     64 7
     65 
     66 0000111
     67 
     68 12
     69 
     70 001011000110
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 -1 
     77 1 -1 
     78 0 1 -1 
     79 1 3 -1 -1 -1 
     80 3 6 9 12 -1 -1 -1 
     81 0 2 4 6 10 15 20 -1 -1 -1 -1 -1
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, we cannot swap any elements, and the number $1$ is not divisible by $2$.
     87 
     88 In the second test case, the initial number is $1$. It is not divisible by $2$, but if we perform the operation, then we obtain the number with binary representation $10$, which is equal to $2$ in decimal representation, thus, it is divisible by $2$. But this number is not divisible by $4$ and we cannot obtain any other number using the operations.
     89 
     90 In the third test case, the initial number is $2$. For $i = 1$ we do not have to perform any operations since the initial number is divisible by $2$. For $i = 2$ we can perform one operation swapping the first two bits (we would obtain $100$ in binary representation, which corresponds to number $4$). There is no answer for $i = 3$.