Tài liệu Tuyển tập đề thi HSG 12 môn Tin học (2005-2008)

Tuyển tập đề thi HSG 12 môn Tin học (2005-2008)

Năm 2005
Bảng A
Bài 1. Phân đoạn Tên file chương trình: SEGPAR.PAS
Cho dãy số nguyên a1, a2, , an và số nguyên dương k. Ta gọi k-phân đoạn của dãy số đã cho là cách
chia dãy số đã cho ra thành k đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính
xác hơn, một k-phân đoạn được xác định bởi dãy chỉ số
121 . ≤ <<< =knn nn.
Đoạn thứ i là dãy con aniư1+1, aniư1+2 , ., ani , i = 1,2, ., k . Ở đây quy ước n0 = 0.
Yêu cầu: Hãy xác định số M nhỏ nhất để tồn tại k-phân đoạn sao cho tổng các phần tử trong mỗi đoạn
đều không vượt quá M.
Dữ liệu: Vào từ file văn bản SEGPAR.INP.
ã Dòng đầu tiên chứa hai số nguyên n và k (1≤ k ≤ n ≤ 15000);
ã Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai (|ai| ≤ 30000), i =1, 2, , n.
Các số cạnh nhau trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra file SEGPAR.OUT một số nguyên duy nhất là giá trị M tìm được.