Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học - Năm học 2013-2014 - Sở GD&ĐT Ninh Bình (Vòng 1) (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT 
Kỳ thi thứ nhất - Năm học 2013 – 2014
MÔN: TIN HỌC
Ngày thi 08/10/2013
(Thời gian 180, phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
 Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian chạy
1- Sức mạnh tập thể
STRONG.PAS
STRONG.INP
STRONG.OUT
1giây/test
2- Dãy số đối xứng
PALIN.PAS
PALIN.INP
PALIN.OUT
1giây/test
3- Thỏ và cà rốt
CAROT.PAS
CAROT.INP
CAROT.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: Sức mạnh tập thể (7,0 điểm)
Vừa qua, cơn bão số 10 bất ngờ đổ bộ vào nước ta, để đảm bảo an toàn cho một kho hàng thực phẩm chứa N gói hàng, bí thư Đoàn Thanh niên đã huy động tất cả đoàn viên của địa phương giúp đỡ chuyển hàng, số lượng huy động được là M người. Do kích thước của các gói hàng lớn, nên mỗi chuyến một người chỉ chuyển được một gói hàng, bí thư Đoàn phải phân công mỗi người chuyển một gói hàng phù hợp với sức khỏe của họ. Cho biết gói hàng thứ i cân nặng là ai (i=1,2,,n) và người thứ j có thể chuyển được gói hàng nặng tối đa là bj (j=1,2,,m). Sức mạnh của một người là số lượng gói hàng người đó có thể chuyển được. Sức mạnh tập thể là tổng sức mạnh của tất cả mọi người.
Yêu cầu: Bạn hãy lập trình giúp bí thư Đoàn tính xem sức mạnh tập thể là bao nhiêu?
Dữ liệu vào: chứa trong file STRONG.INP gồm 3 dòng:
- Dòng đầu tiên ghi hai số nguyên dương N, M (1 ≤ N, M ≤ 105)
- Dòng thứ 2 chứa n số nguyên dương lần lượt là các số a1, a2, ..., an. (ai ≤ 109)
- Dòng thứ 3 chứa m số nguyên dương lần lượt là các số b1, b2, ..., bm. (bj ≤ 109)
(Hai số cạnh nhau trên một dòng cách nhau bởi khoảng trắng)
Dữ liệu ra: Ghi ra file STRONG.OUT một số nguyên là sức mạnh tập thể tính được.
Ví dụ:
STRONG.INP
STRONG.OUT
4 3
7 5 4 9
8 6 3
5
(60% số test có n ≤ 1000)
Bài 2: Dãy số nguyên đối xứng (6,0 điểm)
	Cho dãy n số nguyên a1, a2, ..., an. Dãy con là một dãy các số liên tiếp của dãy số ban đầu. Một dãy số gọi là đối xứng nếu đọc dãy số từ trái qua phải thu được kết quả giống như đọc dãy số từ phải qua trái. 
Yêu cầu: Hãy lập trình tìm dãy con đối xứng dài nhất của dãy ban đầu.
Dữ liệu vào: Chứa trong file PALIN.INP gồm 2 dòng: 	
+ Dòng 1 là số n (n £ 104)
	+ Dòng 2 là n số nguyên mỗi số cách nhau bởi dấu cách. (│ai│≤ 104)
Kết quả ra: Ghi ra file PALIN.INP là độ dài lớn nhất của dãy con đối xứng tìm được.
Ví dụ: 
PALIN.INP
PALIN.OUT
8
5 1 2 3 2 1 2 1 
5
(60% số test có n ≤ 100)
Bài 3: Thỏ và cà rốt (7,0 điểm)
	Vụ mùa năm nay, gia đình nhà thỏ thu hoạch được rất nhiều cà rốt. Thỏ chia nền nhà kho thành một bảng các ô vuông gồm M hàng được đánh số từ 1 đến M từ trên xuống dưới và N cột được đánh số từ 1 đến N từ trái sang phải. Tại mỗi ô vuông thỏ đặt các thùng gỗ để dự trữ cà rốt, khối lượng cà rốt dự trữ trong các thùng được thỏ ghi lại rất cẩn thận. Hôm nay thỏ nhận được đơn đặt hàng mua một khối lượng K kg cà rốt. Thỏ vào kho lấy cà rốt ra bán. Để tiện cho việc quản lý, thỏ phải lấy hết cà rốt của tất cả các thùng nằm trên một hình chữ nhật. 
Yêu cầu: Hãy giúp thỏ lấy đủ lượng cà rốt để bán sao cho số thùng cần bê râ là nhỏ nhất.
Dữ liệu vào: Chứa trong file CAROT.INP có dạng:
	+ Dòng thứ nhất ghi 3 số M, N, K (1 ≤ M, N ≤ 500, 1 ≤ K ≤ 109)
	+ Dòng thứ i trong M dòng tiếp theo ghi N số nguyên không âm, số thứ j cho biết khối lượng cà rốt dự trữ trong thùng đặt tại ô (i, j). ( 1 ≤ Aij ≤ 104)
Dữ liệu ra: Ghi ra file CAROT.OUT 
Nếu không tồn tại cách lấy nào cho đủ bán thì in ra -1, ngược lại thì in ra: 
+ Dòng thứ nhất là số thùng ít nhất cần phải lấy.
+ Dòng tiếp theo ghi 4 số nguyên là tọa độ của góc trái trên và góc phải dưới của vùng cần lấy cà rốt. 
(Nếu nhiều vùng thỏa mãn thì in ra danh sách tọa độ theo thứ tự từ điển)
Ví dụ:
CAROT.INP
CAROT.OUT
3 3 10
1 2 2 
1 4 4
4 2 2
4 
1 2 2 3
(60% số test có n ≤ 50)
---------------------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........................................