Elearning CodePath – CTP Online Judge

Meeting Friends

VAF

🟢 Hard #General #Greedy #Optimization

### 📌 Thông tin chung

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

Nhà của Kangaroo và $N$ người bạn đều nằm trên trục tọa độ $Ox$.
* Nhà Kangaroo ở gốc tọa độ $0$.
* Nhà bạn thứ $i$ cách nhà Kangaroo $x_i$ đơn vị độ dài. Tức là tọa độ của bạn thứ $i$ là $x_i$.

Mỗi bước nhảy của Kangaroo có thể là $1, 2, 3, 4$ hoặc $5$ đơn vị độ dài.

Yêu cầu: Xác định số bước nhảy tối thiểu để Kangaroo đến thăm được tất cả các bạn của mình. (Kangaroo luôn nhảy một cách tối ưu để đạt được tọa độ $x_i$).

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

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

* Dòng 1: Một số nguyên $N$: số lượng bạn.
* Dòng 2: Gồm $N$ số nguyên $x_1, x_2, \dots, x_N$, cách nhau bởi một dấu cách, là tọa độ nhà các bạn.

Giới hạn:
* $1 \le N \le 2 \times 10^5$.
* $1 \le x_i \le 10^9$ ($1 \le i \le N$).

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

Ghi ra file `VAF.OUT` một số nguyên duy nhất là số bước nhảy tối thiểu của Kangaroo.

---
### ✨ Ví dụ

| Input | Output |
| :--- | :--- |
| `3` <br> `12 18 21` | `6` |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $1 \le N \le 10^2$; $1 \le x_i \le 10^5$ | $40\%$ |
| 2 | $10^2 < N \le 10^3$; $10^5 < x_i \le 10^6$ | $30\%$ |
| 3 | $1 \le N \le 2 \times 10^5$; $1 \le x_i \le 10^9$ | $30\%$ |

---

✅ Đã AC: 0 / 3 submissions