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

Xếp chỗ học sinh

Đề bài

Mô tả

Một lớp học gồm n hàng và m cột, mỗi ô có một học sinh. Hai học sinh được gọi là láng giềng nếu hai ô của họ có cạnh chung.

Học sinh được đánh số từ 1 đến n·m theo thứ tự dòng: học sinh ở ô tại hàng i, cột j ban đầu mang số (i1)·m+j.

Bạn cần tìm một cách xếp chỗ mới — vẫn là một ma trận n×m chứa đúng các số từ 1 đến n·m, mỗi số đúng một lần — sao cho không có hai số nào là láng giềng ở cách xếp ban đầu lại tiếp tục là láng giềng ở cách xếp mới. Nếu không tồn tại cách xếp như vậy, hãy báo không có nghiệm.

Dữ liệu vào

Một dòng chứa hai số nguyên nm.

Dữ liệu ra

Nếu không tồn tại ma trận thoả mãn, in ra một dòng "NO" (không kèm dấu ngoặc kép).

Ngược lại, in ra "YES" ở dòng đầu, rồi n dòng tiếp theo, mỗi dòng có m số nguyên cách nhau bởi dấu cách, tạo thành ma trận thoả yêu cầu.

Nếu có nhiều đáp án thì in ra một đáp án bất kỳ.

Ràng buộc

  • 1n,m105
  • n·m105

Ví dụ

Input Output Giải thích
2 4 YES
5 4 7 2
3 6 1 8
Ma trận ban đầu là 1 2 3 4 / 5 6 7 8. Có thể kiểm tra rằng không có cặp học sinh nào là láng giềng ở cả hai cách xếp.
2 1 NO Chỉ có hai cách xếp khả dĩ và ở cả hai cách thì học sinh số 1 và số 2 đều là láng giềng.

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