Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
A1. Phân đoạn In E-mail
(5 votes)
Người viết: Ngô Minh Đức   
17/04/2008

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ố

.

Đoạn thứ i là dãy con  . Ở đây quy ước  

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 nk (1≤ kn ≤ 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.

Ví dụ:

SEGPAR.INP

 

SEGPAR.OUT

9 4

1

1

1

3

2

2

1

3

1

 

5

 

 
Tiếp >