Elearning CodePath – CTP Online Judge

Đoạn con dài nhất có tổng bằng nhau

SUB_LONGEST

🟢 Easy

### 📌 Thông tin chung

-----

### 📝 Bài toán

Cho trước 2 dãy số nguyên $A$ và $B$ đều có $N$ phần tử.
**Yêu cầu:** Hãy chỉ ra một cặp số $i, j$ ($1 \le i \le j \le N$) có khoảng cách xa nhất ($j - i + 1$ lớn nhất) sao cho tổng các phần tử từ $A_i$ đến $A_j$ bằng tổng các phần tử từ $B_i$ đến $B_j$.

Điều kiện cân bằng:
$$\sum_{k=i}^{j} A_k = \sum_{k=i}^{j} B_k$$

-----

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

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

* Dòng 1: Ghi số nguyên dương $N$.
  * Dòng 2: Ghi $N$ số nguyên của dãy $A$: $A_1, A_2, \dots, A_N$.
  * Dòng 3: Ghi $N$ số nguyên của dãy $B$: $B_1, B_2, \dots, B_N$.

**Giới hạn:**

* $N \le 10^5$.
  * $|A_k|, |B_k| \le 10^9$.

-----

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

Ghi ra file `LONGEST.OUT`:

* Một dòng duy nhất ghi 2 số nguyên dương $i$ và $j$ lần lượt là vị trí bắt đầu và kết thúc của dãy tìm được. Nếu có nhiều cặp $i, j$ cùng độ dài tối đa, hãy in ra cặp có $i$ nhỏ nhất.
  * Nếu không tìm thấy dãy nào thỏa mãn thì ghi số 0.

-----

### ✨ Ví dụ

| Input (`LONGEST.INP`) | Output (`LONGEST.OUT`) |
| :--- | :--- |
| `5` <br> `1 3 1 2 2` <br> `7 4 1 1 9` | `2 4` |

**Giải thích:**

* Tại $i=2, j=4$:
      * Tổng dãy $A$ là $3 + 1 + 2 = 6$.
      * Tổng dãy $B$ là $4 + 1 + 1 = 6$.
  * Độ dài là $4 - 2 + 1 = 3$, đây là độ dài lớn nhất tìm được.

-----

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $30\%$ |
| 2 | $N \le 10^5$ | $70\%$ |

✅ Đã AC: 0 / 0 submissions