TS10 Sóc Trăng 2025 - Mua sách
Xem dạng PDFAn 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, \dots, A_N~ tương ứng với số tiền tiết kiệm của ngày thứ ~1, 2, \dots, 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, \dots, 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.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~A_1 = A_2 = \dots = A_N~. |
| 2 | ~30\%~ | ~A_1 \ge A_2 \ge \dots \ge A_N~. |
| 3 | ~30\%~ | ~1 \le N \le 1000~. |
| 4 | ~20\%~ | Không có giới hạn gì thêm. |
Sample Input 1
6 8
2 5 4 1 3 3
Sample Output 1
2
Sample Input 2
6 100
2 3 1 4 4 3
Sample Output 2
0
Notes
Trong ví dụ thứ nhất, 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.
Trong ví dụ thứ hai, 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.
Bình luận
Bài náy khi chạy báo lỗi chương trình dù kiểm tra không có lỗi n,k=map(int,input().split()) a=list(map(int,input().split())) l=0 s=0 d=n+1 for r in range(n): s=s+a[r] while s>=k: d=min(d,r-l+1) s=s-a[l] l=l+1 if d==n+1: print(0) else: print(d)