Xâu nhị phân (DHBB 2021)

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho xâu \(S\) gồm \(n\) ký tự \(\in \{0,1\}\) và số tự nhiên \(k\). Hãy tìm cách đảo một số ít nhất các ký tự của
chuỗi \(S\) (đảo ký tự 0 thành ký tự 1 hoặc ngược lại) sao cho chuỗi kết quả có thể được phân tách
thành không quá \(k\) chuỗi con mà mỗi chuỗi con chỉ chứa các ký tự 0 hoặc chỉ chứa các ký tự 1.
Yêu cầu: Cho biết số ký tự ít nhất trong xâu \(S\) cần đảo.

Input

Vào từ file văn bản BITSTR.INP

  • Dòng 1 chứa hai số nguyên dương \(n, k \le 2\times 10^5\) cách nhau bởi dấu cách

  • Dòng 2 ghi xâu \(S\) (gồm \(n\) ký tự \(\in \{0,1\}\) viết liền nhau)

Output

  • Ghi ra file văn bản BITSTR.OUT một số nguyên duy nhất là số ký tự ít nhất trong xâu \(S\)
    cần đảo.

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\)
  • Subtask \(2\) (\(20\%\) số điểm): \(n, k \le 400\)
  • Subtask \(3\) (\(20\%\) số điểm): \(n \le 2\times 10^5 ; k \le 400\)
  • Subtask \(4\) (\(20\%\) số điểm): \(n \le 2\times 10^5 ; k \le 5000\)

  • Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc bổ sung ngoài các ràng buộc đã nêu trong đề bài.

Example

Test 1

Input
10 1
1000100011
Output
4
Note

Biến đổi thành xâu gồm toàn ký tự 0
0000000000

Test 2

Input
6 2
010110
Output
2
Note

Biến đổi thành:
000111 hoặc
111110 hoặc
011111


Bình luận

Không có bình luận nào.