Rừng Dừa Bảy Mẫu

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 0.5s
Bộ nhớ: 256M

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Go, Pascal

Nhân dịp nghỉ lễ Giỗ Tổ Hùng Vương, Amousvanhthanhthien cùng nhóm bạn đã lên kế hoạch tham quan Rừng Dừa Bảy Mẫu ở Hội An. Đến với rừng dừa, du khách sẽ được di chuyển trên sông bằng thúng để tham quan cảnh đẹp sông nước cùng những màn biểu diễn múa thúng thú vị.

Để khách tham quan có thể chụp những bức ảnh check-in đẹp nhất, nhà bè cung cấp cho du khách các tấm ván dài đặt lên những khóm gốc dừa để có thể đứng chụp hình. Có \(n\) khóm dừa được xếp thẳng hàng có độ cao bằng nhau và cách đều nhau. Khóm dừa thứ \(i\) có sức chịu tải là \(c_i\). Tổng khối lượng của cả nhóm bạn là \(M\), do đó cần một tấm ván gỗ đặt lên \(k\) khóm dừa liên tiếp sao cho tổng sức chịu tải của chúng \(\geq M\).

Là một người yêu thích chụp hình, vanhthanhthien muốn được chụp ảnh với tất cả mọi góc nhìn của cảnh quan nơi đây. Nhưng với kinh nghiệm của mình, Amous biết nếu sử dụng tấm ván càng dài sẽ khiến việc đứng trên đó rất bấp bênh, và có thể bị gãy. Muốn cuộc đi chơi được an toàn đồng thời không bị vanhthanhthien giận, Amous quyết định sẽ chọn một tấm ván với chiều dài nhỏ nhất có thể (chiều dài tấm ván được tính bằng số khóm dừa mà tấm ván đó có thể đặt lên) sao cho dù đặt tấm ván ở vị trí nào thì tổng sức chịu của \(k\) gốc dừa ở dưới nó luôn \(\geq M\).

Trong chuyến đi du lịch về miền sông nước của mình, Amous không mang theo laptop để lập trình giải toán, vì vậy anh ấy quyết định đăng lên Facebook để tìm kiếm sự giúp đỡ từ các bạn học sinh giỏi Tin tỉnh Quảng Nam. Hãy giúp Amousvanhthanhthien có những bức ảnh kỷ niệm đẹp nhất nhé! Dữ liệu nhập vào đảm bảo tổng sức chịu tải của tất cả \(n\) khóm dừa luôn \(\geq M\).

Input

  • Dòng đầu tiên gồm hai số nguyên dương \(n,\ M\) lần lượt là số khóm dừa và tổng khối lượng của nhóm bạn.
  • Dòng thứ hai gồm \(n\) số nguyên dương \(c_i\) thế hiện sức chịu tải của từng khóm dừa.

Output

  • In ra kích thước \(k\) bé nhất (\(k\geq1\)) sao cho dù đặt tấm ván với kích thước đó ở bất cứ vị trí nào thì tổng sức chịu tải của các khóm dừa dưới nó luôn \(\geq M\).

Ví dụ

Sample input
5 7
4 2 3 5 1
Sample output
3
Notes

Vì các đoạn con liên tiếp kích thước \(3\): \([4,\ 2,\ 3],\ [2,\ 3,\ 5],\ [3,\ 5,\ 1]\) đều có tổng lớn hơn \(7\).

Ràng buộc

  • \(c_i,\ M\leq10^9,\ \forall i=[1..n]\);
  • Có \(80\%\) số test tương ứng với \(80\%\) số điểm của bài toán có \(n\leq10^3\);
  • \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm của bài toán có \(n\leq10^5\).