Elearning CodePath – CTP Online Judge

DART

🟢 Easy #Binary Search #String #Sorting

## 💻 Đề Bài:

**Giới hạn thời gian**:  2 giây

---

Cho một bảng lưới kích thước $N \times M$, trong đó $N$ và $M$ đều là số lẻ. Các hàng được đánh số từ $1$ đến $N$, các cột từ $1$ đến $M$.

Giá trị của ô $(i, j)$ được ký hiệu là $v_{i,j}$, được xác định bằng cách **nối hai số $i$ và $j$ lại với nhau** (xem chúng như chuỗi kí tự và nối). Ví dụ: $v_{12,345} = 12345$ và $v_{20,25} = 2025$.

**Yêu cầu:** Xác định **giá trị trung vị (median)** của tất cả các ô trong lưới.
* Tổng số ô là $N \times M$.
* Vị trí trung vị là vị trí thứ $P = \lceil \frac{N \cdot M}{2} \rceil$.

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

* **Dòng 1:** Chứa 1 số nguyên duy nhất $T$ ($1 \le T \le 5$) (số testcase).
* **$T$ dòng tiếp theo:** Mỗi dòng chứa hai số nguyên cách nhau bởi khoảng trắng: $N$ và $M$ ($N, M$ lẻ).
$$1 \le N, M \le 10^9$$

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

* In ra giá trị trung vị của tất cả các ô trong bảng.

### ✨ **Ví dụ**

| Input | Output |
| :--- | :--- |
| **1** | **23** |
| 3 5 | |

**Giải thích:** Lưới có các giá trị $11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35$.
Tổng số phần tử: $3 \times 5 = 15$. Vị trí trung vị: $\lceil 15/2 \rceil = 8$.
Phần tử thứ 8 khi sắp xếp là **23**.

---
#### **Subtask 1 (10%): $N = 1, 1 \le M \le 10^9$**

#### **Subtask 2 (30%): $1 \le N, M \le 1000$**

#### **Subtask 3 (30%): $1 \le N \le 10^5, 1 \le M \le 10^9$**

#### **Subtask 4 (30%): $1 \le N, M \le 10^9$**

##### **Gợi ý: Tìm kiếm nhị phân** trên giá trị $X$

✅ Đã AC: 0 / 2 submissions