Cung điện hài hoà
Đề bài
Mô tả
Tại cố đô Huế, nhà vua muốn xây dựng một cung điện lộng lẫy. Kinh thành được chia thành một lưới ô. Các hàng được đánh số từ đến theo hướng từ bắc xuống nam, các cột được đánh số từ đến theo hướng từ đông sang tây. Ô ở hàng thứ , cột thứ được kí hiệu là . Mỗi ô toả ra năng lượng hài hoà hoặc năng lượng bình thường.
Cung điện phải là một hình chữ nhật nằm trong lưới, có các cạnh song song với biên của kinh thành. Ngoài ra, để hợp phong thuỷ, trong góc của cung điện phải có đúng ba góc là ô hài hoà và góc còn lại là ô bình thường. Hãy tìm một vị trí để xây cung điện. Nhà vua không kiên nhẫn, nên bạn phải tìm thật nhanh!
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu chứa số nguyên (): kích thước lưới.
- Dòng thứ hai chứa xâu : biểu diễn nén Base64 của lưới, thu được theo các bước sau:
- Đầu tiên, lưới được biểu diễn bằng ma trận kích thước , trong đó nếu ô hài hoà và nếu ô đó bình thường.
- Các phần tử của được liệt kê lần lượt theo từng hàng để được xâu nhị phân độ dài (đánh số từ ). Cụ thể, với mọi .
- Sau đó được chia thành các xâu con nhị phân liên tiếp độ dài . Nếu xâu con cuối cùng có ít hơn ký tự, thêm các ký tự vào cuối cho đến khi đủ độ dài . Gọi là xâu con thứ thu được.
- Với mỗi xâu , viết và tính . Dễ thấy .
- Cuối cùng, ký tự thứ của xâu là ký tự thứ của xâu sau (gồm ký tự, đánh số từ đến ):
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
Dữ liệu bảo đảm tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, nếu không có vị trí thích hợp để xây cung điện, in NO trên một dòng.
Ngược lại, in YES trên dòng thứ nhất. Dòng thứ hai in bốn số nguyên (, , ), trong đó và là hai góc đối diện của cung điện.
Nếu có nhiều đáp án đúng, in ra đáp án bất kỳ.
Ràng buộc
- Tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 UF 3 VH 4 /zO |
YES 1 3 2 1 NO YES 4 2 3 1 |
Bộ thứ nhất: ma trận gồm các hàng 001, 010, 101. Ta có = 001010101, = 001010, = 101000, , , nên = UF. Một vị trí khác cũng hợp lệ là góc trên trái và góc dưới phải . Bộ thứ hai: ma trận gồm các hàng 101, 010, 111; mọi hình chữ nhật đều có ít nhất hai góc bình thường. Bộ thứ ba: ma trận gồm các hàng 1111, 1111, 0011, 0111. |
| 3 2 G 2 I 3 uD |
NO YES 1 1 2 2 NO |
Ví dụ bổ sung. Các ma trận lần lượt là 01 / 10, 00 / 01 và 011 / 101 / 110. |
Bình luận