Vũ Đạo Bò

Đ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

Đội nhảy gồm $N$ con bò ( $2 \leq N \leq 10^{6}$ ) đứng thành một hàng. Có hai loại bò: Guernsey (ký hiệu 0) và Holstein (ký hiệu 1). Mỗi bước nhảy, hai con bò cách nhau tối đa $K$ vị trí có thể hoán đổi chỗ.

Cho chuỗi nhị phân đầu tiên và cuối cùng của buổi nhảy (có cùng số ký tự '1'), tìm số bước nhảy tối thiểu để biến đổi chuỗi đầu thành chuỗi cuối.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $K$ ( $1 \leq K \leq N$ )
Dòng 2: Chuỗi nhị phân đầu tiên (độ dài $N$ )
Dòng 3: Chuỗi nhị phân cuối cùng (độ dài $N$ )

Dữ liệu ra

Một số nguyên -- số bước nhảy tối thiểu.

Ràng buộc

$2 \leq N \leq 10^{6}$
$1 \leq K \leq N$
Hai chuỗi có cùng số ký tự '1'
Test 4-5: $K = 1$
Test 6-7: Tối đa 8 ký tự '1'
Test 8-15: $N \leq 5000$

Ví dụ

Input	Output	Giải thích
4 1 0111 1110	3	0111 -> 1011 -> 1101 -> 1110. Mỗi bước hoán đổi hai vị trí liền kề.
5 2 11000 00011	3	11000 -> 01100 -> 00110 -> 00011. Mỗi bước hoán đổi hai vị trí cách nhau tối đa 2.
5 4 11000 00011	2	11000 -> 10010 -> 00011. Với $K = 4$ , có thể hoán đổi xa hơn.

Bình luận

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