Đề thi chọn học sinh giỏi Lớp 12 THPT môn Tin học - Năm học 2010-2011 - Sở GD&ĐT Ninh Bình (Vòng 1)

SỞ GIÁO DỤC VÀ ĐÀO TẠO
ĐỀ THI CHÍNH THỨC
TỈNH NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT
NĂM HỌC 2010 - 2011
Môn: Tin học - Vòng 1
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
(Đề thi gồm 03 bài trong 02 trang)
Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian chạy
1- Tính tổng
SUM.PAS
SUM.INP
SUM.OUT
1giây/test
2- Dây chuyền
FACTORY.PAS
FACTORY.INP
FACTORY.OUT
2giây/test
3- Cứu trợ
STORM.PAS
STORM.INP
STORM.OUT
2giây/test
Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. 
Bài 1: Tính tổng (7 điểm).
 Trên một màn hình lớn, người ta lần lượt cho hiện ra các số của một dãy gồm N số nguyên không âm a1, a2, , aN và cứ lặp đi lặp lại như thế (nghĩa là sau khi ai xuất hiện vài giây đến lượt ai+1 xuất hiện, số xuất hiện sau aN là a1). 
Yêu cầu: Bạn được đề nghị tính tổng của K số nguyên liên tiếp xuất hiện trên màn hình bắt đầu từ số nguyên thứ B. 
Dữ liệu vào: Chứa trong file SUM.INP gồm hai dòng:
+ Dòng đầu tiên ghi ba số nguyên N, K, và B, 1 £ N £104; 1 £ K £ 2. 104 ; 1 £ B £ 109.
+ Trong N dòng sau, dòng thứ i chứa số ai (ai < 2.109). 
Dữ liệu ra: Ghi ra file SUM.OUT một số là tổng tìm được.
Ví dụ:
SUM.INP
SUM.OUT
5 7 6
 1 
 2 
 3 
 4 
 5
18
Bài 2(7 điểm): Dây chuyền sản xuất 
 Nhà máy Intel cần kết hợp N công việc thành một dây chuyền sản xuất. Công việc thứ i cần ai ngày công. Mỗi công đoạn sản phẩm là kết hợp 2 công việc liên tiếp lại với nhau thành một 
công việc với chi phí cho công đoạn này bằng tổng ngày công của 2 công việc đó. 
Yêu cầu: Bạn hãy giúp nhà máy ghép N công việc đó thành dây chuyền bằng N-1 công đoạn sản phẩm sao cho tổng chi phí các công đoạn là nhỏ nhất.
Dữ liệu vào: Trong file FACTORY.INP có dạng:
 - Dòng đầu ghi số N (N<101) là số công việc.
 - Dòng thứ i trong N dòng sau ghi số nguyên dương ai là số ngày công của công việc thứ i 
 (ai < 1000). 
Dữ liệu ra: Ghi ra file FACTORY.OUT một số nguyên dương là tổng chi phí nhỏ nhất tìm được.
Ví dụ:
FACTORY.INP
FACTORY.OUT
5
4 
1 
2 
7 
5
41
Giải thích:
4 2 1 7 5
4 3 7 5
 7 7 5
 7 12
 19
Tổng chi phí: 3+7+12+19=41
(60% số test có n £ 11)
Bài 3. Cứu trợ (6 điểm)
 Hai trận lụt lịch sử liên tiếp đang tàn phá nặng nề khu vực miền Trung nước ta. Đồng bào vùng lũ lụt đang gặp rất nhiều khó khăn thiếu thốn. Công tác cứu trợ dù có nhiều trở ngại nhưng đang được thực hiện hết sức khẩn trương và bài bản. Một uỷ ban cứu trợ địa phương nhận được N thùng hàng cứu trợ. Tại địa phương có rất nhiều khu vực bị thiệt hại, uỷ ban đã đánh giá và lập danh sách các khu vực đó theo mức độ thiệt hại giảm dần. Để đảm bảo công bằng, uỷ ban sẽ phân chia hết số hàng viện trợ cho các khu vực sao cho số thùng hàng mỗi khu vực nhận được không nhiều hơn của khu vực bị thiệt hại nặng hơn. Ngoài ra, mỗi khu vực không nhận được
quá K thùng hàng.
Yêu cầu: Do số người làm công tác cứu trợ không nhiều nên uỷ ban muốn xác định xem có bao 
nhiêu phương án gửi hàng cứu trợ cho các khu vực theo quy tắc trên.
Dữ liệu vào: 
 Cho trong file STORM.INP gồm một dòng chứa hai số N và K (N < 10000, K < 100).
Dữ liệu ra: 
 Ghi ra file STORM.OUT một số duy nhất là phần dư khi chia cho 109 của số cách phân chia
hàng cứu trợ .
Ví dụ: Nếu có 5 thùng hàng (N = 5) và mỗi khu vực nhận không quá 3 thùng (K=3) thì có 5 cách phân chia sau (ở mỗi cách lần lượt gửi hàng cho các khu vực có thiệt hại giảm dần bắt đầu từ nơi bị thiệt hại lớn nhất):
 	 5 = 3 + 2; 5 = 3 + 1+ 1; 5 = 2 + 1 + 1 + 1;
 5 = 2 + 2 + 1; 5 = 1 + 1 + 1 + 1+ 1;
STORM.INP
STORM.OUT
5 3
5
(Có 60 % số test có N < 100 và K < 10).
---------------------Hết---------------------
Hä vµ tªn thÝ sinh...................................... Sè b¸o danh:.........................................................
Ch÷ kÝ cña gi¸m thÞ 1................................ Ch÷ kÝ cña gi¸m thÞ 2............................................