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 DoanMax.out 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:...
