trang chủ / đề bài / icpc26_mb_e

Triển khai đèn hiệu

Đề bài

Mô tả

Một mái vòm phòng thủ hành tinh được mô hình hóa thành một lưới ô vuông có các hàng và các cột được đánh số từ 0 đến 2N. Các ô nằm trên viền (hàng 0, hàng 2N, cột 0, cột 2N) luôn được canh giữ bởi các lính gác tự động. Phần bên trong gồm (2N−1)×(2N−1) vị trí có thể đặt đèn hiệu, là các ô (r,c) với 1≤r,c≤2N−1.

Khoảng cách giữa hai vị trí (L1,C1) và (L2,C2) được đo theo metric Chebyshev: max(|L1−L2|,|C1−C2|).

Các đèn hiệu được triển khai lần lượt từng chiếc một theo quy trình sau:

  1. Với mỗi vị trí bên trong còn trống, tính khoảng cách nhỏ nhất từ nó đến một ô đã bị chiếm bất kỳ (ô có lính gác trên viền hoặc ô đã có đèn hiệu).
  2. Đặt đèn hiệu mới tại một vị trí còn trống có khoảng cách nhỏ nhất này lớn nhất.
  3. Quy tắc phá hòa: chọn vị trí có chỉ số hàng r nhỏ nhất; nếu vẫn hòa, chọn vị trí có chỉ số cột c nhỏ nhất.

Cho Q truy vấn độc lập, mỗi truy vấn cho N và K: hãy xác định chính xác vị trí (r,c) được chọn cho đèn hiệu thứ K trên mái vòm có tham số kích thước N.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên Q (2≤Q≤105).
  • Mỗi dòng trong Q dòng tiếp theo chứa hai số nguyên N và K cách nhau bởi dấu cách (2≤N≤30, 1≤K≤min(109,(2N−1)2)).

Dữ liệu ra

In ra Q dòng. Dòng thứ i chứa hai số nguyên (hàng, cột) cách nhau bởi dấu cách, là đáp án của truy vấn thứ i.

Ràng buộc

  • 2≤Q≤105.
  • 2≤N≤30.
  • 1≤K≤min(109,(2N−1)2).

Ví dụ

Input Output Giải thích
5
3 1
3 2
3 5
3 9
4 10
4 4
2 2
4 2
6 6
2 2
Với N=3 (lưới từ 0 đến 8), 10 đèn hiệu đầu tiên lần lượt ở (4,4), (2,2), (2,4), (2,6), (4,2), (4,6), (6,2), (6,4), (6,6), (1,1). Với N=4 (lưới từ 0 đến 16), 10 đèn hiệu đầu tiên lần lượt ở (8,8), (4,4), (4,8), (4,12), (8,4), (8,12), (12,4), (12,8), (12,12), (2,2).
4
2 1
2 6
2 9
30 1000000000
2 2
2 3
3 3
975503360 69435392
Ví dụ bổ sung (không có trong đề gốc). Với N=2 (lưới từ 0 đến 4), đèn hiệu đầu tiên ở tâm (2,2) với khoảng cách 2; sau đó mọi ô trống đều có khoảng cách 1 nên được chọn theo thứ tự hàng rồi cột: (1,1), (1,2), (1,3), (2,1), (2,3), (3,1), (3,2), (3,3). Đèn thứ 6 ở (2,3), đèn thứ 9 ở (3,3).

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