Elearning CodePath – CTP Online Judge

Tìm Kiếm

GEN030

🟢 Hard #Greedy #Math

| Mục | Chi tiết |
| :--- | :--- |
| **Tên Bài Toán** | Tìm kiếm |
| **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 mảng $A$ có $n$ số nguyên dương $\{a_1, a_2, ..., a_n\}$.

**Yêu cầu:** Với mỗi số nguyên dương $a_i$, tìm số nguyên dương $a_j$ $(j > i)$ với $j$ nhỏ nhất thỏa mãn $a_j$ có nhiều ước hơn $a_i$; nếu không có số $a_j$ thỏa mãn thì kết quả tìm kiếm là $-1$.

---

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

Vào từ file văn bản có thông tin sau:
* **Dòng đầu tiên** là số nguyên dương $n$ $(n \le 2 \times 10^5)$.
* **Dòng thứ hai** có $n$ số nguyên dương $a_1, a_2, ..., a_n$ $(a_i \le 10^6)$.

Dữ liệu đảm bảo: $\max\{a_i\} - \min\{a_i\} \le 10^6$ $\forall i = 1..n$. 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 có $n$ số nguyên theo thứ tự là kết quả tìm kiếm theo yêu cầu. Các số ghi cách nhau bởi một dấu cách trống.

---

### ✨ Ví dụ

| DỮ LIỆU VÀO | KẾT QUẢ RA |
| :---: | :---: |
| `6` <br> `6 18 7 10 9 8` | `18 -1 10 -1 8 -1` |

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

Dãy số: `18 7 10 9 8`

**Bước 1:** Tính số ước của mỗi phần tử:
* $a_1 = 18$: ước là $\{1, 2, 3, 6, 9, 18\}$ → 6 ước
* $a_2 = 7$: ước là $\{1, 7\}$ → 2 ước  
* $a_3 = 10$: ước là $\{1, 2, 5, 10\}$ → 4 ước
* $a_4 = 9$: ước là $\{1, 3, 9\}$ → 3 ước
* $a_5 = 8$: ước là $\{1, 2, 4, 8\}$ → 4 ước

**Bước 2:** Tìm kết quả cho từng phần tử:

* $a_1 = 18$ (6 ước): 
  - Kiểm tra $a_2 = 7$ (2 ước) → $2 < 6$ ✗
  - Kiểm tra $a_3 = 10$ (4 ước) → $4 < 6$ ✗
  - Kiểm tra $a_4 = 9$ (3 ước) → $3 < 6$ ✗
  - Kiểm tra $a_5 = 8$ (4 ước) → $4 < 6$ ✗
  - **Kết quả:** $-1$ (không có số nào có nhiều ước hơn)

* $a_2 = 7$ (2 ước):
  - Kiểm tra $a_3 = 10$ (4 ước) → $4 > 2$ ✓
  - **Kết quả:** $10$ (hoặc index 3, tùy đề bài)

* $a_3 = 10$ (4 ước):
  - Kiểm tra $a_4 = 9$ (3 ước) → $3 < 4$ ✗
  - Kiểm tra $a_5 = 8$ (4 ước) → $4 = 4$ ✗ (phải NHIỀU hơn, không bằng)
  - **Kết quả:** $-1$

* $a_4 = 9$ (3 ước):
  - Kiểm tra $a_5 = 8$ (4 ước) → $4 > 3$ ✓
  - **Kết quả:** $8$ (hoặc index 5)

* $a_5 = 8$ (4 ước):
  - Không còn phần tử nào sau nó
  - **Kết quả:** $-1$

**Lưu ý:** Output trong ví dụ `4 6 2 4 3 4` có vẻ là **chỉ số (index)** thay vì giá trị. Nếu in index (1-indexed):
- $a_1$: không tìm thấy → $-1$ (nhưng ví dụ ghi 4?)
- $a_2$: tìm thấy ở vị trí 3 (index của $a_3 = 10$)

---

### 🏷 Ràng buộc

| Subtask | Ràng buộc | Kỹ thuật | Tỷ lệ điểm |
| :--- | :--- | :--- | :--- |
| $1$ | Dữ liệu vào có $n \le 10^3$ và $a_i \le 10^4$ $\forall i = 1..n$ | Brute force $O(n^2 \sqrt{a_i})$ | $20\%$ |
| $2$ | Dữ liệu vào có $n > 10^3$ và $a_i \le 10^6$ $\forall i = 1..n$ | Tiền xử lý số ước + Stack/Deque | $50\%$ |
| $3$ | Không có ràng buộc nào thêm | Tối ưu với Monotonic Stack | $30\%$ |

---

✅ Đã AC: 0 / 6 submissions