Ở vùng nông thôn có một con đường dài và thẳng được gọi là Con đường Lúa. Dọc theo con đường có \(R\) cánh đồng lúa. Mỗi cánh đồng nằm tại một tọa độ nguyên từ \(1\) đến \(L\), kể cả hai đầu. Các cánh đồng được cho theo thứ tự tọa độ không giảm. Cụ thể, với \(0 \le i < R\), cánh đồng \(i\) nằm tại tọa độ \(X[i]\), và:

Nhiều cánh đồng có thể cùng nằm tại một tọa độ.

Chúng ta dự định xây dựng một kho lúa duy nhất để tập trung và cất giữ nhiều lúa thu hoạch nhất có thể. Kho phải nằm tại một tọa độ nguyên từ \(1\) đến \(L\), kể cả hai đầu. Có thể đặt kho ở bất kỳ vị trí nào trong phạm vi này, kể cả vị trí đã có một hoặc nhiều cánh đồng.

Mỗi cánh đồng thu hoạch được đúng một xe tải lúa trong mỗi vụ. Để đưa lúa về kho, thành phố phải thuê tài xế xe tải. Chi phí vận chuyển một xe tải lúa là \(1\) Baht cho mỗi đơn vị quãng đường từ cánh đồng đến kho. Nói cách khác, nếu kho ở tọa độ \(h\), chi phí chở lúa từ cánh đồng \(i\) về kho là \(|X[i]-h|\) Baht.

Ngân sách của vụ mùa này hạn hẹp: chúng ta chỉ được chi tối đa \(B\) Baht cho việc vận chuyển. Hãy chọn vị trí kho sao cho có thể tập trung được nhiều lúa nhất trong phạm vi ngân sách.

Yêu cầu

Cài đặt hàm sau, được khai báo trong ricehub.h:

int besthub(int R, int L, int X[], long long B);

• R: số cánh đồng, được đánh số từ \(0\) đến \(R-1\).
• L: tọa độ lớn nhất.
• X: mảng một chiều các số nguyên được sắp xếp theo thứ tự không giảm. Với \(0 \le i < R\), cánh đồng \(i\) nằm tại tọa độ X[i].
• B: ngân sách vận chuyển.

Hàm phải xác định cách đặt kho tối ưu và trả về số xe tải lúa lớn nhất có thể vận chuyển về kho mà tổng chi phí không vượt quá \(B\). Chỉ trả về số xe tải, không trả về tọa độ kho. Không có thủ tục gọi lại để báo đáp án; trình chấm sử dụng giá trị trả về của besthub.

Tổng chi phí vận chuyển có thể rất lớn. Ngân sách được cho bằng số nguyên \(64\) bit; nên dùng số nguyên \(64\) bit trong các phép tính. Trong C/C++, dùng kiểu long long; trong Pascal, dùng kiểu Int64.

Ví dụ

5 20 6
1
2
10
12
14
3

Correct.

    ![Vị trí các cánh đồng và một cách đặt kho lúa tối ưu](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_6da42cbf.png)

    Có nhiều vị trí tối ưu để đặt kho: có thể đặt tại bất kỳ tọa độ nguyên nào từ $10$ đến $14$, kể cả hai đầu. Hình trên minh họa một vị trí như vậy. Khi đó có thể vận chuyển lúa từ các cánh đồng ở tọa độ $10$, $12$ và $14$ về kho. Với mỗi vị trí tối ưu, tổng chi phí vận chuyển số lúa này không quá $6$ Baht. Không có vị trí nào cho phép thu gom lúa từ hơn ba cánh đồng, nên phương án này là tối ưu và `besthub` phải trả về `3`.

Ràng buộc

Trong mọi nhóm, \(1 \le X[0] \le \cdots \le X[R-1] \le L\). Nhiều cánh đồng có thể cùng tọa độ, trừ khi nhóm quy định khác.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 1 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là ricehub/. Thí sinh cài đặt ricehub.c, ricehub.cpp hoặc ricehub.pas. Giao diện của thí sinh là ricehub.h hoặc ricehub.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): ba số nguyên \(R\), \(L\) và \(B\).
• Các dòng \(2\) đến \(R+1\): vị trí các cánh đồng. Dòng \(i+2\) chứa X[i], với \(0 \le i < R\).
• Dòng \(R+2\): đáp án mong đợi.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Rice Hub, bản tiếng Anh 1.4: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.