Elearning CodePath – CTP Online Judge

Biến Đổi Mảng thành Số Lẻ

ARRAY_TRANSFORMATION

🟢 Easy #Greedy

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một dãy $N$ số nguyên dương $A = (A_1, A_2, \dots, A_N)$.

Mỗi **bước đi**, bạn được phép chọn một giá trị $c$ là số chẵn ($c \in A, c \equiv 0 \pmod{2}$) và **chia đôi tất cả** các giá trị bằng $c$ có trong dãy.

$$
\text{Chọn } c \in A, c \equiv 0 \pmod{2}. \quad \forall i \text{ sao cho } A_i = c, \text{ đặt } A_i \leftarrow c / 2.
$$

Yêu cầu: Tìm **số bước đi tối thiểu** để biến mảng $A$ thành mảng chỉ chứa các số lẻ.

---

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

Dữ liệu vào gồm nhiều bộ test.

* **Dòng 1:** Số nguyên dương $T$ ($1 \le T \le 10^3$) – số lượng bộ test.
* **$T$ khối dòng tiếp theo:** Mỗi khối mô tả một bộ test:
    * Dòng 1: Số nguyên dương $N$ ($1 \le N \le 2 \cdot 10^5$) – số lượng phần tử.
    * Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$.

**Giới hạn (Ràng buộc):**
* $1 \le N \le 2 \cdot 10^5$
* $1 \le A_i \le 10^9$
* Tổng của tất cả $N$ trong các truy vấn $\le 2 \cdot 10^5$.

---

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

Với mỗi truy vấn, in ra một dòng duy nhất chứa số bước đi tối thiểu.

---

### ✨ Ví dụ

| Input (`Array.inp`) | Output (`Array.out`) |
| :--- | :--- |
| `4` `6` `40 6 40 3 20 1` `1` `1024` `4` `2 4 8 16` `3` `1 7 3` | `4` `10` `4` `0` |

---

### 🧪 Giải thích Ví dụ (Test 1)

$A = [40, 6, 40, 3, 20, 1]$.

| Bước | Chọn $c$ | Thay đổi | Mảng $A$ mới |
| :--- | :--- | :--- | :--- |
| **1** | $c=40$ | $40 \to 20$ | $[20, 6, 20, 3, 20, 1]$ |
| **2** | $c=20$ | $20 \to 10$ | $[10, 6, 10, 3, 10, 1]$ |
| **3** | $c=10$ | $10 \to 5$ | $[5, 6, 5, 3, 5, 1]$ |
| **4** | $c=6$ | $6 \to 3$ | $[5, 3, 5, 3, 5, 1]$ |

Mảng cuối cùng chỉ chứa số lẻ. Tổng số bước: **4**.

✅ Đã AC: 0 / 0 submissions