ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#8845
サブタスク

슬라이딩 윈도우 합계 1s 1024MB

問題

베시는 숨겨진 이진 문자열 b_1 b_2\cdots b_N (1 ≤ N ≤ 2×10^5)을 가지고 있다.

b에 대해 당신에게 주어지는 유일한 정보는 이진 문자열 r_1 r_2\cdots r_{N−K+1}(1 ≤ K ≤ N)인데, 여기서 r_i는 b에서 왼쪽 끝 인덱스가 i인 길이 K 구간(window) 안에 있는 1의 개수를 2로 나눈 나머지(즉, 짝수/홀수)이다.

베시의 숨겨진 이진 문자열에서 가능한 1의 개수의 최솟값과 최댓값을 출력하라.


入力

해결해야 할 독립적인 테스트 케이스가 T개 주어진다(1 ≤ T ≤ 10^3). 각 테스트는 다음과 같이 주어진다.

  • 첫 줄에 N과 K가 주어진다.

  • 둘째 줄에 이진 문자열 r_1…r_{N−K+1}이 주어진다. 여기서 ri=∑^{j+K−1}_{j=i}bj(mod2).이다.

모든 테스트 케이스를 합친 N의 총합은 10^6을 넘지 않는 것이 보장된다.


出力

각 테스트 케이스마다, 베시의 숨겨진 이진 문자열에서 가능한 1의 개수의 최솟값과 최댓값을 한 칸 띄워 출력하라.


部分問題

番号 点数 条件
#120点

N \le 8

#230点

K ≤ 8이고, 모든 테스트 케이스에 대한 N의 합이 10^4을 넘지 않음

#350点

추가 제약 조건 없음


例題 

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

첫 번째 테스트 케이스에서 K=1이면 r=b이므로, r에서 1의 개수는 3이다.

두 번째 테스트 케이스에서는 b가 될 수 있는 경우가 두 가지가 있다: 10001과 01110이며, 각각 1의 개수가 2개와 3개이다.


出典

USACO 2026 First Contest, Silver

ログインしないとコードを書けません。