1 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 2016-2017
¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
ĐỀ 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: 17/9/2016
¯¯¯¯¯¯¯¯¯¯¯¯
Đề thi này có 02 trang
TỔNG QUAN NGÀY THI THỨ NHẤT
Câu Tên câu File chương trình File dữ liệu vào File kết quả 1 Tổng ma trận TongMT.* TongMT.inp TongMT.out 2 Xâu kí tự XauKiTu.* XauKiTu.inp XauKiTu.out 3 Băng nhạc BangNhac.* BangNhac.inp BangNhac.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++. 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) Tổng ma trận
Một ma trận A cấp m x n các số nguyên (mỗi số hạng trên cùng một hàng được cách nhau bằng dấu cách). Tính tổng các số hạng trên mỗi hàng của ma trận?
Dữ liệu vào trong tập tin văn bản TongMT.inp
- Dòng đầu tiên chứa hai số m và n tương ứng với số hàng và số cột của ma trận.
- m hàng tiếp theo là số hạng các hàng của ma trận Kết quả xuất ra tập tin văn bản TongMT.out
Gồm m hàng, số cuối cùng của mỗi hàng là giá trị tổng các số hạng của hàng đó.
Ví dụ: TongMT.inp TongMT.out
3 4 1 3 5 7 2 4 6 8 0 3 2 6
1 3 5 7 16 2 4 6 8 20 0 3 2 6 11
2 Câu 2: (7,0 điểm) Xâu kí tự
Xâu kí tự bao gồm cả các chữ số được lưu trong tập tin văn bản XauKiTu.inp. Sắp xếp lại các số nằm xen kẽ trong xâu theo thứ tự từ nhỏ đến lớn nhưng vị trí của các kí tự khác số vẫn giữ nguyên. Kết quả được ghi trong tập tin văn bản XauKiTu.out.
Chú ý: Khi sắp xếp nếu gặp số bắt đầu bằng chữ số 0 thì cắt bỏ các chữ số 0 vô nghĩa đó (ví dụ số 021 thì sau khi sắp xếp chỉ viết lại thành số 21).
Ví dụ: XauKiTu.inp XauKiTu.out
xyz25av4ghit012m58no xyz4av12ghit25m58no
Câu 3: (7,0 điểm) Băng nhạc
Một máy phát nhạc tự động có một băng nhạc đủ lớn để ghi N bài hát, thời gian phát mỗi bài hát tính theo phút và được biết trước. Biết rằng, để phát bài thứ i thì máy phải trở về vị trí đầu băng và phải quay để bỏ qua i – 1 bài trước đó. Máy có thể trở về vị trí đầu băng với thời gian không đáng kể và thời gian quay băng để bỏ qua mỗi bài và thời gian phát bài đó là bằng nhau.
Hãy tìm cách ghi các bài hát trên băng nhạc sao cho tổng số thời gian quay băng trong ngày là nhỏ nhất. Biết rằng, mỗi bài hát được phát một lần.
Chẳng hạn: Băng nhạc có 3 bài hát có thứ tự là 1, 2, 3 với thời gian phát mỗi bài lần lượt là 3, 2 và 6 phút. Nếu ta ghi băng nhạc theo các thứ tự khác nhau thì tổng thời gian phát cả băng nhạc là khác nhau, cụ thể là:
Thứ tự bài hát Thời gian phát mỗi bài Tổng thời gian phát
1 2 3 3 2 6 3 + (3 + 2) + (3 + 2+ 6) = 19
Dữ liệu vào trong tập tin văn bản BangNhac.inp:
- Dòng thứ nhất chứa số N (N ≤ 100)
- Các dòng tiếp theo chứa các số nguyên t1, t2,…,tN lần lượt là thời gian phát của các bài hát 1, 2,..., N. Các số cách nhau ít nhất một dấu cách.
Kết quả xuất ra tập tin văn bản BangNhac.out:
- Dòng thứ nhất ghi số Tmin là tổng thời gian tìm và phát cả băng nhạc.
- Các dòng tiếp theo chứa N số là thứ tự của các bài hát ghi trên băng nhạc theo thời gian Tmin, các số cách nhau ít nhất một dấu cách.
Ví dụ: BangNhac.inp BangNhac.out
3 3 2 6
18 2 1 3
--- HẾT ---