Elearning CodePath – CTP Online Judge

PS_SubGivenSum

PS_SUBGIVENSUM

🟢 Medium #Two Pointers #Backtracking #Prefix Sum #Sliding Window

## 💻 Đề Bài: Đoạn con có tổng bằng S (PS_SubGivenSum)

### 📌 **Thông tin chung**

---

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

Cho một dãy số nguyên dương $A$ gồm $N$ phần tử. Hãy viết chương trình tìm vị trí $i, j$ ($1 \le i \le j \le N$) sao cho tổng các phần tử từ $A_i$ đến $A_j$ bằng $S$.

Ký hiệu toán học:
$$\sum_{k=i}^{j} A_k = S$$

Nếu có nhiều vị trí $i, j$ thỏa mãn, in ra cặp $(i, j)$ **đầu tiên** tìm được. Nếu không tìm thấy, in $-1$.

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

Dữ liệu vào từ file `PS_SubGivenSum.inp` gồm 2 dòng:

* **Dòng 1:** Hai số nguyên $N$ và $S$ cách nhau một khoảng trắng.
* **Dòng 2:** Dãy số nguyên $A$ cách nhau một khoảng trắng.

**Ràng buộc:**
$$1 \le N \le 10^6, \quad 0 \le S \le 10^9$$
$$0 \le A[i] \le 10^3$$

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

Ghi ra file `PS_SubGivenSum.out` hai số $i, j$ cách nhau một khoảng trắng. Nếu không tìm thấy in $-1$.

### ✨ **Ví dụ**

| Input (`PS_SubGivenSum.inp`) | Output (`PS_SubGivenSum.out`) |
| :--- | :--- |
| **5 12** | **2 4** |
| 1 5 6 1 4 | |
| **Giải thích:** $A[2] + A[3] + A[4] = 5 + 6 + 1 = 12$. | |
| **3 10** | **-1** |
| 2 3 4 | |

---

### 💡 **Gợi ý hướng giải ngắn gọn**

#### **Subtask 1: $O(N^2)$**

* **Ràng buộc:** $1 \le N \le 10^3$.
* **Thuật toán:** **Vét cạn (Brute Force)**.

#### **Subtask 2: $O(N)$ tối ưu**

* **Ràng buộc:** $1 \le N \le 10^6$.
* **Thuật toán:** **Kỹ thuật Cửa sổ trượt (Sliding Window)**.  hoặc **Prefix Sum):**

✅ Đã AC: 1 / 13 submissions