💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
PS_SubGivenSum
PS_SUBGIVENSUM
## 💻 Đề Bài: Đoạn con có tổng bằng S (PS_SubGivenSum) ### 📌 **Thông tin chung** | Mục | Chi tiết | | :--- | :--- | | **Tệp Input** | `PS_SubGivenSum.inp` | | **Tệp Output** | `PS_SubGivenSum.out` | | **Điểm** | 100 | --- ### 📝 **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: 5 / 16 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng