//
you're reading...
00 - Chủ đề chung, Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: Dải lụa

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


Thực hành Tin học trẻ – Bảng B – cấp  THCS – 2016 – Ngày thi: 14/7/2016 – Bài 3


Đề bài


Đầu năm học mới, Bé Sen phụ trách việc mua thảm trải bàn cho lớp. Thảm trải bàn có hình chữ nhật, chiều rộng là một mét, chiều dài là k mét. Tiệm vải bán hàng cho bé Sen có một dải lụa chiều rộng một mét chiều dài n mét, tùy theo hoa văn mỗi mét trên dải lụa mà có giá tiền khác nhau. Số tiền mỗi mét được ghi trên dải lụa tại vị trí cuối mỗi mét, từ mét thứ 1 đến mét thứ n lần lượt là a1, a2, …, an đồng. Để tiết kiệm tiền quỹ lớp bé Sen quyết định mua k mét lụa này làm thảm trải bàn sao cho với số tiền phải trả là ít nhất có thể.

Yêu cầu: Tìm vị trí đầu và vị trí cuối trên dải lụa để cắt k mét liền nhau để làm thảm trải bàn sao cho số tiền phải trả là nhỏ nhất.

Dữ liệu vào:  Cho từ tệp văn bản DAILUA.INP có cấu trúc như sau:

  • Dòng thứ nhất ghi hai số nguyên dương n, k (1 ≤ k < n ≤ 106);
  • Dòng thứ hai ghi n số nguyên dương a1, a2,…, an (1≤ ai ≤ 105; i=1..n).

Các số ghi trên một dòng các nhau một kí tự trắng.

Kết quả: Ghi vào tệp văn bản DAILUA.OUT gồm một dòng duy nhất ghi hai số nguyên dương là vị trí đầu và vị trí cuối tìm được. Nếu có nhiều đáp án thì ghi đáp án gần đầu dải lụa nhất.

Ví dụ:

DAILUA.INP DAILUA.OUT
6 2

6 5 2 6            4 2

3 5

 

Ràng buộc dữ liệu:

  • Có 30% số test tương ứng với 1 < n ≤ 103k = 1
  • Có 40% số test tương ứng với 1 < n  ≤ 103 và 1 < k ≤ 10
  • Có 30% số test tương ứng với 103 < n  ≤ 106 và  10 < k ≤ 100

Hướng dẫn


[]


Chương trình


[]

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 Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,393 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: