codeforces-scrape

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

1217C.md (1357B)


      1 Source: https://codeforces.com/problemset/problem/1217/C
      2 
      3 C. The Number Of Good Substrings
      4 
      5 time limit per test
      6 
      7 4 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 a binary string $s$ (recall that a string is binary if each character is either $0$ or $1$).
     22 
     23 Let $f(t)$ be the decimal representation of integer $t$ written in binary form (possibly with leading zeroes). For example $f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$ and $f(000100) = 4$.
     24 
     25 The substring $s_{l}, s_{l+1}, \dots , s_{r}$ is good if $r - l + 1 = f(s_l \dots s_r)$.
     26 
     27 For example string $s = 1011$ has $5$ good substrings: $s_1 \dots s_1 = 1$, $s_3 \dots s_3 = 1$, $s_4 \dots s_4 = 1$, $s_1 \dots s_2 = 10$ and $s_2 \dots s_4 = 011$.
     28 
     29 Your task is to calculate the number of good substrings of string $s$.
     30 
     31 You have to answer $t$ independent queries.
     32 
     33 Input
     34 
     35 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.
     36 
     37 The only line of each query contains string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of only digits $0$ and $1$.
     38 
     39 It is guaranteed that $\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each query print one integer — the number of good substrings of string $s$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 0110
     52 0101
     53 00001000
     54 0001000
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 4
     61 3
     62 4
     63 3
     64 ```