Tổng Cửa Sổ Trượt

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có chuỗi nhị phân ẩn $b_{1} b_{2} \dots b_{N}$ . Bạn được cho chuỗi nhị phân $r_{1} r_{2} \dots r_{N - K + 1}$ , trong đó $r_{i}$ biểu thị tính chẵn lẻ của số bit $1$ trong cửa sổ độ dài $K$ bắt đầu từ vị trí $i$ (tức $r_{i} = (b_{i} + b_{i + 1} + \dots + b_{i + K - 1}) mod 2$ ).

Tìm số lượng bit $1$ nhỏ nhất và lớn nhất có thể trong chuỗi ẩn $b$ .

Dữ liệu vào

Dòng 1: Số nguyên $T$ — số test case
Mỗi test case:
- Dòng 1: Hai số nguyên $N$ và $K$
- Dòng 2: Chuỗi nhị phân $r$ độ dài $N - K + 1$

Dữ liệu ra

Với mỗi test case, in hai số nguyên trên một dòng: số bit $1$ nhỏ nhất và lớn nhất.

Ràng buộc

$1 \leq T \leq 10^{3}$
$1 \leq K \leq N \leq 2 \times 10^{5}$
Tổng $N$ qua tất cả test case $\leq 10^{6}$

Ví dụ

Input	Output	Giải thích
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	Khi $K = 1$ : $r = b$ nên số bit 1 xác định. Khi $K = 5$ : chỉ biết tính chẵn lẻ tổng.

Bình luận

Không có bình luận tại thời điểm này.