Đề thi HSG Cấp Cơ sở Tin học 11 - Mã đề 111 - Năm học 2020-2021 - Cụm Huyện THPT Huyện Lạng Giang (Có đáp án)

Nội dung tài liệu: Đề thi HSG Cấp Cơ sở Tin học 11 - Mã đề 111 - Năm học 2020-2021 - Cụm Huyện THPT Huyện Lạng Giang (Có đáp án)

1. SỞ GD & ĐT BẮC GIANG ĐỀ THI CHỌN HỌC SINH GIỎI CẤP CƠ SỞ CỤM THPT HUYỆN LẠNG GIANG NĂM HỌC 2020 – 2021 Ngày thi: 23/01/2021 ĐỀ CHÍNH THỨC Môn thi: TIN HỌC - LỚP 11 (Đề thi có 03 trang) Thời gian: 150 phút (không kể thời gian phát đề) TỔNG QUAN VỀ BÀI THI Tên tệp Tên tệp Tên tệp Bài Tên bài chương trình dữ liệu vào dữ liệu ra 1 Số DMT DMT.pas DMT.INP DMT.OUT 2 Dãy số WAVIO WAVIO.PAS WAVIO.INP WAVIO.OUT 3 Điểm thưởng MARKA.INP MARKA.INP MARKA.INP 4 Tần số xuất hiện Tanso.PAS Tanso.INP Tanso.OUT Bài 1 Số DMT (6 điểm) Một số nguyên dương n được gọi là số DMT nếu n thỏa mãn hai tính chất sau: 1) n chia hết cho 3; 2) n có đúng 9 ước số. Người ta muốn khảo sát mật độ các số DMT nên nhờ các bạn tham gia thi chọn học sinh giỏi Trại hè Hùng Vương lập trình giải quyết bài toán sau: “Cho hai số nguyên không âm a,b, hãy đếm số lượng số DMT trong đoạn [a;b].” Dữ liệu: Vào từ file văn bản DMT.INP: - Dòng đầu chứa số nguyên T là số bộ dữ liệu; - T dòng sau, mỗi dòng chứa hai số nguyên dương a, b. Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản DMT.OUTgồm T dòng, mỗi dòng là số lượng số DMT trong đoạn [a;b] tương ứng với bộ dữ liệu vào. Ví dụ: DMT.INP DMT.OUT 2 0 1 10 1 220 230 Ràng buộc: • Có 25% số test ứng với 25% số điểm của bài có a,b<=103; T=1; • Có 25% số test ứng với 25% số điểm của bài có a,b<=103; T<=1000; • Có 25% số test khác ứng với 25% số điểm của bài a,b<=106; T=1; • Có 25% số test khác ứng với 25% số điểm còn lại của bài có a,b<=1012; T<=106. Bài 2. Dãy số WAVIO (7 điểm) Dãy sô Wavio là dãy số nguyên thoả mãn các tính chất: Số lượng phần tử (độ dài của dãy) L là lẻ tức là L=2*N+1, N+1 phần tử đầu tiền là một dãy tăng ngặt, N+1 phần tử cuối là một dãy giảm ngặt. Ví dụ, dãy số 1, 2, 3, 4, 5, 4, 3, 2, 0 là dãy Wavio có độ dài 9 còn dãy 1, 2, 3, 4, 5, 4, 3, 2, 2 khoog phải là dãy Wavio 1
2. Yêu cầu: Cho dãy số nguyên có độ dài N, hãy tìm dãy con Wavio có độ dài lớn nhất từ dãy đã cho. Ví dụ: cho dãy 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 1, 5, 4, 1, 2, 3, 2, 2, 1. Dãy con Wavio dài nhất là 1, 2, 3, 4, 5, 4, 3, 2, 1 và có độ dài 9. Dữ liệu vào từ file văn bản WAVIO.INP gồm nhiều Tests mỗi test cho trên 2 dòng: Dòng thứ nhất chứa số nguyên N (0<N≤10000) dòng thứ 2 chứa N số nguyên, các số cách nhau một dấu cách. Kết quả đưa ra file văn bản WAVIO.OUT độ dài của dãy con Wavio dài nhất. Mỗi số trên một dòng. Ví dụ: WAVIO.INP WAVIO.OUT 10 9 1 2 3 4 5 4 3 2 10 9 19 1 1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1 5 1 2 3 4 5 Bài 3. Điểm thưởng (4 điểm) Cho hai dãy A gồm N số nguyên a 1, a2, , aN và dãy B gồm M số nguyên b1, b2, , bN không giảm. Với mỗi b j, ai (|ai|, |bj| ≤ 10^9; i=1..N và j=1..M) nếu a i > bj thì A được thưởng một điểm. Yêu cầu: Hãy xác định xem nếu xét toàn bộ phần tử của dãy A với mọi phần tử của dãy B thì A thu được tối đa bao nhiêu điểm. Input: Dòng 1 chứa 2 số N và M, dòng 2 ghi N số của dãy A và dòng 3 ghi M số của dãy B. Output: Ghi số duy nhất là đáp án của bài. Chú ý: -Subtask 1: N,M ≤ 103 với 60% điểm; -Subtask 2: N,M ≤ 105 với 80% điểm; -Subtask 3: N,M ≤ 106 với 100% điểm. MARKA.INP MARKA.OUT 3 2 3 5 6 9 5 7 Bài 4. Tần số xuất hiện – TANSO.PAS (3 điểm). Cho xâu S có độ dài không quá 10000 kí tự gồm các chữ cái tiếng Anh. Tần số xuất hiện của chữ cái ch trong xâu S đúng bằng số lần xuất hiện của nó trong xâu S (các kí tự không phân biệt chữ hoa hay chữ thường). Ví dụ xâu S = ‘abgABa’ thì tần số xuất hiện của chữ cái A là 3, của chữ cái B là 2, của chữ cái G là 1. Yêu cầu: Đếm số chữ cái tiếng Anh có trong xâu S có tần số xuất hiện lớn hơn hay bằng số nguyên K cho trước? Dữ liệu vào: Đọc từ tệp văn bản TANSO.INP có cấu trúc: • Dòng 1 chứa số nguyên dương K (K<=10000). 2
3. • Dòng 2 chứa xâu S. Kết quả: ghi ra tệp văn bản TANSO.OUT gồm một số duy nhất tương ứng là số chữ cái tiếng Anh có trong xâu S có tần số xuất hiện lớn hơn hoặc bằng K. Ví dụ: Trong ví dụ cho dưới đây, có 4 chữ cái A,B,C,D có tần số xuất hiện lớn hơn hoặc bằng 3 TANSO.INP TANSO.OUT 3 4 aBAgbCccdDBadAce HẾT 3