Elearning CodePath – CTP Online Judge

Cắt dây bằng nhau

TKM09_bsribbon

🟢 Easy

## Đề bài

Có `N` sợi dây, sợi thứ `i` có độ dài nguyên `Ai`.

Bạn muốn cắt các sợi dây thành ít nhất `K` đoạn dây có cùng độ dài nguyên dương. Mỗi đoạn cắt ra phải có độ dài đúng bằng nhau. Một sợi dây có thể bị cắt thành nhiều đoạn, phần thừa có thể bỏ đi.

Hãy tìm độ dài lớn nhất có thể của mỗi đoạn dây.

Nếu không thể tạo ra `K` đoạn dây độ dài ít nhất `1`, in ra `0`.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `N` và `K`.
- Dòng thứ hai chứa `N` số nguyên `A1, A2, ..., AN`.

## Dữ liệu ra

In ra một số nguyên duy nhất — độ dài lớn nhất của mỗi đoạn dây.

## Ràng buộc

```text
1 <= N <= 200000
1 <= K <= 10^14
1 <= Ai <= 10^9
```

## Subtask

- Subtask 1 — 25 điểm: `N <= 20`, `Ai <= 100`, `K <= 100`.
- Subtask 2 — 35 điểm: `N <= 5000`, `Ai <= 10^6`, `K <= 10^7`.
- Subtask 3 — 40 điểm: Không có ràng buộc bổ sung.

## Ví dụ

### Input

```text
4 11
802 743 457 539
```

### Output

```text
200
```

## Giải thích ví dụ

Nếu cắt mỗi đoạn dài `200`, ta tạo được:

```text
802 / 200 = 4 đoạn
743 / 200 = 3 đoạn
457 / 200 = 2 đoạn
539 / 200 = 2 đoạn
```

Tổng cộng `11` đoạn. Không thể chọn độ dài lớn hơn `200` mà vẫn đủ `11` đoạn.

✅ Đã AC: 10 / 16 submissions