Cruise control (kiểm soát hành trình) là một hệ thống cho phép xe ô tô chạy ở tốc độ không đổi, trong khi người lái chỉ điều khiển vô lăng. Tất nhiên, người lái có thể tắt hệ thống kiểm soát hành trình để tránh va chạm.

Trong bài toán này, chúng ta sẽ xem xét một con đường một chiều có hai làn xe và \(N\) chiếc xe đang sử dụng hệ thống kiểm soát hành trình trên đường. Mỗi chiếc xe dài 5 mét và chạy với một tốc độ không đổi nào đó. Một chiếc xe có thể chuyển làn bất cứ lúc nào nếu việc đó không gây ra va chạm với xe khác (tiếp xúc nhau không được tính là va chạm). Giả sử việc chuyển làn diễn ra tức thời và chỉ đơn giản là khiến chiếc xe chuyển sang làn kia. Chúng ta quan tâm đến việc liệu có người lái nào cuối cùng sẽ phải tắt hệ thống kiểm soát hành trình để tránh va chạm hay không, hoặc liệu tất cả họ có thể lái xe mãi mãi (có thể chuyển làn, nhưng ở tốc độ không đổi) mà không xảy ra va chạm hay không. Lưu ý rằng mặc dù việc chuyển làn là tức thời, hai chiếc xe đang chạy song song không thể đổi chỗ cho nhau bằng cách chuyển làn cùng một lúc.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bắt đầu bằng số \(N\). \(N\) dòng tiếp theo, mỗi dòng mô tả một chiếc xe duy nhất. Mỗi dòng chứa một ký tự \(C_i\) (biểu thị xe ban đầu ở làn trái hay làn phải), hai số nguyên mô tả tốc độ \(S_i\) của xe (tính bằng mét trên giây) và vị trí ban đầu \(P_i\) của xe (tính bằng mét), biểu thị khoảng cách giữa đuôi xe và một vạch cố định ngang qua đường. Tất cả các xe đều đang di chuyển ra xa vạch này và không có xe nào ở phía sau vạch.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy 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à từ "Possible" (trong ngoặc kép chỉ để làm rõ), nếu các xe có thể lái ở tốc độ không đổi đã cho mãi mãi, hoặc số giây tối đa chúng có thể lái trước khi ai đó phải thay đổi tốc độ để tránh va chạm. Các câu trả lời chính xác trong khoảng sai số tuyệt đối hoặc tương đối \(10^{-5}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 30\).
• \(1 \le S_i \le 1000\).
• \(0 \le P_i \le 10000\).
• Mỗi ký tự \(C_i\) sẽ là L (biểu thị làn trái) hoặc R (biểu thị làn phải).
• Ban đầu, vị trí của các xe được sắp xếp sao cho chúng không va chạm, nghĩa là nếu hai xe \(i\) và \(j\) có cùng làn xuất phát ban đầu (\(C_i = C_j\)), thì \(|P_i - P_j| \ge 5\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 6\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N \le 50\).

Đ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
2
L 5 10
L 100 0
3
L 100 0
R 100 0
L 50 505
6
L 30 0
R 30 2
L 10 39
R 10 42
L 25 13
L 15 29
4
L 4 0
L 2 29
L 1 35
L 1 44

Case #1: Possible
Case #2: 10.0
Case #3: 1.4
Case #4: 12.0

Nguồn

Google Code Jam 2012, Vòng 1A, bài Cruise Control.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.