//
you're reading...
Bài tập huấn luyện

Đề thi học sinh giỏi 12 cấp tỉnh 2016 – Bài 2

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH NĂM HỌC 2015 – 2016

ĐỀ THI MÔN: TIN HỌC – Ngày thi: 20/3/2016


Đề bài


Bài 2: (7,0 điểm) ĐÀN BÒ

Trang trại của ông Năm vừa xây dựng một dãy n chuồng bò mới trên một đường thẳng dọc theo con đường đi xuyên qua cánh đồng cỏ. Chuồng bò thứ i nằm ở vị trí xi tính từ đầu đường. Trang trại có tất cả m con bò và ông Năm định bố trí mỗi con bò vào một chuồng mới xây này. Tuy nhiên các con bò của ông lại rất hung hăng, khi nhốt chúng gần nhau thì chúng có thể làm tổn thương lẫn nhau, vì vậy ông muốn bố trí sao cho khoảng cách tối thiểu giữa bất kỳ hai con bò nào trong số chúng càng lớn càng tốt.

Yêu cầu: Hãy tìm cách bố trí các con bò vào chuồng sao cho khoảng cách tối thiểu giữa hai con bò bất kỳ là lớn nhất.

Dữ liệu vào: Cho từ tệp văn bản DANBO.INP có dạng:

  • Dòng thứ nhất ghi hai số nguyên nm (2 ≤ m n ≤ 105).
  • Dòng thứ hai ghi n số nguyên x1, x2, …, xn (0 ≤ x1 < x2 < … < xn ≤ 109).

Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi vào tệp văn bản DANBO.OUT một số nguyên duy nhất là khoảng cách tối thiểu lớn nhất khi bố trí các con bò vào chuồng.

Ví dụ:

DANBO.INP DANBO.OUT
6 3

1 2 3 4 8 9

3

Giải thích: Các con bò được bố trí vào các chuồng thứ nhất, thứ tư và thứ sáu. Hai con gần nhau nhất ở chuồng thứ nhất và chuồng thứ tư có khoảng cách là 3.


Hướng dẫn hoặc lời giải


[Chương trình mẫu]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 179,897 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: