All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is a well-known chef, and everyone wishes to taste his dishes.
As you might know, cooking is not an easy job at all and cooking everyday makes the chef very tired. So, Chef has decided to give himself some days off.
Chef has made a schedule for the next N days: On i-th day if Ai is equal to 1 then Chef is going to cook a delicious dish on that day, if Ai is equal to 0 then Chef is going to rest on that day.
After Chef made his schedule he discovered that it's not the best schedule, because there are some big blocks of consecutive days where Chef will cook which means it's still tiring for Chef, and some big blocks of consecutive days where Chef is going to rest which means chef will be bored doing nothing during these days.
Which is why Chef has decided to make changes to this schedule, but since he doesn't want to change it a lot, he will flip the status of at most K days. So for each day which Chef chooses, he will make it 1 if it was 0 or he will make it 0 if it was 1.
Help Chef by writing a program which flips the status of at most K days so that the size of the maximum consecutive block of days of the same status is minimized.
The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two integers: N denoting the number of days and K denoting maximum number of days to change.
The second line contains a string of length N , of which the i-th character is 0 if chef is going to rest on that day, or 1 if chef is going to work on that day
For each test case, output a single line containing a single integer, which is the minimum possible size of maximum block of consecutive days of the same status achievable.
- 1 ≤ T ≤ 11,000
- 1 ≤ N ≤ 106
- The sum of N in all test-cases won't exceed 106.
- 0 ≤ K ≤ 106
- 0 ≤ Ai ≤ 1
- Subtask #1 (20 points): N ≤ 10
- Subtask #2 (80 points): Original Constraints
Input: 2 9 2 110001111 4 1 1001 Output: 2 2
Example case 1: The answer is 2 because we can change the string to: 110101011
Example case 2: If we don't change the input string at all, the answer will be 2. It is the best value we can achieve under the given conditions.
|Tags||binary-search, easy, kingofnumbers, march17|
|Time Limit:||1 - 2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.