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 mét bằng các tấm ván gỗ. Có ba loại ván:
- Ván loại (chiếm hàng, cột liền nhau): có tấm.
- Ván loại (chiếm hàng, cột liền nhau): có tấm.
- Ván loại : có tấm.
Không được xoay ván. Nghĩa là ván luôn nằm ngang, ván luôn nằm dọc. Mỗi ô vuông 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 số nguyên , , , , .
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 dòng, mỗi dòng gồ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
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 ván ngang, ván dọc và ván . Đá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 được chia thành các khối , 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 | Ô 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