[HSG-QH_TK_NA_24] Phát quà Noel
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python
Nhân dịp lễ Giáng Sinh 2024 sắp tới, trường tổ chức phát quá cho các bạn nhỏ. Có ~N~ món quà được xếp thành hàng ngang, mỗi món quà đều có khối lượng cho trước. Tí là một đứa trẻ không như nhiều đứa trẻ khác, Tí chỉ muốn chọn ít phần quà càng tốt miễn là tổng các phần quà này lớn hơn hoặc bằng ~S~. Tí chỉ có thể lựa chọn các phần quà đặt cạnh nhau.
Yêu cầu
Bạn hãy xác định xem Tí có thể chọn tối thiểu bao nhiêu phần quà để tổng khối lượng của các phần quà lớn hơn hoặc bằng ~S~.
Dữ liệu đầu vào
Gồm hai dòng:
- Dòng 1: Số nguyên dương ~N~ và ~S~ ~(1 \le N \le 10^6,\ 1 \le S \le 10^9)~.
- Dòng 2: Chứa ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ ~(a_i \le 10^6)~.
Dữ liệu đầu ra
Gồm một số nguyên là kết quả tìm được.
Ràng buộc dữ liệu
- 60% số test đầu tiên ~n \le 10^3~.
- 40% số test cuối cùng không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
INPUT
10 17
5 1 3 5 10 7 4 9 2 8
OUTPUT
2
Bình luận
hi ae