Bessie has a hidden binary string \(b_1b_2\dots b_N\) (\(1\le N\le 2\cdot 10^5\)).
The only information about \(b\) you are given is a binary string
\(r_1r_2\dots r_{N-K+1}\) (\(1 \le K \le N\)), where \(r_i\) is the remainder when
the number of ones in the length-\(K\) window of \(b\) with leftmost index \(i\) is
divided by two.

Output the minimum and maximum possible numbers of ones in Bessie's hidden
binary string.

Problem credits: Benjamin Qi

SCORING

• Input 2: \(N\le 8\)
• Inputs 3-4: \(K\le 8\) and the sum of \(N\) over all tests does not exceed \(10^4\).
• Inputs 5-11: No additional constraints.

Problem credits: Benjamin Qi

There are \(T\) (\(1\le T\le 10^3\)) independent test cases to be solved. Each test
is specified by the following:

The first line contains \(N\) and \(K\).

The second line contains the binary string \(r_1\dots r_{N-K+1}\), where
\(r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}\).

It is guaranteed that the sum of \(N\) over all tests does not exceed \(10^6\).

For each test case, output the minimum and maximum possible numbers of ones in
Bessie's hidden binary string, separated by a single space.

riseoj 작성

출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver