{"code":"domiart","name":"Mỹ thuật Domino (DHHV 2021)","description":"Hai chị em Hồng, Phúc có một mảnh giấy to gồm $m$ hàng $n$ cột, các hàng được đánh số từ 1 đến $m$ từ trên xuống dưới, các cột được đánh số từ 1 đến $n$ từ trái sang phải, ô nằm giao giữa hàng $i$ và cột $j$ được gọi là ô ($i,j$). Hai chị em cùng nhau vẽ và tô màu trên mảnh giấy, em Phúc đã lựa chọn một số ô và tô màu các ô đó, Hồng rất thích kiểu giấy domino nên Hồng muốn vẽ $k$ hình domino (mỗi hình có kích thước $1× 2$ hoặc $2× 1$ và chứa chọn hai ô chưa được tô màu của mảnh giấy). Để tạo điểm nhấn trên mảnh giấy, Hồng muốn lựa chọn các vị trí vẽ $k$ hình domino để sau đó có thể chọn được một hình vuông lớn nhất, hình vuông không chứa ô đã bị tô màu cũng như ô thuộc vào một trong $k$ hình domino, hình vuông đó sẽ cho em Phúc vẽ và tô màu.\r\n\r\n**Yêu cầu**: Cho $m,n,k$ và vị trí các ô mà em Phúc đã tô màu, hãy giúp Hồng lựa chọn các vị trí vẽ $k$ hình domino để có thể tìm được hình vuông lớn nhất thỏa mãn yêu cầu trên.\r\n\r\n####Input\r\n- Dòng đầu chứa ba số nguyên $m,n,k$;\r\n- Tiếp theo là $m$ dòng, mỗi dòng chứa một xâu độ dài $n$ mô tả mảnh giấy, ví trí các ô chưa tô màu là ký tự `.`, vị trí các ô đã được tô màu là `#`. Dữ liệu đảm bảo để có thể vẽ được $k$ hình domino.\r\n\r\n####Output\r\n- Xuất ra độ dài cạnh hình vuông lớn nhất\r\n\r\n####Constraints\r\n- $m,n≤ 32$\r\n\r\n####Scoring\r\n- Subtask $1$ ($40\\%$ số điểm): $m,n≤ 8,k≤ 3$.\r\n- Subtask $2$ ($30\\%$ số điểm): $m≤ 8,n≤ 32$.\r\n- Subtask $3$ ($30\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 5 2\r\n        .....\r\n        ....#\r\n        ....# \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2 4 2\r\n        1 4 1\r\n        \r\n        3 (<- đây là output)\r\n        ```\r\n    ??? warning \"Note\"\r\n        ```\r\n        ...22\r\n        ...1#\r\n        ...1#\r\n        ```\r\n        \r\n        - Chữ số 1 và 2 thể hiện các ô chứa hình domino. Diện tích hình vuông lớn nhất chọn được là 9.","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}