Đề bài
An rất thích chơi với xâu nhị phân (xâu nhị phân là xâu chứa các bit 0 và 1). Hôm nay An có một xâu nhị phân độ dài . 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á bit 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ỳ bit nào của xâu (bit 0 lật thành 1 và bit 1 lật thành bit 0).
Vì sắp đến giờ vào lớp nên An muốn nhờ bạn tìm số thao tác tối thiểu mà anh ấy cần. Ngoài ra, An cũng muốn bạn đưa ra một trong các xâu có được sau khi sửa đổi.
Dữ liệu vàobina.inp
Vào từ tệp văn bản bina.inp. Dòng đầu tiên chứa hai số nguyên và (). Dòng thứ hai chứa xâu nhị phân độ dài .
Kết quả rabina.out
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.
Ràng buộc
- Có 20% số test ứng với 20% số điểm thoả mãn: Tất cả các bit của xâu đều là 0 hoặc đều là 1;
- 20% số test khác ứng với 20% số điểm thoả mãn: ;
- 20% số test khác ứng với 20% số điểm thoả mãn: ;
- 20% số test khác ứng với 20% số điểm thoả mãn: ;
- 20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.
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 của test đó.
Ví dụ
Ví dụ 1
2 1 11
1 10
Giải thích
Trong ví dụ đầu tiên, bit 1 xuất hiện hai lần liên tiếp nên chúng ta có thể sửa đổi xâu 11 thành 10 bằng một thao tác lật bit thứ hai. Chú ý rằng bạn có thể đưa ra xâu sửa đổi là 01 bằng một thao tác lật bit thứ nhất.
Ví dụ 2
2 2 11
0 11
Giải thích
Trong ví dụ thứ hai, bạn không cần sửa đổi xâu vì xâu không có nhiều hơn 2 bit liên tiếp giống nhau.
Ví dụ 3
4 1 1001
2 1010
Giải thích
Trong ví dụ thứ ba, bit 0 xuất hiện hai lần liên tiếp nên chúng ta có thể sửa đổi xâu 1001 thành 1010 bằng hai thao tác lật bit thứ ba và thứ tư.