3. Google Code Jam 2013 - Multiplayer Pong
Hai đội chơi bóng bàn (Pong). Pong là một trò chơi máy tính đơn giản, trong đó mỗi người chơi điều khiển một cây vợt (ta coi là một điểm), và một quả bóng nhỏ nảy qua lại. Các thành viên trong một đội phải đánh bóng theo một thứ tự xoay vòng cố định (ví dụ: trong một đội ba người, người đầu tiên chạm bóng là P1, sau đó đến P2, rồi P3 và sau đó mới quay lại P1), cho đến khi một người chơi không thể đánh trúng bóng, lúc đó bóng sẽ rời khỏi sân và đội của người chơi đó thua.
Cụ thể hơn: sân chơi là một hình chữ nhật kích thước \(A \times B\). Trên mỗi bức tường thẳng đứng (chiều dài \(A\)) có một số cây vợt, mỗi cây vợt tương ứng với một người chơi của đội bảo vệ bức tường đó. Mỗi cây vợt là một điểm. Tất cả các vợt của các thành viên trong cùng một đội di chuyển theo chiều dọc với cùng một tốc độ (đơn vị mỗi giây) và có thể đi xuyên qua nhau tự do. Có một quả bóng với vị trí ban đầu (dọc và ngang, tính từ góc dưới bên trái) và vận tốc ban đầu (dọc và ngang, đơn vị mỗi giây) đã biết. Người chơi được phép chọn vị trí ban đầu của các cây vợt trên tường của mình sau khi biết vị trí ban đầu của bóng. Bất cứ khi nào bóng chạm vào tường ngang, nó sẽ nảy ra (với góc tới bằng góc phản xạ). Bất cứ khi nào bóng chạm vào một đầu thẳng đứng của sân, nếu vợt của người chơi đến lượt chạm bóng đang ở đó, bóng sẽ nảy lại; nếu không, đội của người chơi đó sẽ thua.
Trận đấu có thể kéo dài rất lâu khi các cầu thủ đánh bóng qua lại. Mục tiêu của bạn là xác định kết quả cuối cùng (giả định tất cả người chơi đều chơi tối ưu).
Dữ liệu vào
Dòng đầu tiên của đầu vào chứa số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo, mỗi bộ gồm bốn dòng:
- Dòng đầu tiên chứa hai số nguyên \(A\) và \(B\), mô tả chiều cao và chiều rộng của sân chơi.
- Dòng thứ hai chứa hai số nguyên \(N\) và \(M\), mô tả kích thước của hai đội: \(N\) là số người chơi của đội có vợt ở tường \(X = 0\), và \(M\) là số người chơi của đội có vợt ở tường \(X = B\).
- Dòng thứ ba chứa hai số nguyên \(V\) và \(W\), mô tả tốc độ của các cây vợt của đội thứ nhất và đội thứ hai tương ứng.
- Dòng thứ tư chứa bốn số nguyên: \(Y, X, V_Y\) và \(V_X\), mô tả vị trí ban đầu (dọc và ngang) và vận tốc ban đầu của bóng (bóng di chuyển \(V_Y\) đơn vị lên trên và \(V_X\) đơn vị sang phải mỗi giây, cho đến khi nó nảy).
Dữ liệu ra
Với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một trong ba kết quả có thể:
- "DRAW" (nếu trận đấu có thể kéo dài mãi mãi).
- "LEFT z" (nếu đội ở tường \(X = 0\) thắng, và đội đối phương có thể đánh bóng tối đa \(z\) lần).
- "RIGHT z" (nếu đội ở tường \(X = B\) thắng, và đội đối phương có thể đánh bóng tối đa \(z\) lần).
Ràng buộc
- \(1 \le T \le 100\).
- \(0 < X < B\).
- \(0 < Y < A\).
Phân nhóm
- Small dataset (Test set 1):
- \(1 \le N, M \le 10^6\)
- \(1 \le V, W \le 10^{12}\)
- \(-10^{12} \le V_Y \le 10^{12}\)
- \(-10^6 \le V_X \le 10^6\)
- \(2 \le A, B \le 10^6\)
- Large dataset (Test set 2):
- \(1 \le N, M \le 10^{100}\)
- \(1 \le V, W \le 10^{100}\)
- \(-10^{100} \le V_Y, V_X \le 10^{100}\)
- \(2 \le A, B \le 10^{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 | 12/37 | 32,43% |
| Test Set 2 | 25/37 | 67,57% |
Ví dụ
Ví dụ 1
Input
4
6 4
1 2
3 1
5 1 4 8
12 3
3 1
2 3
1 1 2 4
12 3
1 3
3 1
1 1 2 4
12 2
1 2
10 2
3 1 13 4Output
Case #1: LEFT 2
Case #2: DRAW
Case #3: LEFT 3
Case #4: RIGHT 11Note
Hình ảnh mô tả lối chơi trong ví dụ đầu tiên. Quả bóng nảy khỏi tường bên phải tại thời điểm 0.375 (người chơi RIGHT đầu tiên chặn nó, ví dụ bằng cách bắt đầu với vợt ở đó và không di chuyển), sau đó nảy khỏi tường bên trái tại 0.875 (người chơi LEFT đánh bóng), lại nảy ở bên phải tại thời điểm 1.375 (người chơi RIGHT thứ hai có thể đặt vợt tại điểm va chạm), lại nảy ở bên trái (nơi người chơi LEFT đến vừa kịp lúc để bắt nó — cô ấy đi hết ba đơn vị khoảng cách chính xác trong một giây cần thiết để đến đó) và sau đó chạm tường phải ở vị trí quá xa để người chơi RIGHT đầu tiên có thể tới kịp. Lưu ý rằng người chơi RIGHT thứ hai có thể bắt được bóng, nhưng không được phép làm vậy theo luật. Cũng lưu ý rằng nếu đội RIGHT có thêm một người chơi, cô ấy có thể đánh bóng, và khi đó LEFT sẽ thua — bóng sẽ bay quá cao để người chơi LEFT duy nhất có thể đến kịp lúc.
Nguồn
Google Code Jam 2013, Vòng 2, bài Multiplayer Pong.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.