Elearning CodePath – CTP Online Judge

Minimum Length Subarray with Sum

GEN001

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy số nguyên dương $A = (a_1, a_2, \dots, a_N)$ và một số nguyên dương $S$.

Một dãy con liên tiếp của dãy số có dạng $A[i..j] = (a_i, a_{i+1}, \dots, a_j)$, với $1 \le i \le j \le N$.

* **Tổng** của dãy con là $Sum(i, j) = \sum_{k=i}^{j} a_k$.
* **Độ dài** của dãy con là $j - i + 1$.

Yêu cầu: Tìm độ dài nhỏ nhất của dãy con liên tiếp $A[i..j]$ sao cho tổng của nó lớn hơn hoặc bằng $S$.
${Min Length} = \min \{ j - i + 1 \mid 1 \le i \le j \le N, \sum_{k=i}^{j} a_k \ge S \}$
Nếu không có dãy con nào thỏa mãn điều kiện tổng, kết quả là $0$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `SUB.INP`:

* Dòng 1: Ghi hai số nguyên $N$ và $S$.
* Dòng 2: Ghi $N$ số nguyên $a_1, a_2, \dots, a_N$ cách nhau bởi dấu cách.

Giới hạn:
* $10 < N < 100,000$.
* $1 \le a_i \le 10,000$.
* $1 \le S < 100,000,000$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `SUB.OUT` một số nguyên duy nhất là độ dài nhỏ nhất tìm được. Nếu không có dãy con nào thỏa mãn, ghi $0$.

---

### 🏷Ví dụ

| Input | Output | Giải thích |
|---|---|---|
| 10 15 5 1 3 5 10 7 4 9 2 8 | 2 | Dãy con ngắn nhất có tổng lớn hơn hoặc bằng 15 là $(10, 7)$, có tổng bằng 17 và độ dài bằng 2. |
| 5 11 1 2 3 4 5 | 3 | Dãy con ngắn nhất thỏa mãn là $(3, 4, 5)$, có tổng bằng 12 và độ dài bằng 3. |
| 6 100 1 2 3 4 5 6 | 0 | Tổng của toàn bộ dãy là 21, nhỏ hơn 100 nên không tồn tại dãy con nào thỏa mãn. |
| 8 7 2 1 1 1 1 1 1 6 | 2 | Dãy con ngắn nhất thỏa mãn là $(1, 6)$, có tổng bằng 7 và độ dài bằng 2. |
| 7 9 9 1 1 1 1 1 1 | 1 | Dãy con chỉ gồm phần tử đầu tiên $(9)$ đã có tổng bằng 9 nên đáp án là 1. |

---
### 🏷 Phân Subtask

Do $N$ có thể lên đến $10^5$, thuật toán $O(N)$ là bắt buộc. Vì $a_i$ là số nguyên dương, kỹ thuật Cửa sổ trượt là áp dụng hoàn hảo.

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 100,000$ | $60\%$ |

---

✅ Đã AC: 13 / 36 submissions