Elearning CodePath – CTP Online Judge

Tìm cặp có tổng bằng K

TP_Find_2

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho dãy số nguyên `A` gồm `N` phần tử và một số nguyên `K`.  
Hãy viết chương trình tìm **một cặp phần tử** `X, Y` trong dãy `A` sao cho `X + Y = K`.

**Quy tắc chọn cặp duy nhất để in ra:**

- Gọi cặp vị trí là `(i, j)` với `1 ≤ i < j ≤ N`, `A[i] + A[j] = K`.
- Chọn cặp có chỉ số trái nhỏ nhất `i`.

---

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

Dữ liệu vào từ file `TP_Find_2.inp` gồm:

* **Dòng 1:** Hai số nguyên `N` và `K` cách nhau một khoảng trắng.  
* **Dòng 2:** `N` số nguyên `A[1], A[2], …, A[N]` cách nhau một khoảng trắng.

**Ràng buộc:**
```
1 ≤ N ≤ 1,000,000
0 ≤ A[i] ≤ 1,000,000
-1,000,000 ≤ K ≤ 1,000,000
```

> Ghi chú: Biên `K` có thể âm/ dương/ 0; vẫn áp dụng quy tắc chọn cặp như trên.

---

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

Ghi ra file `TP_Find_2.out` hai số `X Y` (giá trị phần tử) cách nhau một khoảng trắng — tương ứng với cặp thỏa mãn quy tắc chọn ở trên.  
Nếu không tồn tại cặp thỏa mãn, in:
```
-1 -1
```

---

### ✨ Ví dụ

| Input (`TP_Find_2.inp`) | Output (`TP_Find_2.out`) |
| :--- | :--- |
| `5 9`<br>`1 2 4 5 7` | `2 7` |
| `7 8`<br>`4 5 7 6 3 4 0` | `4 4` |
| `5 10`<br>`1 2 4 5 7` | `-1 -1` |

---

### 🧪 Phân Subtask & Ràng buộc

| Subtask | Ràng buộc bổ sung | Gợi ý thuật toán |
| :--- | :--- | :--- |
| **Subtask 1 (30 điểm)** | `N ≤ 3000` | **Vét cạn O(N²)**|
| **Subtask 2 (70 điểm)** | `N ≤ 1,000,000` | **Tối ưu O(N)** với **Hash Map** |

---

### 💡 Gợi ý

- Với Subtask 2, **không nên** sắp xếp mảng nếu bạn phải bảo toàn quy tắc chọn theo **thứ tự xuất hiện gốc**.  
- Dùng `unordered_map`/`dictionary` để lưu tần suất hoặc lần gặp đầu tiên của mỗi giá trị đã quét.

✅ Đã AC: 14 / 46 submissions