Bài 4: (4 điểm)
Một xưởng dệt vải chịu trách nhiệm phân phối vải đến K cửa hàng và lượng vải mỗi cửa hàng cần là như nhau. Trong kho xưởng dệt còn N khúc vải được dệt sẵn, khúc vải thứ (1<=i<=N) dài ai mét. Xưởng dệt quyết định cắt N khúc vải thành K tấm vải bằng nhau để chuyển tới cửa hàng tiêu thụ. Biết rằng không thể ghép các tấm vải ngắn thành các tấm vải dài, bạn hãy tìm cách cắt N khúc vải thành K tấm vải bằng nhau với độ dài mỗi tấm lớn nhất có thể.
Dữ liệu vào: File văn bản CATVAI.INP gồm:
- Dòng 1 chứa hai số nguyên N, K (1 <=N<=105; 1<K<=109)
- Dòng 2 gồm N số nguyên dương ai, cách nhau khoảng trắng (ai<=109;1<=i<=N)
Dữ liệu ra: File văn bản CATVAI.OUT gồm:
- Một số nguyên là độ dài lớn nhất có thể của các tấm vải chuyển cho các cửa hàng. Nếu không tồn tại cách cắt nào thỏa mãn thì in ra 0
|
CATVAI.INP |
CATVAI.OUT |
|
5 5 10 9 12 15 17 |
9 |
Giới hạn:
- Có 50% số test có N<=1000
- Có 50% số test còn lại không ràng buộc gì thêm
Giải thích:
Cắt khúc vải 1 thành 2 tấm vải có độ dài 1, 9 (tấm độ dài 1 không thể sử dụng sẽ bỏ đi)
- Giữ nguyên độ dài khúc vải 2
- Cắt khúc vải 3 thành 2 tấm vải có độ dài 3, 9 (tẩm độ dài 3 không thể sử dụng sẽ bỏ đi)
- Cắt khúc vải 4 thành 2 tấm vải có độ dài 6, 9 (tấm độ dài 6 không thể sử dụng sẽ bỏ đi)
- Cắt khúc vải 5 thành 2 tấm vải có độ dài 8, 9 (tấm độ dài 8 không thể sử dụng sẽ bỏ đi)
Từ đó thu được 5 tấm vải có độ dài 9 để phân phối cho K=5 của hàng.