Sau nhiều năm chờ đợi, tuyến Metro số 2 Bến Thành – Tham Lương của TP.HCM cuối cùng cũng bước vào giai đoạn lắp đặt ray cuối cùng. Đây là tuyến metro ngầm dài nhất Việt Nam, đi qua nhiều quận trung tâm sầm uất của thành phố.
Ban quản lý dự án giao cho các kỹ sư nhiệm vụ lắp đặt hệ thống ray thép cho toàn tuyến. Kho vật tư hiện có N thanh thép ray được nhập khẩu từ Nhật, trong đó thanh thứ i có chiều dài L_i(cm). Do đặc thù kỹ thuật, mỗi đoạn ray lắp xuống hầm phải có cùng chiều dài d (cm) (d là số nguyên dương) vì nếu các đoạn ray dài ngắn khác nhau, tàu chạy qua sẽ bị rung lắc không đều. Mỗi đoạn ray chỉ được cắt từ đúng một thanh thép nguyên và tuyệt đối không được hàn nối hai thanh lại với nhau vì mối hàn chịu lực kém, nguy hiểm khi tàu chạy tốc độ cao.
Theo thiết kế kỹ thuật, toàn tuyến cần đúng K đoạn ray. Các kỹ sư hiểu rằng đoạn ray càng dài thì số lượng mối nối càng ít, giúp tàu vận hành êm hơn và tăng tuổi thọ cho hệ thống đường ray.
Yêu cầu: Hãy tìm số nguyên dương d lớn nhất sao cho tổng số đoạn ray độ dài d (cm) có thể cắt được từ N thanh thép không nhỏ hơn K.
