[Sóc Trăng - TS10 - 2025] Bài 3: Mua sách

Xem dạng PDF

Gửi bài giải

Điểm: 5,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

An muốn mua 1 bộ sách quý với giá là ~X~ đồng. An quyết định tiết kiệm tiền mỗi ngày và ghi lại số tiền tiết kiệm được trong ~N~ ngày liên tiếp, tạo thành dãy số nguyên ~A_1, A_2, ..., A_N~ tương ứng với số tiền tiết kiệm của ngày thứ ~1, 2, ..., N~. An muốn biết: "Trong giai đoạn liên tiếp ngắn nhất (liên tiếp các ngày), An có thể tiết kiệm được ít nhất ~X~ đồng là bao nhiêu ngày".

Yêu cầu: Bạn hãy giúp An tìm số ngày liên tiếp ngắn nhất để tiết kiệm được ít nhất là ~X~ đồng.

INPUT

Dòng đầu tiên chứa 2 số nguyên ~N~ và ~X~ (~1 \le N \le 10^5, 1 \le X \le 10^9~) Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~1 \le A_i \le 10^5~).

OUTPUT

Gồm 1 số nguyên duy nhất cho biết số ngày liên tiếp ngắn nhất để tiết kiệm được ít nhất là ~X~ đồng, ngược lại nếu không thể tiết kiệm được số tiền ít nhất ~X~ đồng thì in ra ~0~.

SAMPLE INPUT 1

6 8
2 5 4 1 3 3

SAMPLE OUTPUT 1

2

Giải thích: Giá bộ sách là ~8~ đồng. Trong 2 ngày liên tiếp (ngày thứ ~2~ và ~3~), An tiết kiệm được ~5 + 4 = 9~ đồng. Đây là số ngày liên tiếp ngắn nhất An tiết kiệm đủ số tiền mua sách.

SAMPLE INPUT 2

6 100
2 3 1 4 4 3

SAMPLE OUTPUT 2

0

Giải thích: Giá bộ sách là ~100~ đồng. Sau ~6~ ngày, tổng số tiền tiết kiệm là ~17~ đồng, vẫn chưa đủ tiền mua sách.

SUBTASKS

Subtask Điểm Ràng buộc
1 ~20\%~ ~A_1 = A_2 = ... = A_N~.
2 ~30\%~ ~A_1 \ge A_2 \ge ... \ge A_N~.
3 ~30\%~ ~1 \le N \le 1000~.
4 ~20\%~ Không có ràng buộc gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.