Giải bài trực tuyến

Có n xe buýt chạy trên tuyến là một đường vòng khép kín có độ dài S. Các xe buýt được đánh số từ 1 đến n theo thứ tự nối đuôi nhau trên tuyến đường. Xe số n chạy sau xe số 1.

Các xe chạy cùng với vận tốc V₀ và khoảng cách giữa hai xe liên tiếp là như nhau.

Có k xe buýt đồng thời rời khỏi tuyến. Để trở lại khoảng cách đều nhau giữa các xe, cần phải có một khoảng thời gian t và một số xe cần phải thay đổi tốc độ. Trong khoảng thời gian này, các xe phải chạy với tốc độ không đổi trong khoảng [V_min, V_max] theo lệnh của trung tâm.

Hết khoảng thời gian t các xe lại quay về vận tốc V₀.

Yêu cầu: giúp trung tâm tìm khoảng thời gian bé nhất T_min để khôi phục sự cân bằng khoảng cách giữa hai xe liên tiếp trên tuyến và vận tốc của mỗi xe trong khoảng thời gian ấy. Biết rằng, trong quá trình điều chỉnh, không có xe nào vượt qua xe trước mặt.

Dữ liệu vào

• Dòng thứ nhất chứa N, K ,S , V_min, V_max, V₀.
• Dòng thứ hai chứa K số nguyên dương được ghi theo thứ tự tăng dần là chỉ số của các xe rời khỏi tuyến.
• Các dữ liệu trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết qủa

• Dòng đầu tiên: T_min
• Mỗi một trong số N-K dòng tiếp theo chứa hai số, số thứ nhất là chỉ số của xe buýt, số thứ hai là tốc độ của nó trong khoảng thời gian T_min. Các dòng này phải sắp xếp theo thứ tự tăng dần của chỉ số xe buýt.

Kết quả cần được in ra với độ chính xác cao (khoảng 6 chữ số thập phân).

Giới hạn

• K < N < 10000
• S ≤ 10000
• V_min < V_max ≤ 10000
• V_min ≤ V₀ ≤ V_max

Ví dụ

Dữ liệu mẫu
4 1 60 21 70 60
3

Kết qủa
0.2041
1 45.5
2 70
4 21

Dữ liệu mẫu
4 2 40 30 80 50
2 4

Kết qủa
0
1 50
3 50