Elearning CodePath – CTP Online Judge

Tìm Cặp Số

GEN028

🟢 Medium #Math

| Mục | Chi tiết |
| :--- | :--- |
| **Tên Bài Toán** | Tìm cặp số |
| **Nguồn** | Kì Thi Chọn HSG Thành Phố Cấp THPT năm 2025-2026 |
| **Tên File Input** |  |
| **Tên File Output** ||

---

### 📝 Bài toán

Cho số nguyên dương $S$ và ma trận $A$ có $m$ hàng, $n$ cột. Ô giao giữa hàng $i$ $(i = 1..m)$ và cột $j$ $(j = 1..n)$ có số nguyên dương $a_{ij}$ $(a_{ij} \le 10^9)$.

**Yêu cầu:** Tìm tổng lớn nhất của 2 phần tử ở 2 vị trí khác nhau trong ma trận $A$ sao cho tổng này không lớn hơn số nguyên dương $S$.

---

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

Vào từ file văn bản có thông tin sau:
* **Dòng đầu tiên** có 3 số nguyên dương $m, n, S$ $(m, n \le 10^2; S \le 2 \times 10^9)$.
* **$m$ dòng tiếp theo**, mỗi dòng có $n$ số nguyên dương không vượt quá $10^9$.

Các số trên cùng một dòng trong file dữ liệu được viết cách nhau bởi dấu cách trống.

---

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

Ghi ra file kết quả một dòng là tổng lớn nhất tìm được theo yêu cầu đề bài. Nếu không tìm được 2 phần tử thỏa yêu cầu thì in ra $-1$.

---

### ✨ Ví dụ

| DỮ LIỆU VÀO | KẾT QUẢ RA |
| :---: | :---: |
| `1 4 17` `1 7 9 11` | `16` |
| `2 4 7` `1 2 2 3` `3 3 7 2` | `6` |
| `3 4 10` `6 7 8 9` `5 6 7 8` `9 8 8 7` | `-1` |

**Giải thích Ví dụ:**

**Ví dụ 1:** Ma trận $1 \times 4$: `[9, 7, 11]`
* Tổng lớn nhất $\le 17$: $9 + 7 = 16$ ✓
* Các cặp khác: $9 + 11 = 20 > 17$ ✗, $7 + 11 = 18 > 17$ ✗
* **Kết quả:** $16$

**Ví dụ 2:** Ma trận $2 \times 4$:

✅ Đã AC: 1 / 3 submissions