SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
SÓC TRĂNG Năm học 2015-2016
Đề chính thức
Môn: Tin học - Lớp 12
(Thời gian làm bài 180 phút, không kể phát đề)
Ngày thi: 27/9/2015
________________
Đề thi này có 02 trang
TỔNG QUAN NGÀY THI THỨ HAI
Tên câu
File chương trình
File dữ liệu vào
File kết quả
Câu 1
Đoạn không giảm
DoanMax.*
DoanMax.inp
Câu 2
Tổng hàng lẻ
TongHangLe.*
TongHangLe.inp
TongHangLe.out
Câu 3
Dãy con K
DayConK.*
DayConK.inp
DayConK.out
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng
là Pascal hoặc C++. Lưu ý: Yêu cầu đặt tên file giống bảng trên.
Hãy lập trình giải các câu hỏi sau:
Câu 1: (6,0 điểm) Đoạn không giảm
Cho dãy gồm N số nguyên (1 N 20000). Tìm đoạn không giảm có chiều dài lớn
nhất. (đoạn không giảm phải chứa các phần tử liên tục)
Dữ liệu vào trong tập tin văn bản DoanMax.inp
- Dòng 1: số nguyên N (1 N 20000).
- Dòng thứ 2: các phần tử của dãy, các phần tử này cách nhau bằng khoảng trắng.
Kết quả xuất ra tập tin văn bản DoanMax.out
- Dòng 1: chứa chỉ số bắt đầu đoạn.
- Dòng 2: chứa số phần tử trong đoạn (chiều dài đoạn).
Ví dụ :
DoanMax.inp
DoanMax.out
12
7 5 15 1 3 3 3 5 7 9 5 2
Vi tri bat dau cua doan: 4
So phan tu trong doan: 7
Câu 2: (7,0 điểm) Tổng hàng lẻ
Cho một ma trận M x N số nguyên (M, N ≤ 200). Hãy tính tổng số lẻ của từng hàng
ma trận, sau đó sắp xếp giảm dần theo các giá trị tổng đó.
Dữ liệu vào trong tập tin văn bản TongHangLe.inp
- Dòng 1: chứa 2 số nguyên M, N cách nhau bởi khoảng trắng.
- M dòng tiếp theo chứa M hàng ma trận gồm N số nguyên, các số cách nhau bằng
khoảng trắng.
Kết quả xuất ra tập tin văn bản TongHangLe.out
- Dòng 1: chứa số nguyên M.
- M dòng tiếp theo chứa M tổng các số lẻ của M hàng.
- Dòng cuối cùng chứa tổng M số được sắp xếp giảm dần của tổng M hàng, các số
cách nhau bằng khoảng trắng.
Ví dụ:
TongHangLe.inp
TongHangLe.out
5 4
3 2 -1 5
5 7 -8 10
-4 -3 1 3
2 -4 -1 7
-5 1 13 -5
Tong cua 5 hang
Tong hang thu 1 = 7
Tong hang thu 2 = 12
Tong hang thu 3 = 1
Tong hang thu 4 = 6
Tong hang thu 5 = 4
Tong cac so giam dan: 12 7 6 4 1
Câu 3: (7,0 điểm) Dãy con K
Cho một dãy A gồm N số nguyên dương (1 ≤ N ≤ 1000) có dạng A1, A2, …, AN và
số nguyên dương K (K ≤ 1000). Hãy tìm dãy con gồm nhiều phần tử nhất của dãy đã cho
sao cho tổng các phần tử của dãy con này chia hết cho K. (dãy con tìm được có thể chứa các
phần tử không liên tục trong dãy đã cho)
Dữ liệu vào trong tập tin văn bản DayConK.inp
- Dòng 1: N, K cách nhau bằng khoảng trắng.
- Dòng 2: chứa N số A1, A2, …, AN cách nhau bằng khoảng trắng.
Kết quả xuất ra tập tin văn bản DayConK.out
- Dòng 1: số lượng phần tử tìm được.
- Các dòng tiếp ghi các phần tử được chọn vào dãy con.
- Dòng cuối ghi tổng các phần tử của dãy con đó.
Ví dụ:
DayConK.inp
DayConK.out
10 7
1 9 11 5 10 21 7 2 4 8
So luong phan tu tim duoc: 9
A[1] = 1
A[2] = 9
A[3] = 11
A[4] = 5
A[5] = 10
A[6] = 21
A[7] = 7
A[8] = 2
A[9] = 4
Tong cac phan tu cua day tim duoc: 70
--- HẾT ---
Họ tên thí sinh: ................................................................Số báo danh: ................................
Chữ ký của Giám thị 1: ..................................Chữ ký của Giám thị 2:.................................