Chiếc xe của bạn đã hết xăng, và bạn muốn về nhà nhanh nhất có thể! May mắn thay, nhà của bạn nằm ở chân đồi và bạn (cùng chiếc xe) đang ở trên đỉnh đồi. Không may là có một chiếc xe khác đang ở phía trước bạn, và bạn không thể vượt qua nó. May mắn thay, phanh của bạn vẫn hoạt động và chúng rất mạnh mẽ.

Bạn bắt đầu tại đỉnh đồi với vận tốc \(0\) m/s tại thời điểm \(0\) giây. Trọng lực kéo xe của bạn xuống đồi với một gia tốc không đổi. Tại bất kỳ thời điểm nào, bạn có thể sử dụng phanh để giảm tốc độ, hoặc tạm thời giảm gia tốc của mình đi bất kỳ lượng nào.

Bạn có thể về nhà nhanh nhất là bao lâu nếu bạn sử dụng phanh theo cách tối ưu nhất?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Dòng đầu tiên của mỗi bộ thử nghiệm chứa ba số cách nhau bởi dấu cách: một số thực \(D\), khoảng cách tính bằng mét đến nhà bạn ở chân đồi; và hai số nguyên, \(N\) và \(A\). Khoảng cách \(D\) sẽ được cho với chính xác 6 chữ số thập phân.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số thực cách nhau bởi dấu cách: thời điểm \(t_i\) tính bằng giây, và vị trí \(x_i\) tính bằng mét. Các giá trị \(t_i\) và \(x_i\) sẽ được cho với chính xác 6 chữ số thập phân.

Một dòng tiếp theo chứa \(A\) số thực cách nhau bởi dấu cách \(a_i\), là các gia tốc tính bằng \(m/s^2\). Các gia tốc sẽ được cho với chính xác 2 chữ số thập phân.

Vị trí của chiếc xe kia được xác định bởi các cặp \((t_i, x_i)\). Vị trí của chiếc xe đó tại thời điểm \(t_i\) giây là \(x_i\) mét tính từ đỉnh đồi (tức là vị trí ban đầu của bạn). Chiếc xe đó di chuyển với vận tốc không đổi giữa thời điểm \(t_i\) và \(t_{i+1}\). Các vị trí và thời gian đều được cho theo thứ tự tăng dần, với \(t_0=0\).

Ví dụ, nếu \(t_5=10, x_5=20, t_6=20, x_6=40\), thì \(10\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(20\) mét; \(15\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(30\) mét; và \(20\) giây sau khi bắt đầu, chiếc xe kia cách đỉnh đồi \(40\) mét.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, in ra một dòng chứa "Case #c:", trong đó c là số thứ tự bộ thử nghiệm (bắt đầu từ 1). Sau đó in ra \(A\) dòng, dòng thứ \(i\) chứa số giây tối thiểu để bạn về đến nhà nếu gia tốc xuống đồi do trọng lực của bạn là \(a_i\), và bạn sử dụng phanh theo cách tối ưu nhất. Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-6}\) so với đáp án đúng sẽ được chấp nhận. Không nên có dòng trống trong đầu ra.

Ghi chú

• Vị trí và Gia tốc: Một vật với gia tốc không đổi \(a\) \(m/s^2\) và vận tốc bắt đầu \(v_0\) \(m/s\) sẽ di chuyển một quãng đường \(v_0 \cdot t + 0.5 \cdot a \cdot t^2\) sau \(t\) giây.
• Khoảng cách trên dốc: Tất cả các khoảng cách và gia tốc được cho đối với đường thẳng xuống đồi. Chúng không phải là, ví dụ, khoảng cách nằm ngang; vì vậy nếu xe của bạn đang tăng tốc với \(2\) \(m/s^2\) với vận tốc ban đầu \(0\) \(m/s\), và chiếc xe kia đang dừng ở \(x=1\), sẽ mất đúng \(1\) giây để bắt kịp chiếc xe kia.
• Chiếc xe kia: Bạn không bao giờ được vượt qua chiếc xe kia, nghĩa là tại không có thời điểm nào khoảng cách xuống đồi của bạn lớn hơn khoảng cách của chiếc xe kia. Nó có thể bằng nhau. Các xe nên được coi là các chất điểm.
• Giá trị đầu ra: Bạn có thể in bao nhiêu chữ số thập phân tùy thích. Chúng tôi sẽ đọc và so sánh câu trả lời của bạn với đáp án của chúng tôi bằng ngưỡng sai số \(10^{-6}\). Vì vậy \(25, 25.0\) và \(25.000000\) là giống nhau. Các chữ số \(0\) vô nghĩa sau dấu phẩy thập phân không quan trọng.

Ràng buộc

• \(1 \le T \le 20\).
• \(1.0 \le D \le 10^4\).
• \(1.0 \le a_i \le 9.81\).
• \(0.0 \le t_i \le 10^5\).
• \(0.0 \le x_i \le 10^5\).
• \(t_i < t_{i+1}\).
• \(x_i < x_{i+1}\).
• \(t_0 = 0\).
• \(x_{N-1} \ge D\).

Phân nhóm

• Test set 1 (Visible Verdict):

  • \(1 \le N \le 2\).
  • \(1 \le A \le 10\).

  • Test set 2 (Hidden Verdict):

  • \(1 \le N \le 2000\).

  • \(1 \le A \le 250\).

Đ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ụ

3
1000.000000 2 3
0.000000 20.500000
25.000000 1000.000000
1.00 5.00 9.81
50.000000 2 2
0.000000 0.000000
100000.000000 100.000000
1.00 1.01
10000.000000 3 1
0.000000 0.000000
10000.000000 0.100000
10000.100000 100000.000000
1.00

Case #1:
44.7213595
25.000000
25.0
Case #2:
50000.0
50000.0
Case #3:
10140.974143

Nguồn

Google Code Jam 2012, Vòng 1C, bài Out of Gas.

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