Phân tích: Người hâm mộ quá khích

Test Set 1

Trong Test Set 1, chúng ta có thể thử mọi lộ trình mà mình có thể đi. Trong mỗi phút bất kỳ, chúng ta có 5 lựa chọn: đi một khu phố theo một trong 4 hướng, hoặc đứng yên. Vì chuyến lưu diễn của Peppurr kéo dài nhiều nhất 8 phút, chúng ta cũng chỉ có thể đi trong nhiều nhất 8 phút. Như vậy có nhiều nhất \(5^8\) khả năng, một con số khá nhỏ đối với máy tính. Với mỗi tổ hợp, chúng ta mô phỏng cả lộ trình của mình lẫn lộ trình của Peppurr và ghi nhận mọi lần gặp nhau. Sau khi thử tất cả khả năng, lời giải là IMPOSSIBLE nếu không ghi nhận lần gặp nào; nếu có, lời giải là thời điểm sớm nhất trong số các lần gặp đã ghi nhận.

Test Set 2

Trong Test Set 2, cũng như trong Test Set 1, chuyến lưu diễn của Peppurr sẽ chỉ nằm trên một con đường bắc–nam duy nhất. Nhận thấy rằng nếu muốn gặp Peppurr tại giao lộ \((a, b)\), thứ tự đi qua các khu phố không quan trọng, miễn là số lần đi về phía đông nhiều hơn số lần đi về phía tây đúng \(a\) lần và số lần đi về phía bắc nhiều hơn số lần đi về phía nam đúng \(b\) lần. Vì vậy, chẳng hạn, ta có thể giả sử mình hoàn thành toàn bộ phần đường đi về phía đông trước khi đi theo bất kỳ hướng nào khác. Điều này có nghĩa là một chiến lược tối ưu có thể bắt đầu bằng việc đi X khu phố về phía đông. Sau đó, chúng ta ở trên cùng con đường bắc–nam với Peppurr, nên có thể đi về phía chuyến lưu diễn cho đến khi gặp nhau, hoặc cho đến khi chỉ còn cách 1 khu phố; trong trường hợp sau, chúng ta cần đứng yên 1 phút để tránh cắt ngang đường đi của chuyến lưu diễn ở giữa một khu phố.

Test Set 3

Với Test Set 3, chúng ta có thể mô phỏng chuyến lưu diễn của Peppurr. Nếu sau \(R\) phút, Peppurr ở vị trí cách chúng ta \(X_R\) khu phố về phía đông và \(Y_R\) khu phố về phía bắc (\(X_R\) và \(Y_R\) có thể âm để biểu thị vị trí về phía tây hoặc phía nam), ta chỉ cần kiểm tra liệu mình có thể đến giao lộ đó trong \(R\) phút hay không. May mắn thay, điều này rất dễ kiểm tra: giao lộ có thể đến được trong không quá \(R\) phút khi và chỉ khi \(|X_R| + |Y_R| \le R\). Nói cách khác, giao lộ phải có khoảng cách L1 (còn gọi là khoảng cách Manhattan) không quá \(R\).

Do đó, chúng ta có thể giải bài toán bằng cách mô phỏng lộ trình của Peppurr và, với giao lộ thứ \(i\) được ghé qua, kiểm tra xem có thể đến đó trong \(i\) phút hay không. Nếu có thì \(i\) là đáp án; nếu không, ta tiếp tục xét. Nếu không có giao lộ nào có thể đến được trong thời gian yêu cầu, ta trả lời IMPOSSIBLE.

Dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 1C — Overexcited Fan.