Elearning CodePath – CTP Online Judge

PENCILS

Bút Chì Màu

🟢 Easy #Binary Search

### 📌 Thông tin chung

---
### 📝 Bài toán

An có $N$ cái bút chì màu. Màu của ruột bút chì thứ $i$ được mô tả bởi bộ ba số nguyên $(R_i, G_i, B_i)$ cho ba màu chính (Đỏ, Xanh lá cây, Xanh da trời).

Độ lệch màu của cái bút chì thứ $i$ và cái bút chì thứ $j$ được xác định bởi:
$\text{Diff}(i, j) = |R_i - R_j| + |G_i - G_j| + |B_i - B_j|$

Dải màu của một dãy các bút chì được xác định là độ lệch màu lớn nhất của hai cái bút chì bất kỳ trong dãy đó.

Yêu cầu: Chọn ra trong dãy $N$ cái bút chì $K$ cái bút chì (không nhất thiết liên tục) sao cho dải màu của $K$ bút chì này là nhỏ nhất.

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

Dữ liệu vào từ file `PENCILS.INP`:

* Dòng đầu tiên: Ghi hai số nguyên dương $N$ và $K$.
* $N$ dòng tiếp theo: Dòng thứ $i$ ghi ba số nguyên $R_i, G_i, B_i$.

Giới hạn:
* $2 \le K \le N \le 10^5$.
* $0 \le R_i, G_i, B_i \le 255$.

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

Ghi ra file `PENCILS.OUT` một giá trị nguyên là dải màu nhỏ nhất tìm được.

---
### ✨ Ví dụ

| Input (`PENCILS.INP`) | Output (`PENCILS.OUT`) |
| :--- | :--- |
| `5 3` `6 6 4` `6 2 7` `3 1 3` `4 1 5` `6 2 6` | `2` |

---
### 🏷 Phân Subtask
| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions