Điều độ xe buýt

View as PDF

Submit solution

Points: 1.21 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Russian OI
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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_{0}~ 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_{0}~.

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.

Input

  • Dòng thứ nhất chứa ~n~, ~K~, ~S~, ~V_{min}~, ~V_{max}~, ~V_{0}~.
  • 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.

Output

  • 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ủa bạn sẽ được tính là đúng nếu như các số thực được in ra chênh lệch với đáp án không quá ~10^{-4}~

Giới hạn

  • ~k < n < 10000~
  • ~S \leq 10000~
  • ~V_{min} < V_{max} \leq 10000~
  • ~V_{min} \leq V_{0} \leq V_{max}~

Sample Input 1

4 1 60 21 70 60
3

Sample Output 1

0.2041
1 45.5
2 70
4 21

Sample Input 2

4 2 40 30 80 50
2 4

Sample Output 2

0
1 50
3 50

Comments

Please read the guidelines before commenting.


There are no comments at the moment.