2095: [USACO 2026 First Contest, Silver] Problem 3. Sliding Window Summation
文件提交：无需freopen
内存限制：256 MB
时间限制：2.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
Bessie has a hidden binary string (). The only information about you are given is a binary string (), where is the remainder when the number of ones in the length- window of with leftmost index is divided by two.
Output the minimum and maximum possible numbers of ones in Bessie's hidden binary string.
输入
There are () independent test cases to be solved. Each test is specified by the following:
The first line contains and .
The second line contains the binary string , where
It is guaranteed that the sum of over all tests does not exceed .
输出
For each test case, output the minimum and maximum possible numbers of ones in Bessie's hidden binary string, separated by a single space.
样例输入
7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
0000样例输出
3 3
2 3
1 4
0 4
1 5
1 3
0 5提示
For the first test case, means that , and the number of ones in is .
For the second test case, there are two possibilities for : 10001 and 01110, having and ones, respectively.
SCORING:
- Input 2:
- Inputs 3-4: and the sum of over all tests does not exceed .
- Inputs 5-11: No additional constraints.