trang chủ / đề bài / icpc23_reg_h

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 n×n ô. Các hàng được đánh số từ 1 đến n theo hướng từ bắc xuống nam, các cột được đánh số từ 1 đến n theo hướng từ đông sang tây. Ô ở hàng thứ i, cột thứ j được kí hiệu là (i,j). 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 4 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 t (1≤t≤105): số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu chứa số nguyên n (2≤n≤5000): kích thước lưới.
  • Dòng thứ hai chứa xâu s: 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 a kích thước n×n, trong đó ai,j=0 nếu ô (i,j) hài hoà và ai,j=1 nếu ô đó bình thường.
    • Các phần tử của a được liệt kê lần lượt theo từng hàng để được xâu nhị phân b độ dài n×n (đánh số từ 0). Cụ thể, b(i−1)×n+(j−1)=ai,j với mọi 1≤i,j≤n.
    • Sau đó b được chia thành các xâu con nhị phân liên tiếp độ dài 6. Nếu xâu con cuối cùng có ít hơn 6 ký tự, thêm các ký tự 0 vào cuối cho đến khi đủ độ dài 6. Gọi ci là xâu con thứ i thu được.
    • Với mỗi xâu ci, viết ci=ci,0ci,1ci,2ci,3ci,4ci,5 và tính di=∑j=052j×ci,j. Dễ thấy 0≤di≤63.
    • Cuối cùng, ký tự thứ i của xâu s là ký tự thứ di của xâu sau (gồm 64 ký tự, đánh số từ 0 đến 63): ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Dữ liệu bảo đảm tổng n2 của tất cả các bộ dữ liệu không vượt quá 2.5·107.

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 x1,y1,x2,y2 (1≤x1,y1,x2,y2≤n, x1≠x2, y1≠y2), trong đó (x1,y1) và (x2,y2) 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

  • 1≤t≤105
  • 2≤n≤5000
  • Tổng n2 không vượt quá 2.5·107.

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 a gồm các hàng 001, 010, 101. Ta có b = 001010101, c0 = 001010, c1 = 101000, d0=22+24=20, d1=20+22=5, nên s = UF. Một vị trí khác cũng hợp lệ là góc trên trái (1,1) và góc dưới phải (2,3). 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

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0