THỰC HÀNH

 (Đề thi học sinh giỏi Toàn quốc 2003)

Trên tuyến đường của xe  du lịch vòng quanh thế giới xuất phát từ bến xe có n khách sạn đánh số từ 1 đến n theo thứ tự xuất hiện trên tuyến đường, trong đó khách sạn i cách địa điểm xuất phát a_i km (a₁ < a₂ < … < a_n).

Để đảm bảo sức khỏe cho hành khách, theo tính toán của các nhà chuyên môn, sau khi đã chạy được P km xe nên dừng lại cho khách nghỉ ngơi ở khách sạn. Vì thế, nếu xe dừng lại cho khách nghỉ ở khách sạn sau khi đã đi được Q km thì lái xe phải trả một lượng phạt là (Q – P)².

Yêu cầu: Hãy xác định xem trên tuyến đường đến khách sạn n, xe cần dừng lại nghỉ ở những khách sạn nào để tổng lượng phạt mà lái xe phải trả là ít nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa số nguyên dương P.
• Dòng thứ ba chứa các số nguyên dương a₁, a₂, …, a_n (hai số liên tiếp trên dòng được ghi cách nhau bởi dấu cách).

Dữ liệu ra:

Một số nguyên duy nhất là lượng phạt nhỏ nhất mà lái xe phải trả.

(Đề thi còn yêu cầu dữ liệu ra chi tiết hơn, ở đây đã lược bớt)

Ví dụ:

Dữ liệu vào:
4
300
250 310 550 590

Dữ liệu ra:
500

Giải thích: Lái xe cho hành khách nghỉ tại các khách sạn 2 và 4. Số tiền bị phạt là:

(310 – 300)² + (590 – 310 – 300)² = 100 + 400 = 500

Giới hạn: 1 ≤ n ≤ 10⁴; 0 < P ≤ 500; 0 < a_i ≤ 2.10⁶.