레이팅 미적용베시는 숨겨진 이진 문자열 \(b_1b_2\dots b_N\) (\(1\le N\le 2\cdot 10^5\))을 가지고 있다. \(b\)에 대해 주어지는 유일한 정보는 이진 문자열 \(r_1r_2\dots r_{N-K+1}\) (\(1 \le K \le N\))이며, 여기서 \(r_i\)는 가장 왼쪽 인덱스가 \(i\)인 \(b\)의 길이 \(K\) 윈도우 안에 있는 1의 개수를 2로 나눈 나머지이다.
베시의 숨겨진 이진 문자열에 있을 수 있는 1의 개수의 최솟값과 최댓값을 출력하라.
Problem credits: Benjamin Qi
SCORING
- 입력 2: \(N\le 8\)
- 입력 3-4: \(K\le 8\)이고 모든 테스트에 걸친 \(N\)의 합이 \(10^4\)를 넘지 않는다.
- 입력 5-11: 추가 제약 없음.
Problem credits: Benjamin Qi
풀어야 할 독립적인 테스트 케이스가 \(T\) (\(1\le T\le 10^3\))개 있다. 각 테스트는 다음과 같이 주어진다.
첫째 줄에 \(N\)과 \(K\)가 주어진다.
둘째 줄에 이진 문자열 \(r_1\dots r_{N-K+1}\)이 주어지며, 여기서 \(r_i=\sum_{j=i}^{j+K-1}b_j\pmod{2}\)이다.
모든 테스트에 걸친 \(N\)의 합이 \(10^6\)을 넘지 않음이 보장된다.
각 테스트 케이스에 대해, 베시의 숨겨진 이진 문자열에 있을 수 있는 1의 개수의 최솟값과 최댓값을 공백 하나로 구분하여 출력한다.
7
5 1
10011
5 2
1001
5 3
100
5 5
0
5 5
1
4 4
1
5 2
00003 3
2 3
1 4
0 4
1 5
1 3
0 5For the first test case, \(K=1\) means that \(r=b\), and the number of ones in \(r\)
is \(3\).
For the second test case, there are two possibilities for \(b\): 10001 and 01110,
having \(2\) and \(3\) ones, respectively.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > First Contest > Silver