Đề 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 bít 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á bít liên tiếp giống nhau. Để đạt đ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 bít 1 và bít 1 lật thành 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à ().
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 thỏa mãn: Tất cả các bít của xâu đều là 0 hoặc đều là 1;
- 20% số test khác ứng với 20% số điểm thỏa mãn: ;
- 20% số test khác ứng với 20% số điểm thỏa mãn: ;
- 20% số test khác ứng với 20% số điểm thỏa 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 cho test đó.
Ví dụ
Ví dụ 1
2 1 11
1 10
Giải thích
Trong ví dụ đầu tiên, bít 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 bít 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 bít 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 bít liên tiếp giống nhau.
Ví dụ 3
4 1 1001
2 1010
Giải thích
Trong ví dụ thứ ba, bít 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 bít thứ ba và thứ tư.