Elearning CodePath – CTP Online Judge

Số nhát cắt tối thiểu để chia vòng tròn thành các phần bằng nhau

NT002

🟢 Hard #Math #Number Theory #Geometry

### 📌 Thông tin chung

---
Cho một mảng $arr$ biểu diễn các góc (theo độ) mà tại đó một vòng tròn đã được cắt. 
Các góc được cho là vị trí so với điểm 0 độ, theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ 
(tùy thuộc vào quy ước, nhưng quan trọng là sự chênh lệch góc). Mảng $arr$ đã được sắp xếp theo thứ tự tăng dần.

Yêu cầu: Xác định số lượng nhát cắt tối thiểu cần bổ sung thêm để vòng tròn được chia thành các phần bằng nhau 
(tức là tất cả các cung tạo thành phải có độ dài bằng nhau).

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

Tìm số nhát cắt nhỏ nhất cần thêm để độ dài của tất cả các cung (segments) tạo bởi tổng số nhát cắt (cũ + mới) là bằng nhau.

---
### 📥 Dữ liệu vào

* Dòng đầu tiên chứa số nguyên $N$ là số lượng nhát cắt ban đầu ($0 \le N \le 10^5$).
* Dòng thứ hai chứa $N$ số nguyên $arr_i$ là các góc cắt ($0 \le arr_i < 360$).

Giới hạn:
* $0 \le N \le 10^5$.
* Mảng $arr$ đã được sắp xếp.
* Các góc là số nguyên.

---
### 📤 Kết quả

Ghi ra một số nguyên duy nhất là số lượng nhát cắt tối thiểu cần thêm.

---
### ✨ Ví dụ

| Input| Output | Giải thích |
| :---: | :---: | :--- |
| `4` <br> `0 90 180 270` | `0` | Không cần thêm nhát cắt nào vì vòng tròn đã được chia thành bốn phần bằng nhau (mỗi phần $90^\circ$). |
| `2` <br> `90 210` | `1` | Các cung hiện tại là $90^\circ$ (từ $210^\circ$ đến $90^\circ$ theo vòng tròn),<br> $120^\circ$ (từ $90^\circ$ đến $210^\circ$), $150^\circ$ (từ $210^\circ$ đến $90^\circ$ qua $0/360^\circ$).<br> Để chia vòng tròn thành 3 phần bằng nhau ($120^\circ$ mỗi phần), cần thêm 1 nhát cắt tại $330^\circ$. |

---
### 🏷 Subtasks

| \# | Điểm | Ràng buộc |
| :---: | :---: | :--- | 
| $1$ | $30\%$ | $N \le 100$  |
| $2$ | $70\%$ | $N \le 10^5$  |

---

✅ Đã AC: 1 / 3 submissions