3. Google Code Jam 2020 - Recalculating
Recalculating
Đề bài
Bạn làm việc cho bộ phận thiết kế chỉ đường dự phòng cho drone giao hàng tự lái của Apricot Rules LLC. Công ty sắp đưa drone đầu tiên, Principia, ra thị trường. Bạn phải thiết kế hệ thống dự phòng khi nó mất hệ thống định vị chính như GPS nhưng vẫn cần chỉ đường. Principia hoạt động trên một mặt phẳng Descartes có tọa độ tính bằng mét. Một hoặc nhiều điểm là trung tâm sửa chữa drone, và không có hai trung tâm cùng vị trí.
Principia thu thập được vị trí tương đối của các trung tâm cách nó không quá \(D\) mét theo khoảng cách \(L_1\) (Manhattan). Chẳng hạn: “một trung tâm cách 4 mét về bắc và 3,5 mét về tây, trung tâm khác cách 2,5 mét về đông”. Thông tin không định danh trung tâm, mà chỉ cho vị trí tương đối với Principia.
Có thể tồn tại hai hay nhiều điểm khác nhau cho cùng thông tin, khiến Principia không xác định duy nhất vị trí. Những điểm như vậy gọi là không phân biệt được; các điểm còn lại là phân biệt được.
Một cách hình thức, tại \((x,y)\),
Ở đây \(|z-x|,|w-y|\) là các giá trị tuyệt đối tương ứng. Điểm \((x_1,y_1)\) không phân biệt được khi và chỉ khi tồn tại điểm khác \((x_2,y_2)\) sao cho \(\operatorname{Info}(x_1,y_1)=\operatorname{Info}(x_2,y_2)\).
Ví dụ, với \(D=4\) và các trung tâm \((0,0),(5,0)\), điểm \((0,0)\) không phân biệt được vì \(\operatorname{Info}(0,0)=\{(0,0)\}=\operatorname{Info}(5,0)\); do đó \((5,0)\) cũng vậy. Ngược lại, \(\operatorname{Info}(3.5,0.1)=\{(-3.5,-0.1),(1.5,-0.1)\}\) không bằng thông tin ở bất kỳ điểm nào khác, nên điểm ấy phân biệt được. Hình minh họa miền phân biệt được (đỏ) và không phân biệt được (xanh):
Principia được đặt tại một điểm chọn ngẫu nhiên đều trong tập mọi điểm cách ít nhất một trung tâm không quá \(D\) theo \(L_1\), tức nơi Info khác rỗng. Xác suất thuộc một tập liên tục \(S\) tỉ lệ với diện tích mét vuông của \(S\). Trong ví dụ, mỗi hình vuông đỏ rộng \(4.5\), mỗi phần xanh rộng \(23\) mét vuông. Xác suất vào mỗi hình đỏ là \(4.5/(3\times4.5+2\times23)\), vào mỗi phần xanh là \(23/(3\times4.5+2\times23)\). Biên giữa các phần khác màu có diện tích 0 nên xác suất rơi đúng lên biên bằng 0.
Cho mọi vị trí trung tâm, hãy tính xác suất vị trí triển khai Principia phân biệt được.
Dữ liệu vào
Dòng đầu chứa \(T\). Mỗi test bắt đầu bằng \(N,D\): số trung tâm và khoảng cách \(L_1\) tối đa để thu thập thông tin. Sau đó là \(N\) dòng; dòng \(i\) chứa tọa độ nguyên \(X_i,Y_i\) của trung tâm thứ \(i\). Mọi tọa độ và \(D\) tính bằng mét.
Dữ liệu ra
Với mỗi test, in Case #x: y z, trong đó x bắt đầu từ 1, y,z là số nguyên không âm và y/z biểu diễn xác suất cần tìm khi chọn đều trong mọi vị trí cách ít nhất một trung tâm không quá \(D\) theo \(L_1\). Nếu có nhiều cặp hợp lệ, chọn cặp có z nhỏ nhất.
Ràng buộc
- \(1\le T\le100\); \(1\le D\le10^7\).
- \(-10^9\le X_i,Y_i\le10^9\) với mọi \(i\).
- \((X_i,Y_i)\ne(X_j,Y_j)\) với mọi \(i\ne j\).
Phân nhóm
Test Set 1 (phán quyết hiển thị)
\(N=2\).
Test Set 2 (phán quyết hiển thị)
\(2\le N\le10\).
Test Set 3 (phán quyết hiển thị)
Trong 6 test, \(N=1687\); trong \(T-6\) test còn lại, \(2\le N\le100\).
Điểm các phân nhóm
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 6/32 | 18,75% |
| Test Set 2 | 11/32 | 34,38% |
| Test Set 3 | 15/32 | 46,87% |
Ví dụ
Ví dụ 1
Dữ liệu mẫu và phần giải thích chính thức được trình bày đầy đủ ngay bên dưới.
4
2 4
0 0
5 0
2 1
0 0
5 0
2 4
0 0
4 4
2 4
0 0
5 1Case #1: 27 119
Case #2: 0 1
Case #3: 0 1
Case #4: 1 5??? "Giải thích"
Các test trên thỏa Test Set 1; một test không thỏa nằm cuối phần. Test 1 đã được mô tả trong đề.
Mọi điểm ở miền đỏ giữa phân biệt được vì chỉ chúng thấy cả hai trung tâm và mỗi điểm nhận tập thông tin riêng.
Các điểm ở mỗi miền đỏ trái/phải chỉ thấy một trung tâm nhưng thông tin luôn duy nhất. Ví dụ, nếu Principia biết nó ở 3 mét phía đông một trung tâm, đó không thể là trung tâm $(0,0)$ vì khi ấy nó thấy cả hai; vậy phải là trung tâm $(5,0)$.
Mọi điểm xanh không phân biệt được: thông tin chỉ chứa trung tâm trong tầm, và có một điểm tương ứng ở miền xanh kia cho đúng cùng thông tin.
Xác suất vào mỗi phần đỏ là $4.5/59.5$, nên tổng là $3\times4.5/59.5=27/119$.
Hình sau minh họa test 2. Không nơi nào thấy hơn một trung tâm, nên mọi điểm đủ gần một trung tâm đều có điểm tương ứng gần trung tâm kia. Mẫu `z` phải tối thiểu, vì vậy chỉ `0 1` hợp lệ.
Hình sau minh họa test 3. Biên hai hình xanh gồm các điểm phân biệt được, nhưng diện tích bằng 0 nên xác suất rơi vào đó bằng 0. Mọi điểm triển khai khác đều không phân biệt được.
Hình sau minh họa test 4.
Hình sau minh họa test bổ sung.
Test bổ sung này không thể có trong Test Set 1 nhưng có thể có trong các Test Set khác:
```sample
1
3 4
0 0
1 1
2 3
```
Đầu ra đúng là `Case #1: 101 109`.
Nguồn
Google Code Jam 2020, Vòng 3, bài Recalculating.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
