codeforces-scrape

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

1295B.md (1848B)


      1 Source: https://codeforces.com/problemset/problem/1295/B
      2 
      3 B. Infinite Prefixes
      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 You are given string $s$ of length $n$ consisting of 0-s and 1-s. You build an infinite string $t$ as a concatenation of an infinite number of strings $s$, or $t = ssss \dots$ For example, if $s =$ 10010, then $t =$ 100101001010010...
     22 
     23 Calculate the number of prefixes of $t$ with balance equal to $x$. The balance of some string $q$ is equal to $cnt_{0, q} - cnt_{1, q}$, where $cnt_{0, q}$ is the number of occurrences of 0 in $q$, and $cnt_{1, q}$ is the number of occurrences of 1 in $q$. The number of such prefixes can be infinite; if it is so, you must say that.
     24 
     25 A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".
     26 
     27 Input
     28 
     29 The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.
     30 
     31 Next $2T$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $-10^9 \le x \le 10^9$) — the length of string $s$ and the desired balance, respectively.
     32 
     33 The second line contains the binary string $s$ ($|s| = n$, $s_i \in \{\text{0}, \text{1}\}$).
     34 
     35 It's guaranteed that the total sum of $n$ doesn't exceed $10^5$.
     36 
     37 Output
     38 
     39 Print $T$ integers — one per test case. For each test case print the number of prefixes or $-1$ if there is an infinite number of such prefixes.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 6 10
     48 010010
     49 5 3
     50 10101
     51 1 0
     52 0
     53 2 0
     54 01
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 3
     61 0
     62 1
     63 -1
     64 ```
     65 
     66 Note
     67 
     68 In the first test case, there are 3 good prefixes of $t$: with length $28$, $30$ and $32$.