trang chủ / bài tập / bintable

Bảng nhị phân (Easy)

Đề bài

Mô tả

Cho một bảng nhị phân kích thước n×m, mỗi ô chứa ký tự 0 hoặc 1.

Trong một thao tác, bạn chọn 3 ô khác nhau nằm trong cùng một hình vuông con 2×2 và đảo bit ở cả 3 ô đó (đổi 0 thành 11 thành 0).

Nhiệm vụ của bạn là đưa toàn bộ bảng về 0. Bạn được phép thực hiện tối đa 3nm 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 0 là được chấp nhận.

Dữ liệu vào

Dòng đầu chứa một số nguyên t (1t5000) — số test.

Với mỗi test:

  • Dòng đầu chứa hai số nguyên n,m (2n,m100).
  • n dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài m mô tả các hàng của bảng.

Tổng n·m qua tất cả các test không vượt quá 20000.

Dữ liệu ra

Với mỗi test, in ra:

  • Dòng đầu chứa số nguyên k (0k3nm) — số thao tác sử dụng.
  • k dòng tiếp theo, mỗi dòng gồm 6 số nguyên x1,y1,x2,y2,x3,y3 (1xin, 1yim) mô tả 3 ô 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 2×2.

Ràng buộc

  • 1t5000
  • 2n,m100
  • n·m20000

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 ô (1,1),(2,1),(2,2). Sau thao tác, mọi ô trong bảng đều bằng 0.
1
3 3
011
101
110
2
2 1 3 1 3 2
1 2 1 3 2 3
Thao tác 1 đảo (2,1),(3,1),(3,2), bảng trở thành 011/001/000. Thao tác 2 đảo (1,2),(1,3),(2,3), bảng trở thành toàn 0.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0