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ừ đến . Các ô nằm trên viền (hàng , hàng , cột , cột ) luôn được canh giữ bởi các lính gác tự động. Phần bên trong gồm vị trí có thể đặt đèn hiệu, là các ô với .
Khoảng cách giữa hai vị trí và được đo theo metric Chebyshev: .
Các đèn hiệu được triển khai lần lượt từng chiếc một theo quy trình sau:
- 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).
- Đặ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.
- Quy tắc phá hòa: chọn vị trí có chỉ số hàng nhỏ nhất; nếu vẫn hòa, chọn vị trí có chỉ số cột nhỏ nhất.
Cho truy vấn độc lập, mỗi truy vấn cho và : hãy xác định chính xác vị trí được chọn cho đèn hiệu thứ trên mái vòm có tham số kích thước .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên ().
- Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và cách nhau bởi dấu cách (, ).
Dữ liệu ra
In ra dòng. Dòng thứ 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ứ .
Ràng buộc
- .
- .
- .
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 (lưới từ đến ), đèn hiệu đầu tiên lần lượt ở , , , , , , , , , . Với (lưới từ đến ), đèn hiệu đầu tiên lần lượt ở , , , , , , , , , . |
| 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 (lưới từ đến ), đèn hiệu đầu tiên ở tâm với khoảng cách ; sau đó mọi ô trống đều có khoảng cách nên được chọn theo thứ tự hàng rồi cột: , , , , , , , . Đèn thứ ở , đèn thứ ở . |
Bình luận