Elearning CodePath – CTP Online Judge

Tổng Đoạn Con Bằng Nhau Nhỏ Nhất

TP002

🟢 Easy #General #Binary Search #Two Pointers #Knapsack

### 📌 Thông tin chung

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

Cho dãy số nguyên dương $A = (a_1, a_2, \dots, a_M)$.

Dãy con $A[i..j] = (a_i, a_{i+1}, \dots, a_j)$ được gọi là một đoạn số.
Tổng của đoạn số là $\sum_{k=i}^{j} a_k$.

Dãy $A$ có thể được phân hoạch thành các đoạn con liên tiếp:
$A = (A[1..j_1]), (A[j_1+1..j_2]), \dots, (A[j_{p-1}+1..M])$
với điều kiện các đoạn này có **tổng bằng nhau**, tức là:
$\sum_{k=1}^{j_1} a_k = \sum_{k=j_1+1}^{j_2} a_k = \dots = \sum_{k=j_{p-1}+1}^{M} a_k = S$
(Trong đó $S$ là giá trị tổng của đoạn).

Yêu cầu: Tìm giá trị $S$ nhỏ nhất có thể của một đoạn tổng bằng nhau trong tất cả các cách phân hoạch hợp lệ.

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

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

* Dòng 1: Số nguyên $T$ ($1 \le T \le 1000$) là số lượng bộ test.
* Mỗi bộ test bao gồm:
 * Dòng đầu tiên: Số thứ tự bộ test (Test ID) và số nguyên $M$ ($1 \le M \le 10000$) là số phần tử của dãy.
 * Các dòng tiếp theo: $M$ số nguyên dương của dãy $A$ ($a_i < 20000$), ghi 10 số trên mỗi dòng (dòng cuối có thể ít hơn).

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

Ghi ra file `BCSEQ.OUT`. Với mỗi bộ test, in ra trên một dòng:
$\text{Test ID} \quad \text{Min } S$

---
### 🏷 Ví dụ

| Input | Output |
| :--- | :--- | 
|`3` `1 4` `1 2 3 3` `2 3` `2 1 4` `3 6` `3 1 2 3 1 2` | `1 3` `2 7` `3 3` |

---

---
### 🏷 Subtask

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

---

✅ Đã AC: 1 / 1 submissions