Lát sàn

Đề bài

Mô tả

Bạn cần lát kín sàn một căn phòng hình chữ nhật kích thước n×m mét bằng các tấm ván gỗ. Có ba loại ván:

  • Ván loại 1×2 (chiếm 1 hàng, 2 cột liền nhau): có a tấm.
  • Ván loại 2×1 (chiếm 2 hàng, 1 cột liền nhau): có b tấm.
  • Ván loại 2×2: có c tấm.

Không được xoay ván. Nghĩa là ván 1×2 luôn nằm ngang, ván 2×1 luôn nằm dọc. Mỗi ô vuông 1×1 của sàn phải được phủ bởi đúng một tấm ván, các tấm ván không được chồng lên nhau và không được vượt ra ngoài phòng. Không bắt buộc phải dùng hết tất cả các tấm ván.

Hãy xác định xem có thể lát kín sàn hay không, và nếu có thì đưa ra một cách lát cụ thể.

Dữ liệu vào

Một dòng chứa 5 số nguyên n, m, a, b, c.

Dữ liệu ra

Nếu không thể lát kín sàn, in ra một dòng duy nhất chứa từ IMPOSSIBLE.

Ngược lại, in ra n dòng, mỗi dòng gồm m chữ cái Latin thường mô tả một cách lát. Hai ô kề cạnh nhau phải mang cùng một chữ cái nếu chúng thuộc cùng một tấm ván, và phải mang chữ cái khác nhau nếu chúng thuộc hai tấm ván khác nhau. Hai tấm ván không kề nhau có thể được đánh dấu bằng cùng một chữ cái. Nếu có nhiều cách lát, in ra cách bất kỳ.

Ràng buộc

  • 1n,m100
  • 0a,b,c104

Ví dụ

Input Output Giải thích
2 6 2 2 1 aacabb
bbcabb
Một cách lát hợp lệ dùng 2 ván ngang, 2 ván dọc và 1 ván 2×2. Đáp án không duy nhất, mọi cách lát đúng đều được chấp nhận.
4 4 10 10 10 aabb
bbaa
aabb
bbaa
Sàn 4×4 được chia thành các khối 2×2, mỗi khối lát bằng hai ván ngang hoặc hai ván dọc.
1 1 100 100 100 IMPOSSIBLE Ô 1×1 không thể phủ bởi bất kỳ loại ván nào (mọi ván đều có diện tích chẵn hoặc lớn hơn ô).

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