Bảng nhị phân (Easy)
Đề bài
Mô tả
Cho một bảng nhị phân kích thước , mỗi ô chứa ký tự hoặc .
Trong một thao tác, bạn chọn ô khác nhau nằm trong cùng một hình vuông con và đảo bit ở cả ô đó (đổi thành và thành ).
Nhiệm vụ của bạn là đưa toàn bộ bảng về . Bạn được phép thực hiện tối đa thao tác (không cần tối thiểu hóa số thao tác). Có thể chứng minh rằng luôn tồn tại cách làm thỏa mãn.
Vì đáp án có thể không duy nhất, dãy thao tác của bạn sẽ được kiểm tra bằng checker: chỉ cần dãy thỏa mãn các ràng buộc và đưa bảng về toàn là được chấp nhận.
Dữ liệu vào
Dòng đầu chứa một số nguyên () — số test.
Với mỗi test:
- Dòng đầu chứa hai số nguyên ().
- dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài mô tả các hàng của bảng.
Tổng qua tất cả các test không vượt quá .
Dữ liệu ra
Với mỗi test, in ra:
- Dòng đầu chứa số nguyên () — số thao tác sử dụng.
- dòng tiếp theo, mỗi dòng gồm số nguyên (, ) mô tả ô bị đảo trong thao tác. Ba ô phải khác nhau đôi một và phải nằm trong cùng một hình vuông con .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 2 2 10 11 |
1 1 1 2 1 2 2 |
Thao tác duy nhất đảo các ô . Sau thao tác, mọi ô trong bảng đều bằng . |
| 1 3 3 011 101 110 |
2 2 1 3 1 3 2 1 2 1 3 2 3 |
Thao tác đảo , bảng trở thành 011/001/000. Thao tác đảo , bảng trở thành toàn . |
Bình luận