Elearning CodePath – CTP Online Judge

Chia Dãy thành Ba Phần Tổng Bằng Nhau

GEN012

🟢 Hard #Prefix Sum #Two Pointers

### 📝 Bài toán

Cho dãy số nguyên $A$ gồm $N$ phần tử được đánh số từ $0$ đến $N-1$: $A = (A_0, A_1, \dots, A_{N-1})$.

Yêu cầu: Tìm hai chỉ số $i$ và $j$ ($0 \le i < j < N$, hoặc $0 \le i < j \le N-1$) sao cho dãy $A$ được chia thành ba mảng con liên tiếp sau đây, và **tổng các phần tử** trong ba mảng con này là **bằng nhau**:

1.  **Phần 1:** $A[0..i]$ (Bao gồm $A_0$ đến $A_i$).
2.  **Phần 2:** $A[i+1..j]$ (Bao gồm $A_{i+1}$ đến $A_j$).
3.  **Phần 3:** $A[j+1..N-1]$ (Bao gồm $A_{j+1}$ đến $A_{N-1}$).

Nếu gọi $S$ là tổng toàn bộ dãy $A$, thì tổng của mỗi phần phải bằng $S/3$.

$sum_{k=0}^{i} A_k = \sum_{k=i+1}^{j} A_k = \sum_{k=j+1}^{N-1} A_k = \frac{S}{3}$

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

* Dòng 1: Ghi số nguyên $N$.
* Dòng 2: Ghi $N$ số nguyên $A_0, A_1, \dots, A_{N-1}$, cách nhau bởi dấu cách.

Giới hạn:
* $N \le 10^6$.
* $|A_i| \le 10^9$.

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

* Kết quả gồm hai chỉ số $i$ và $j$ ($0 \le i < j < N-1$) thỏa mãn yêu cầu. Các chỉ số cách nhau bởi dấu cách.
* Nếu không tồn tại cách chia nào, in ra `-1`.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `5` <br> `1 3 4 0 4` | `1 2` |
| `3` <br> `2 3 4` | `-1` |

Giải thích cho Ví dụ 1: $A = [1, 3, 4, 0, 4]$. Tổng $S=12$. $S/3 = 4$.
* $i=1, j=2$.
    * Phần 1: $A[0..1] = [1, 3]$. Tổng = $4$.
    * Phần 2: $A[2..2] = [4]$. Tổng = $4$.
    * Phần 3: $A[3..4] = [0, 4]$. Tổng = $4$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $30\%$ |
| 2 | $N \le 10^6$ | $70\%$ |

---

✅ Đã AC: 11 / 60 submissions