Elearning CodePath – CTP Online Judge

Chuyển đổi sang Mã Nhị phân

D2B

🟢 Easy #String #Math #Monotonic Stack #Sliding Window

### 📌 Thông tin chung

| Mục | Chi tiết |
| :--- | :--- |
| **Tên File Input** | `nhiphan.inp` |
| **Tên File Output** | `nhiphan.out` |
| **Độ phức tạp mong muốn** | $O(T \cdot \log_{2} N)$ |

---

### 📝 Bài toán

Cho một dãy gồm $T$ số nguyên dương. Với mỗi số nguyên dương $N$ trong dãy, hãy thực hiện chuyển đổi $N$ sang dạng mã nhị phân (hệ cơ số 2) và in chuỗi nhị phân đó ra màn hình.

**Quy tắc:**
* Chuỗi nhị phân phải là biểu diễn chuẩn, không có các số 0 vô nghĩa ở đầu (trừ khi $N=0$, trong trường hợp đó chuỗi là "0"). Tuy nhiên, do ràng buộc $N$ là số dương, nên sẽ không có chuỗi "0" nào được in ra.

---

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

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

* **Dòng 1:** Gồm số nguyên dương $T$ – số lượng trường hợp kiểm thử.
* **$T$ dòng tiếp theo:** Mỗi dòng chứa một số nguyên dương $N$.

**Giới hạn (Ràng buộc):**
* $1 \le T \le 10^5 $
* $1 \le N \le 2 \cdot 10^9$
> Ràng buộc $N \le 2 \cdot 10^9$ đảm bảo $N$ nằm trong giới hạn của kiểu dữ liệu 32-bit (integer) và chuỗi nhị phân tối đa khoảng 31 bit.

---

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

Ghi ra file `nhiphan.out` kết quả chuyển đổi nhị phân của mỗi số $N$, mỗi chuỗi trên một dòng riêng biệt.

---

### ✨ Ví dụ

| Input (`nhiphan.inp`) | Output (`nhiphan.out`) |
| :--- | :--- |
| `2` <br> `13` <br> `3` | `1101` <br> `11` |

---

### 🧪 Giải thích Ví dụ

1.  **Trường hợp $N=13$:**
    $$
    13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 8 + 4 + 0 + 1
    $$
    $\implies$ Kết quả: $\mathbf{1101}$
2.  **Trường hợp $N=3$:**
    $$
    3 = 1 \cdot 2^1 + 1 \cdot 2^0 = 2 + 1
    $$
    $\implies$ Kết quả: $\mathbf{11}$

---

### 💡 Gợi ý thuật toán

Sử dụng thuật toán chia liên tiếp cho 2:

1.  Chia $N$ cho 2, lưu **số dư** (remainder) (luôn là 0 hoặc 1). Số dư này là bit nhị phân (binary digit) của $N$, bắt đầu từ bit LSB (Least Significant Bit - Bit có trọng số thấp nhất).
2.  Tiếp tục chia **thương số** (quotient) cho 2.
3.  Lặp lại cho đến khi thương số bằng 0.
4.  Chuỗi nhị phân là chuỗi các số dư được thu thập theo thứ tự **ngược lại** (từ cuối lên đầu).

Độ phức tạp của thuật toán cho mỗi số $N$ là $O(\log_2 N)$. Tổng độ phức tạp thời gian là $O(T \cdot \log_{2} N)$.
```

✅ Đã AC: 0 / 184 submissions