DUAXE - Đua xe
Giới hạn- Thời gian: 0.139s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trong 1 cuộc đua xe phân khối lớn, đường đua gồm N đoạn đường. Điểm chuyển tiếp giữa 2 đoạn đường liên tiếp gọi là các nút, có tất cả N-1 nút như thế. Rõ ràng ai cũng muốn đi với tốc độ cao nhất để về đíhc nhanh nhất, tuy nhiên có các ràng buộc sau:
- Vận tốc tại vị trí xuất phát và về đích phải bằng 0 (tức là xe phải dừng ở đúng đích)
- Xe chỉ có thể tăng tốc ở mức gia tốc tối đa A (m/s^2)
- Xe chỉ có thể giảm tốc (phanh) ở mức gia tốc tối đa B (m/s^2) Điều này có nghĩa là tại mỗi thời điểm, gia tốc a của xe phải thoả mãn -B<=a<=A
- Xe không bị giới hạn vận tốc trên đường nhưng khi qua các nút chuyển tiếp, để đảm bảo an toàn, lái xe không được phép vượt quá một vận tốc V (m/s) nào đó, tuỳ thuộc vào từng nút.
Giả thiết vận tốc của xe không bị giới hạn nào khác ngoài các ràng buộc trên. Hãy tính thời gian ngắn nhất để xe có thể về đích.
Input
Dữ liệu nhập vào có khuôn dạng như sau:
- Dòng 1 ghi 3 số nguyên dương N, A, B (N <= 1000)
- N dòng tiếp, mỗi dòng mô tả 1 chặng đường, gồm 2 số nguyên dương là độ dài của chặng và vận tốc giới hạn tại điểm nút cuối chặng. Chú ý rằng điểm xuất phát là điểm đầu của chặng 1 và điểm đích là điểm cuối chặng N
Output
Thời gian ngắn nhất (đơn vị giây) để xe có thể đến đích. Kết quả ghi dưới dạng số thực chính xác đến 3 chữ số thập phân. Bài của bạn sẽ được coi là Accept nếu kết quả sai lệch không quá 0.01 so với kết quả của file đáp án.
Example
Input: 1 1 1 100 0 Output: 20.000
Input: 2 1 1 10 10 90 0 Output: 20.000
- Người up: huy391992