Bedao Mini Contest 21 - Cắt dây
View as PDF
Cho ~n~ sợi dây, sợi dây thứ ~i~ có độ dài ~A_i~ đơn vị độ dài. Giả sử có một sợi dây độ dài ~X~, nếu ta cắt một đoạn độ dài ~0 < t < X~ thì ta sẽ được hai sợi dây mới độ dài ~t~ và ~X - t~.
Được thực hiện ~k~ phép cắt dây, hãy tìm độ dài nhỏ nhất có thể của sợi dây dài nhất nhé.
Input
Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 2 \times 10^5, 0 \le k \le 10^9)~, thể hiện số lượng sợi dây và số lượng phép cắt thực hiện.
Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 10^9)~ - độ dài ban đầu của ~n~ sợi dây.
Output
Gọi ~S~ là độ dài nhỏ nhất của sợi dây dài nhất, có thể cắt được sau ~k~ phép cắt dây. In ra giá trị ~S~ làm tròn lên đến phần nguyên.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~k = 1~ |
| 2 | ~30~ | ~n, A_i \le 1000~ |
| 3 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5 1
3 3 3 4 5
Sample Output 1
4
Sample Input 2
2 3
7 9
Sample Output 2
4
Notes
Trong test ví dụ thứ hai, ta có thể thực hiện lần lượt các phép cắt như sau:
Với sợi dây độ dài ~7~, ta có thể cắt ra thành hai sợi dây độ dài ~\frac{7}{2}~.
Với sợi dây độ dài ~9~, ta có thể cắt ra thành hai sợi dây độ dài ~3~ và ~6~.
Với sợi dây độ dài ~6~, ta có thể cắt ra thành hai sợi dây độ dài ~3~.
Vậy sợi dây có độ dài lớn nhất là ~\frac{7}{2}~, ta cần in ra giá trị làm tròn lên là ~4~. Ta có thể chứng minh đây là phương án tối ưu.
Comments
ai gthich de bai voi a, nghe kho hieu qua
My solve: