SPOTIT - Spot the largest string
Rat Ronnie is very intelligent. Recently she got interested in the binary number system. Seeing this Rat Rocky decided to give her a problem to solve. If she solves it then she gets a big piece of cheese as a prize :).
A binary string of length N is a string that contains N characters. Each of these characters is either 0 or 1. Given a binary string S of length N and another input integer L, find a substring of length exactly L whose decimal value is largest amongst all substrings of length L in S. Print this largest value. (See notes and examples for further clarification)
Now Rat Ronnie is unable to think of anything else but cheese. As you are a brilliant programmer, she wants you to solve the problem. She promises to share the piece of cheese if you succeed.
Notes
- A substring of a string S, is any contiguous sequence of characters in the string. For example, "cde" is a substring of "abcdef" but "ce" is not a substring of "abcdef".
- A value of a binary substring is the value after converting it to a decimal number. For example- Decimal value of "1101" = (2^0)*1 + (2^1)*0 + (2^2)*1 + (2^3)*1 = 13
Input
The first line is T, the number of test cases.
T test case follows. The first line of every test case contains two integers N and L. The second line of every test case contains a binary string of length N.
1<=T<=100
1<=N<=100
1<=L<=50
N>=L
Output
Output the maximum decimal value of the substring of length L. As the output may be large, use an appropriate data type.
Example
Input:
3
7 3
0110111
5 3
10110
4 4
1000
Output:
7
6
8
Explanation of Example
In the second test case, possible substrings of length 3 are "101" , "011", "110" . Out of these, "110" has the highest value in decimal, i.e, 6.
| Added by: | Ishani Parekh |
| Date: | 2011-09-22 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own |
RSS