BOI 2009 - Ngày 1

Một con bọ đang ở trên một cành cây mảnh nằm ngang. Trên cùng cành cây có \(n\) giọt sương, mỗi giọt ban đầu chứa \(m\) đơn vị nước. Tọa độ nguyên của các giọt sương, lấy vị trí ban đầu của con bọ làm gốc, là \(x_1,x_2,\ldots,x_n\).

Mỗi đơn vị thời gian, mỗi giọt sương mất đi một đơn vị nước. Con bọ uống hết lượng nước còn lại trong một giọt ngay khi đến đó; việc uống không tốn thời gian. Trong một đơn vị thời gian, con bọ bò được một đơn vị độ dài.

Hãy tính lượng nước lớn nhất mà con bọ có thể uống.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n\) và \(m\). Mỗi dòng trong \(n\) dòng tiếp theo chứa một tọa độ \(x_i\).

Dữ liệu ra

In ra một số nguyên duy nhất: lượng nước lớn nhất con bọ có thể uống.

Ràng buộc

Các tọa độ đôi một khác nhau.

Phân nhóm

Tài liệu chấm chính thức công bố 15 nhóm test:

1. 3 điểm: \(n\le 3\).
2. 3 điểm: \(n\le 10\).
3. 5 điểm: \(n\le 20\).
4. 5 điểm: \(n\le 25\).
5. 5 điểm: \(n\le 25\).
6. 10 điểm: \(n\le 25\).
7. 7 điểm: \(n\le 60\).
8. 5 điểm: \(n\le 100\).
9. 5 điểm: \(n\le 100\).
10. 5 điểm: \(n\le 100\).
11. 15 điểm: \(n\le 100\).
12. 10 điểm: \(n\le 200\).
13. 10 điểm: \(n\le 250\).
14. 10 điểm: \(n\le 300\).
15. 2 điểm: \(n\le 100\); đáp án bằng \(0\), và có một test với \(n=0\).

Ví dụ

3 15
6
-3
1

25

Trong một nhà máy kẹo có một cỗ máy bí ẩn. Máy có một dãy cửa ra được đánh số từ \(1\) đến \(n\); mỗi viên kẹo rơi ra ngay khi được làm xong. Trước mỗi phiên sản xuất, máy in danh sách cho biết thời điểm và cửa ra của từng viên kẹo.

Chủ nhà máy có thể lắp các xe tự động chạy phía dưới dãy cửa để hứng kẹo. Không viên kẹo nào được phép rơi xuống sàn, nhưng vì vận hành xe rất tốn kém nên cần dùng ít xe nhất có thể. Mỗi xe chạy với vận tốc một khoảng cách giữa hai cửa trong một giây. Trước khi phiên sản xuất bắt đầu, mỗi xe có thể được đặt sẵn tại cửa nơi nó sẽ hứng viên kẹo đầu tiên.

Hãy tìm số xe ít nhất cần dùng và chỉ ra xe nào hứng từng viên kẹo.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), số viên kẹo trong phiên sản xuất. Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số nguyên \(s_i,t_i\): cửa ra và thời điểm của viên kẹo thứ \(i\). Các cặp \((s_i,t_i)\) đôi một khác nhau.

Dữ liệu ra

Dòng đầu chứa số nguyên \(w\), số xe ít nhất cần dùng. Các xe được đánh số từ \(1\) đến \(w\).

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(s_j,t_j,w(j)\), cho biết xe \(w(j)\) sẽ ở cửa \(s_j\) tại thời điểm \(t_j\) để hứng viên kẹo đó. Mỗi cặp cửa–thời điểm trong dữ liệu vào phải xuất hiện đúng một lần; các dòng có thể được in theo thứ tự bất kỳ.

Nếu có nhiều phương án, bạn có thể in ra bất kỳ phương án nào.

Ràng buộc

Phân nhóm

• 20% số điểm: \(n\le 85\) và số xe tối ưu \(w\le 4\).
• 60% số điểm: \(n\le 8\,000\).

Ví dụ

5
1 1
2 3
1 5
3 4
2 6

2
1 1 1
2 3 1
1 5 2
3 4 1
2 6 2

Tàu điện ngầm Stockholm có nhiều tuyến. Ta xét một tuyến gồm hai đường ray song song nối với nhau ở hai đầu. Trên đường ray phía trên, tàu chạy từ phải sang trái; trên đường ray phía dưới, tàu chạy từ trái sang phải. Khi đến đầu đường ray, tàu lập tức chuyển sang đường ray kia và đổi hướng; thao tác này không tốn thời gian.

Trong điều kiện bình thường, các tàu chạy liên tục với vận tốc một đơn vị độ dài trong một đơn vị thời gian và được phân bố đều: tại một vị trí bất kỳ trên đường ray, tàu xuất hiện theo chu kỳ. Thời gian dừng để đón khách được xem là không đáng kể.

Sau một lỗi tín hiệu, các tàu bị phân bố ngẫu nhiên dọc tuyến. Bạn được phép ra lệnh cho tàu tạm dừng và/hoặc đổi hướng tại bất kỳ vị trí nào. Khi đổi hướng, tàu chuyển sang đường ray kia.

Hãy tính thời gian ngắn nhất để các tàu lại được phân bố đều.

Trong hình, mỗi đường ray dài \(100\). Ở cấu hình trên, các tàu lần lượt ở vị trí \(5\) (sang phải), \(35\) (sang trái), \(46\) (sang trái), \(75\) (sang trái) và \(85\) (sang phải). Có thể cho tàu tại \(46\) đi một đơn vị sang trái rồi đổi hướng để đạt cấu hình đều trong một đơn vị thời gian, nhưng đây chưa phải phương án tối ưu; xem Ví dụ 1.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(m,n\): chiều dài mỗi đường ray và số tàu. Mỗi dòng trong \(n\) dòng tiếp theo chứa một số nguyên \(x_i\) và một ký tự chỉ hướng, L nếu tàu đang đi sang trái hoặc R nếu tàu đang đi sang phải.

Dữ liệu ra

In ra thời gian ngắn nhất để các tàu được phân bố đều. Sai số tuyệt đối không được vượt quá \(10^{-6}\).

Ràng buộc

Phân nhóm

• 50% số điểm: \(n\le 200\).

Ví dụ

100 5
5 R
35 L
46 L
75 L
85 R

0.5

100 8
9 L
15 R
41 L
33 L
81 R
33 R
100 L
97 R

15.500000