CRAN04  Audition
Penny is a terrible waitress and even worse actress, however recently she applied for a role in an upcoming TV series. Even though she thought she had no chance, she was called for an audition. She was very happy about it until she found out that her character in this new series will be a studious, high IQ girl named Megan. Producer told her that to get the role of Megan she had to prove that her mind can handle a bit of mathematics and reasoning. If she passed the test then she will be given the role of Megan. The test was as follow.
The people (Boys and Girls) who came for audition are standing in a line in a random order. Producer has to select exactly K boys for the show. So he asks Penny to tell how many ways can he select two numbers i and j such that the number of boys standing between these (including I and j) indexes is exactly K.
Penny desperately needs this role. Everybody knows that Penny is not a very smart and requests you to help her.
Input
First line contains T – The number of test cases.
Next line contains space separated N and K.
N – The total number of boys and girls who came to audition.
K – The number of the boys who must be there between each (i, j) pair.
Next line contains a nonempty string consisting of '1' and '0'.
1 represents Boy.
0 represents Girl.
Output
The number of (i, j) pairs such that the number of boys between index i and j, both inclusive is equal to K.
Constraints
1<=T<=10
1<=N<=10^6
0<=K<=10^6
Example
Input:3
4 1
0101
5 2
01010
5 4
01010
Output: 6
4
0
hide comments
Hugo Godoy:
20171113 06:39:27
May I assume that the string has length N? 

pradeep_yadav:
20170902 09:47:16
did using binary search O(nlogn) solution.


hacker_sk:
20170627 08:55:00
3rd rank with O(n) soln. :) 

aman224:
20170317 08:41:59
O(N) solution without binary search is possible...


ricky99999:
20170201 12:36:29
O(n) Solution>Use same logic as in SUBSEQ & CRAN02. 

Chinmay Kousik:
20161126 14:17:09
Someone please tell me what's wrong with the source code. I keep getting WA. O(n) soln. submission id: 18262942 

rahulpadhy:
20161015 12:17:08
Last edit: 20161015 12:23:26 

geoffreymace7:
20160718 18:26:55
Number of pairs can exceed 10^9, lead me to several WAs. Last edit: 20160718 18:27:54 

aspro:
20160518 12:54:56
input the string carefully...got TLE bcuz of that


SUBHAM SANGHAI:
20160516 17:17:20
nice Binary Search questn . Beware of the case when k=0 Last edit: 20160516 17:27:34 
Added by:  CSI 
Date:  20130216 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 