Google Code Jam 2020 - Wormhole in One
Xem PDFĐề bài
Bạn đang tham gia một cuộc thi golf siêu không gian liên thiên hà và đã tiến vào vòng chung kết! Bạn thực sự quyết tâm giành chiến thắng, vì vậy bạn muốn chuẩn bị một chiến thuật tất thắng.
Trong golf siêu không gian, cũng như trong golf thông thường, bạn dùng gậy đánh một quả bóng, khiến bóng bay theo hướng do bạn chọn. Sân chơi là một mặt phẳng hai chiều, trên đó các điểm biểu diễn những lỗ khác nhau. Quả bóng cũng được biểu diễn bằng một điểm, và bạn được chọn vị trí xuất phát của bóng, miễn là vị trí đó không trùng với một lỗ.
Vì đây là golf siêu không gian, người chơi được phép biến một số cặp lỗ thành các lỗ sâu bằng cách liên kết chúng với nhau. Mỗi lỗ hoặc được để lại làm lỗ bình thường, hoặc được liên kết với nhiều nhất một lỗ khác (không bao giờ với chính nó). Lỗ sâu là liên kết vô hướng và có thể được đi qua theo cả hai chiều.
Do môi trường không có ma sát, khi bạn đánh bóng, bóng chuyển động thẳng theo một hướng và giữ hướng đó mãi mãi, trừ khi nó đến một lỗ; gọi lỗ đó là \(h\). Khi chạm \(h\), bóng dừng nếu \(h\) không nối với lỗ nào khác. Nếu \(h\) nối với một lỗ khác \(h'\), bóng lập tức đi ra từ \(h'\) rồi tiếp tục chuyển động theo đúng hướng trước đó.
Bạn biết vị trí của mỗi lỗ. Bạn muốn tối đa hóa số lỗ phân biệt có thể chạm bằng một cú đánh. Vì vậy, bạn muốn chọn vị trí xuất phát, hướng đánh và những cặp lỗ sẽ được liên kết thành lỗ sâu, nếu có. Bóng không được xuất phát tại cùng vị trí với một lỗ sâu. Khi bóng đi qua một lỗ sâu, cả lỗ đi vào lẫn lỗ đi ra đều được tính. Mỗi lỗ chỉ được tính một lần, kể cả khi bóng đi vào hoặc đi ra khỏi nó (hoặc cả hai) nhiều lần. Nếu bóng dừng trong một lỗ, lỗ đó cũng được tính.
Dữ liệu vào
Dòng đầu cho biết số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa số nguyên \(N\): tổng số lỗ. \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\), lần lượt là tọa độ X và Y của lỗ thứ \(i\).
Dữ liệu ra
Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số lỗ phân biệt lớn nhất có thể chạm nếu đưa ra các quyết định tối ưu như trên.
Ràng buộc
- \(1 \le T \le 100\).
- \(-10^9 \le X_i \le 10^9\) với mọi \(i\).
- \(-10^9 \le Y_i \le 10^9\) với mọi \(i\).
- \((X_i,Y_i) \ne (X_j,Y_j)\) với mọi \(i \ne j\). (Không có hai lỗ cùng tọa độ.)
Phân nhóm
Test Set 1 (phán quyết hiển thị)
\(1 \le N \le 7\).
Test Set 2 (phán quyết ẩn)
\(1 \le N \le 100\).
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 10/26 | 38,46% |
| Test Set 2 | 16/26 | 61,54% |
Ví dụ
Ví dụ 1
Input
5
2
0 0
5 5
3
0 0
5 5
5 0
5
0 0
5 5
5 0
3 2
2 4
7
0 0
1 1
2 1
3 1
8 2
11 2
14 2
1
-1000000000 1000000000Output
Case #1: 2
Case #2: 3
Case #3: 4
Case #4: 7
Case #5: 1Giải thích
Trong trường hợp mẫu số 1, ta có thể nối hai lỗ bằng một lỗ sâu để chạm cả hai bằng cách đưa bóng vào một trong hai lỗ. Nếu không có lỗ sâu, bóng sẽ dừng tại lỗ đầu tiên nó chạm, nên không thể chạm nhiều hơn một lỗ.
Trong trường hợp mẫu số 2, ta có thể nối lỗ tại \((0,0)\) với lỗ tại \((5,5)\). Sau đó, chẳng hạn ta đánh bóng từ \((4.9,5)\) theo chiều ngang dương để bóng chạm \((5,5)\) trước. Bóng đi vào đó rồi đi ra từ \((0,0)\), vẫn giữ hướng ngang dương. Cuối cùng, bóng chạm \((5,0)\) và dừng (vì lỗ đó không được liên kết với lỗ sâu nào).
Trong trường hợp mẫu số 3, ta có thể nối cặp lỗ tại \((0,0)\) và \((5,0)\), đồng thời nối cặp tại \((3,2)\) và \((5,5)\). Đánh bóng từ \((4,-1)\) về phía \((5,0)\) khiến bóng lần lượt chạm \((5,0)\), \((0,0)\), \((5,5)\) và \((3,2)\).
Trong trường hợp mẫu số 4, ta có thể nối các cặp \((0,0)\)–\((1,1)\), \((2,1)\)–\((11,2)\) và \((8,2)\)–\((14,2)\). Đánh bóng từ \((-1,0)\) về phía \((0,0)\) khiến bóng lần lượt chạm: \((0,0)\), \((1,1)\), \((2,1)\), \((11,2)\), \((14,2)\), \((8,2)\), \((11,2)\), \((2,1)\) và \((3,1)\). Dù \((11,2)\) và \((2,1)\) được chạm hai lần, mỗi lỗ chỉ được tính một lần vì đề bài yêu cầu đếm các lỗ phân biệt.
Trong trường hợp mẫu số 5, chỉ có một lỗ và ta có thể đánh bóng vào đó mà không cần xét lỗ sâu. (Ta có thể chọn bất kỳ vị trí xuất phát nào, kể cả bên ngoài miền tọa độ được phép của các lỗ.)
Nguồn
Google Code Jam 2020, Vòng 2, bài Wormhole in One.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2020 - Round 2 (16 Tháng năm, 2020)
Bình luận