An có một xâu nhị phân \(s\) độ dài \(n\). Trước khi bắt đầu chơi với nó, anh ấy muốn đảm bảo rằng xâu đó không chứa quá \(k\) bít liên tiếp giống nhau. Để đạt được điều đó, loại thao tác duy nhất anh ta được phép thực hiện là lật bất kỳ bít nào của xâu (bít \(0\) lật thành \(1\) và bít \(1\) lật thành \(0\)).
Tìm số thao tác tối thiểu mà An cần. Ngoài ra, đưa ra một trong các xâu có được sau khi sửa đổi.
Input
Vào từ tệp văn bản bina.inp:
- Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \le k \le n \le 10^5)\);
- Dòng thứ hai chứa xâu nhị phân \(s\) độ dài \(n\).
Output
Ghi ra tệp văn bản bina.out:
- Dòng đầu tiên in ra một số nguyên là số thao tác tối thiểu mà An cần;
- Dòng thứ hai in ra một trong các xâu có được sau khi sửa đổi.
Example
Test 1
Input
2 1
11Output
1
01Note
Trong ví dụ đầu tiên, bít \(1\) xuất hiện hai lần liên tiếp nên có thể sửa đổi xâu \(11\) thành \(10\) bằng một thao tác lật bít thứ hai. Có thể đưa ra xâu sửa đổi là \(01\) bằng một thao tác lật bít thứ nhất.
Trong ví dụ thứ hai, không cần sửa đổi xâu vì xâu không có nhiều hơn \(2\) bít liên tiếp giống nhau.
Trong ví dụ thứ ba, bít \(0\) xuất hiện hai lần liên tiếp nên có thể sửa đổi xâu \(1001\) thành \(1010\) bằng hai thao tác lật bít thứ ba và thứ tư.
Test 2
Input
2 2
11Output
0
11Test 3
Input
4 1
1001Output
2
1010Scoring
- Chấm điểm: Nếu kết quả chỉ đúng dòng thứ nhất hoặc dòng thứ hai thì chương trình sẽ được 50% số điểm cho test đó.
-
Ràng buộc:
-
20% số test: Tất cả các bít của xâu \(s\) đều là \(0\) hoặc đều là \(1\);
- 20% số test: \(k = 1\);
- 20% số test: \(n \le 20\);
- 20% số test: \(n \le 10^3\);
- 20% số test: Không có thêm ràng buộc nào.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.