Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 (Đề dự bị) - Bảng B - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có ma trận)

Nội dung text: Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 (Đề dự bị) - Bảng B - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có ma trận)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI GIA LAI LỚP 12 CẤP TỈNH (BẢNG B) NĂM HỌC 2019 - 2020 ĐỀ DỰ BỊ Môn thi: TIN HỌC (Đề thi có 04 bài, 03 trang) Thời gian: 180 phút (không kể thời gian phát đề) Ngày thi: 13/12/2019 TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Bài Tên bài chương trình dữ liệu vào dữ liệu ra 1 C3 C3.* C3.inp C3.out 2 HEIGHT Height.* Height.inp Height.out 3 QSUM Qsum.* Qsum.inp Qsum.out 4 CHƠI CHỮ Words.* Words.inp Words.out Lưu ý: - Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++. - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. - Khi hết thời gian làm bài, tại máy tính được sử dụng để làm bài thi, thí sinh tạo một thư mục với tên là số báo danh của mình và đặt các file bài làm (file chương trình .CPP hoặc .PAS) vào thư mục vừa tạo. Sau đó tiến hành ghi nội dung thư mục này vào đĩa CD dưới sự giám sát, hướng dẫn của Cán bộ coi thi và sự chứng kiến của một thí sinh nào đó tại phòng thi. Bài 1. C3 (6.0 điểm) Cho dãy số nguyên dương gồm N phần tử a 1 ,a 2 ,...,a N. In ra số lượng cặp (i,j) thỏa mãn: ▪ 1 ≤ i ≤ j ≤ N; 2 ▪a i + (aj) = K với K cho trước. + Dữ liệu vào: Tệp C3.inp có nội dung như sau: ▪ Dòng đầu gồm 2 số nguyên dương N và K (N ≤ 105, K ≤ 109); ▪ Dòng thứ hai gồm N số nguyên dương a1, a2, ... , aN (ai ≤ 500). + Dữ liệu ra: Tệp C3.out chứa một số nguyên là số lượng cặp (i,j) thỏa mãn. + Ví dụ: C3.inp C3.out 3 5 1 1 2 1 Trang 1/3
2. Bài 2. HEIGHT (4.0 điểm) Lớp 5/3 tại trường Tiểu học NOBEL có N học sinh, các học sinh được đánh số từ 1 đến N. Học sinh i có chiều cao là Ai. Với mỗi học sinh i từ 1 đến N, hãy đếm xem có bao nhiêu học sinh có chiều cao thấp hơn so với học sinh i. + Dữ liệu vào: Tệp Height.inp có nội dung như sau: ▪ Dòng đầu tiên gồm số nguyên N (1 ≤ N ≤ 105) - số học sinh trong lớp. ▪ Dòng thứ hai gồm một dãy N số nguyên A1, A2, , AN (50 ≤ Ai ≤ 250) - cho biết chiều cao của các học sinh. + Dữ liệu ra: Tệp Height.out chứa N số nguyên, số nguyên thứ i cho biết số học sinh có chiều cao thấp hơn học sinh i. Ví dụ Height.inp Height.out 4 0 1 2 3 110 120 130 140 + Giải thích: Trong ví dụ thứ nhất, có 2 học sinh có chiều cao thấp hơn học sinh 3 là học sinh 1 và học sinh 2. + Ràng buộc: ▪ Có 50% số điểm: N ≤ 103 ▪ Có 50% số điểm: Không có ràng buộc gì thêm Bài 3. QSUM (6.0 điểm) Trong lớp học của cô Quỳnh, Ngân là một học sinh vô cùng xuất sắc. Hôm nay, Ngân lại tiếp tục đứng nhất trong một cuộc thi Tin học giữa các trường, vì thế cô Quỳnh quyết định sẽ tặng Ngân một ít kẹo xem như phần thưởng. Cô Quỳnh có n viên kẹo được đánh số lần lượt từ 1 đến n. Viên kẹo thứ i có độ ngon Wi. Hôm nay, cô quyết định tặng Ngân k viên kẹo liên tiếp (1 ≤ k ≤ n) trong n viên kẹo. Mặc khác, vì Ngân rất xuất sắc nên cô Quỳnh muốn tổng độ ngon của những viên kẹo Ngân nhận được là lớn nhất. Em hãy giúp cô Quỳnh tính toán tổng độ ngon của những viên kẹo mà Ngân sẽ nhận được nhé! + Dữ liệu vào: Tệp Qsum.inp có nội dung như sau: ▪ Dòng đầu tiên chứa số nguyên dương n và k (k ≤ n ≤ 100000) là số lượng kẹo của cô Quỳnh. ▪ Dòng thứ i trong n dòng tiếp theo chứa duy nhất một số nguyên W i là độ ngon của viên kẹo 9 thứ i (1 ≤ Wi ≤ 10 ). + Dữ liệu ra: Tệp Qsum.out là kết quả bài toán. + Ràng buộc: ▪ 40% số test ứng với 40% số điểm có k ≤ n ≤ 10000. ▪ 60% số test còn lại ứng với 60% số điểm không có giới hạn gì thêm. Trang 2/3
3. + Ví dụ: QSUM.inp QSUM.out 5 2 8 4 3 2 6 1 + Giải thích ví dụ: Cô Quỳnh cần chọn 2 viên kẹo liên tiếp sao cho tổng độ ngon là lớn nhất, vì thế cô sẽ chọn viên kẹo thứ 3 và viên kẹo thứ 4. Bài 4. CHƠI CHỮ (4.0 điểm) Io và Ao chơi một trò chơi trên các từ. Họ chỉ nói các từ được tạo thành từ các nguyên âm với qui tắc chữ cái đầu tiên của từ được nói tiếp theo phải trùng với chữ cái cuối cùng của từ được nói trước đó. Không được sử dụng từ nào quá 2 lần và chỉ được dùng các từ có trong một từ điển cho trước. Điểm của trò chơi là tổng độ dài của các từ được nói ra. Viết chương trình xác định điểm lớn nhất của trò chơi nếu như chỉ sử dụng các từ có trong từ điển cho trước. + Dữ liệu vào: Tệp Words.inp có nội dung như sau: - Dòng đầu tiên chứa số tự nhiên N, 1<N<16 xác định số lượng các từ có trong từ điển. - N dòng tiếp theo mỗi dòng chứa 1 từ có trong từ điển. Mỗi từ là một dãy chỉ gồm các ký tự ‘A’, ‘E’, ‘T’, ‘O’, ‘U’. Độ dài của mỗi từ không vượ t quá 100. Tất cả các từ là khác nhau. + Dữ liệu ra: Tệp Words.out chứa một số nguyên duy nhất là điểm lớn nhất nhận được của trò chơi. + Ví dụ: WORDS.INP WORDS.OUT WORDS.INP WORDS.OUT WORDS.INP WORDS.OUT 3 8 4 13 5 16 AEIOU AEEEO IOO UIU OEOAEEE IUUO EO AO AI O OIOOI AOOI + Ràng buộc: Không có ràng buộc gì thêm. ----------HẾT---------- Họ và tên thí sinh........................................................Số báo danh:................................................... Họ và tên, chữ kí của CBCT1:....................................Họ và tên, chữ kí của CBCT2:....................... Lưu ý: - Thí sinh không được sử dụng tài liệu trong lúc làm bài. - Cán bộ coi thi không giải thích gì thêm. Trang 3/3