Elearning CodePath – CTP Online Judge

BOOKS1

🟢 Medium #Binary Search #Combinatorics

---
### 📝 Bài toán
Trước khi máy in được phát minh, việc sao chép sách là một công việc cực kỳ khó khăn. Toàn bộ nội dung phải được viết lại bằng tay bởi các scriber (người chép thuê). Công việc này rất nhàm chán và cách duy nhất để đẩy nhanh tiến độ là thuê thêm người.

Giả sử bạn có m cuốn sách (được đánh số từ 1, 2, ..., m) với số trang tương ứng là p1, p2, ..., pm. Bạn cần chia m cuốn sách này cho k người chép thuê (k <= m). Quy tắc phân chia như sau:
1. Mỗi cuốn sách chỉ được giao cho đúng một người.
2. Mỗi người phải nhận một dãy các cuốn sách liên tiếp nhau. Điều này có nghĩa là tồn tại một dãy số tăng dần 0 = b0 < b1 < b2 < ... < bk = m sao cho người thứ i nhận các cuốn sách từ bi-1 + 1 đến bi.
3. Mỗi người phải được giao ít nhất một cuốn sách.

Thời gian để hoàn thành việc sao chép toàn bộ số sách được quyết định bởi người phải chép nhiều trang nhất.

Yêu cầu: Hãy tìm cách phân chia sao cho số lượng trang sách lớn nhất mà một người phải chép là nhỏ nhất có thể.

Nếu có nhiều phương án chia cùng cho ra giá trị cực tiểu đó, hãy chọn phương án tối ưu hóa theo thứ tự ưu tiên: giảm thiểu công việc cho người thứ nhất, sau đó đến người thứ hai, và tiếp tục như vậy.

### 📥 Định dạng Đầu vào
Dữ liệu vào từ file BOOKS1.INP:
* Dòng đầu tiên chứa số nguyên dương N là số lượng bộ test.
* Mỗi bộ test gồm hai dòng:
    * Dòng 1: Hai số nguyên m và k (1 <= k <= m <= 500).
    * Dòng 2: m số nguyên p1, p2, ..., pm (pi < 10000000).

### 📤 Định dạng Đầu ra
Ghi ra file BOOKS1.OUT:
* Với mỗi bộ test, in trên một dòng dãy p1, p2, ..., pm được chia thành k phần bởi dấu gạch chéo ('/'). 
* Phải có đúng một khoảng trắng giữa các con số và dấu '/'.

### ✨ Ví dụ
| Input | Output |
| :--- | :--- |
| 2 | |
| 9 3 | 100 200 300 400 500 / 600 700 / 800 900 |
| 100 200 300 400 500 600 700 800 900 | |
| 5 4 | 100 / 100 / 100 / 100 100 |
| 100 100 100 100 100 | |

### 🏷 Subtasks
| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | m <= 20; k <= 5 | 30% |
| 2 | m <= 500; k <= 500 | 70% |

✅ Đã AC: 9 / 14 submissions