Tôi đang ở đâu?
Đề bài
Mô tả
Tôi là ai? Tôi là gì? Tôi tồn tại để làm gì? Đó đều là những câu hỏi khó đã khiến các triết gia bận rộn suốt mấy thiên niên kỷ qua. Nhưng với câu hỏi "Tôi đang ở đâu?" thì điện thoại thông minh và vệ tinh GPS ngày nay đã lấy đi gần hết sự hồi hộp.
Để chứng minh GPS mạnh hơn bản đồ kiểu cũ đến mức nào, Công ty Định vị Bản đồ Tức thời (ICPC) tổ chức một buổi trình diễn. Lập luận của họ là bản đồ chỉ hữu ích khi bạn đã biết mình đang ở đâu, còn khi xuất phát từ một vị trí không biết trước thì kém hữu ích hơn nhiều.
Khu vực thử nghiệm là một lưới ô vuông vô hạn trên mặt phẳng tọa độ. Phần lớn các ô trống, nhưng có hữu hạn ô có một điểm mốc ở tâm (hình (a) dưới đây là ví dụ với năm ô có mốc, ứng với ví dụ 1). Mọi ô trống trông giống hệt nhau và mọi ô có mốc cũng trông giống hệt nhau. Giả sử bạn được cho bản đồ của khu vực (tức là vị trí của tất cả các mốc) và bị đặt vào một ô mà bạn không biết. Bạn cần bao lâu để biết mình thực sự đang ở đâu?
Câu trả lời của ICPC rất rõ ràng: có thể rất, rất lâu, trong khi GPS cho bạn câu trả lời ngay lập tức. Nhưng chính xác là bao lâu?
Hình (a): lưới với các mốc X của ví dụ 1 (hàng trên cùng có , cột trái nhất có ).
grid ....X .X... ..... X..X. ..X..
Trong thử nghiệm, người tham gia khám phá xung quanh bằng cách đi theo một đường xoắn ốc mở rộng theo chiều kim đồng hồ, các bước đầu tiên được cho trong hình (b). Ô xuất phát được đánh số , các số còn lại cho biết thứ tự các ô được thăm: đầu tiên đi lên ô ngay phía trên, rồi vòng theo chiều kim đồng hồ quanh ô xuất phát, mỗi vòng xa hơn vòng trước một ô.
Hình (b): thứ tự thăm các ô, tính so với ô xuất phát (ô tô màu).
grid 24 9 10 11 12 23 8 1 2 13 22 7 0 3 14 21 6 5 4 15 20 19 18 17 16 highlight green 3,3
Người tham gia chỉ nhìn thấy mốc khi đứng tại ô chứa mốc đó, và họ dừng khám phá ngay khi biết mình đang ở đâu dựa trên các ô đã thấy cho tới lúc đó. Nghĩa là dãy các ô trống và ô có mốc quan sát được chỉ có thể bắt đầu từ đúng một vị trí xuất phát. Lưới là vô hạn, nhưng việc khám phá luôn kết thúc, vì khi đã thấy mọi mốc trên lưới thì chắc chắn họ biết mình đang ở đâu.
Cho hàng trăm người chạy vòng tròn thì tốn kém, nên ICPC cho rằng viết một chương trình mô phỏng sẽ rẻ và nhanh hơn. Bạn hãy giúp họ.
Dữ liệu vào
Dữ liệu vào mô tả một lưới. Dòng đầu tiên chứa hai số nguyên , . Mỗi dòng trong dòng tiếp theo chứa ký tự, mô tả một phần của lưới thử nghiệm. Ký tự thứ của dòng thứ trong phần mô tả này cho biết nội dung của ô có tọa độ . Ký tự đó là . hoặc X, nghĩa là ô đó trống hoặc có mốc. Mọi ô nằm ngoài phần được mô tả đều trống.
Dữ liệu ra
Trong thử nghiệm của ICPC, người tham gia biết mình sẽ xuất phát ở một vị trí nào đó với , . Số bước để xác định được vị trí xuất phát là số thứ tự (trong hình (b)) của ô mà tại đó người tham gia lần đầu biết chắc mình xuất phát ở đâu, trong số các vị trí xuất phát có thể này.
In ra ba dòng:
- Dòng thứ nhất: kỳ vọng của số bước cần để xác định vị trí xuất phát, khi vị trí xuất phát được chọn ngẫu nhiên đều. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá .
- Dòng thứ hai: số bước lớn nhất cần thiết để xác định vị trí xuất phát.
- Dòng thứ ba: tất cả các tọa độ xuất phát cần đúng số bước lớn nhất đó, viết dạng
(x,y), cách nhau bởi dấu cách, sắp xếp theo tăng dần, nếu cùng thì theo tăng dần.
Ràng buộc
- .
- Tổng số mốc trong lưới từ tới .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 5 ....X .X... ..... X..X. ..X.. |
9.960 18 (1,4) (4,5) |
Lưới trong hình (a). Hai vị trí xuất phát và cần nhiều bước nhất, bước. |
| 5 1 ..XX. |
4.600 7 (1,1) (5,1) |
Từ hoặc thấy ngay mốc ở bước , nhưng chỉ ở bước (ô bên phải) mới phân biệt được hai vị trí này. Từ hoặc cần tới bước (ô bên trái). |
Bình luận