Gửi bài giải
Điểm:
1,70 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Một cách chia hình chữ nhật đúng được định nghĩa như sau:
- Không chia gì cả
- Chia hình chữ nhật thành ~2~ nữa trên và dưới. ~2~ nửa này lại được chia tiếp
- Chia hình chữ nhật thành ~2~ nửa trái và phải. ~2~ nửa này lại được chia tiếp
Cho ~2~ cách chia hình chữ nhật ~A~ và ~B~, ~2~ hình chữ nhật này có cùng kích thước.
a/ Tìm cách chia đúng ~C~ sử dụng ít lần chia nhất, sao cho mỗi đường chia của ~A~ và ~B~ đều có trong cách chia ~C~
b/ Tìm cách chia đúng ~D~ sử dụng nhiều lần chia nhất, sao cho mỗi đường chia của ~D~ đều có trong cả ~A~ và ~B~
Input
Gồm nhiều bộ test, mỗi bộ:
- Dòng ~1~: ~M~, ~N~ ~(1 \leq M~, ~N \leq 20)~ lần lượt là số cột và số hàng của hình chữ nhật ban đầu
- ~N + 1~ dòng tiếp, mỗi dòng ~4 \times M + 3~ kí tự mô tả cách chia (các cách chia đều chính xác và có dạng hoàn toàn giống phía dưới). Riêng dòng đầu tiên của mỗi mô tả chỉ có ~4 \times M + 2~ kí tự.
Output
Với mỗi test in ra:
- Dòng ~1~: "Case X", trong đó ~X~ là số thứ tự của bộ test, đánh số từ ~1~.
- ~N + 1~ dòng tiếp: ~2~ cách chia giống dạng như input
Sample Input
4 3
_ _ _ _ _ _ _ _
|_ _ _ _| |_|_ _ _|
| | | | |
|_ _|_ _| |_ _ _ _|
3 4
_ _ _ _ _ _
| | | | | |
| | | |_|_ _|
|_|_ _| | | |
|_ _|_| |_ _|_|
0 0
Sample Output
Case 1:
_ _ _ _ _ _ _ _
|_|_ _ _| |_ _ _ _|
| | | | |
|_ _|_ _| |_ _ _ _|
Case 2:
_ _ _ _ _ _
| | | | |
|_|_ _| | |
|_|_|_| | |
|_ _|_| |_ _ _|
Bình luận