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.

Ví dụ

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 4

Case #1: LEFT 2
Case #2: DRAW
Case #3: LEFT 3
Case #4: RIGHT 11

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.