Đề thi chọn Học sinh giỏi cấp tỉnh môn Tin học - Bảng B - Năm học 2019-2020 - Sở Giáo dục và đào tạo tỉnh Quảng Ninh (Có đáp án)

Nội dung text: Đề thi chọn Học sinh giỏi cấp tỉnh môn Tin học - Bảng B - Năm học 2019-2020 - Sở Giáo dục và đào tạo tỉnh Quảng Ninh (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT NĂM 2019 TỈNH QUẢNG NINH Môn thi:TIN HỌC - Bảng B Ngày thi: 03/12/2019 ĐỀ THI CHÍNH THỨC Thời gian làm bài: 180 phút, không kể thời gian giao đề (Đề thi này có 02 trang) TỔNG QUAN VỀ BÀI THI Bài Bài 1 Bài 2 Bài 3 File chương trình TONGUOC.* XAU.* DAYSO.* File dữ liệu vào TONGUOC.INP XAU.INP DAYSO.INP File kết quả TONGUOC.OUT XAU.OUT DAYSO.OUT Giới hạn thời gian 1 giây / test 1 giây / test 1 giây / test Giới hạn bộ nhớ 1024 MB 1024 MB 1024 MB 7 điểm 7 điểm 6 điểm Điểm Tổng 20 điểm 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++. Hãy lập trình giải các bài toán sau: Bài 1. Tổng các ước Cho 2 số nguyên dương x và y. Bạn hãy viết chương trình tính tổng các ước nguyên dương của từng số và tìm tổng lớn hơn trong hai tổng đó, nếu hai tổng có giá trị bằng nhau thì tổng lớn hơn là giá trị bằng nhau đó. Dữ liệu: Vào từ tệp TONGUOC.INP gồm một dòng ghi hai số nguyên dương x và y viết cách nhau một dấu cách (1 ≤ x, y ≤ 1012). Kết quả: Ghi ra tệp TONGUOC.OUT trên một dòng, một số nguyên dương theo yêu cầu bài toán. Ví dụ: TONGUOC.INP TONGUOC.OUT 10 11 18 12 12 28 Ràng buộc: • 50% số test ứng với 50% số điểm của bài có x, y ≤ 103. • 30% số test ứng với 30% số điểm của bài có x, y ≤ 107. • 20% số test ứng với 20% số điểm của bài có x, y ≤ 1012 . Bài 2. Xâu Cho số nguyên dương N và xâu S gồm các kí tự là chữ cái (a,b, ,z, A,B, ,Z) viết liền nhau. Chuẩn hóa xâu S bằng cách chuyển các kí tự chữ cái in thường thành các kí tự chữ cái in hoa. Ta quy ước kí tự ‘A’ xuất hiện đầu tiên trong xâu S có giá trị là 1, kí tự ‘A’ tiếp theo xuất hiện trong xâu S có giá trị là 2, kí tự ‘A’ tiếp theo xuất hiện trong xâu S có giá trị là 3, cứ như thế cho đến cuối xâu S; đối với các kí tự khác cũng quy ước tương tự. Sau đó tính tổng các giá trị đã được quy ước của xâu S. Chẳng hạn: Nếu S = ‘cAbbaCAaB’ thì chuẩn hóa S = ‘CABBACAAB’ và quy ước : - Kí tự ‘A’ xuất hiện 4 lần nên có các giá trị lần lượt là 1, 2, 3, 4; - Kí tự ‘B’ xuất hiện 3 lần nên có các giá trị lần lượt là 1, 2, 3; - Kí tự ‘C’ xuất hiện 2 lần nên có các giá trị lần lượt là 1, 2. Tổng các giá trị xuất hiện sẽ là 19. Yêu cầu: Hãy viết chương trình cho biết tổng các giá trị theo quy ước như trên có chia hết cho số nguyên dương N hay không. Nếu chia hết thì ghi ra tổng đó, nếu không chia hết thì ghi ra số lượng các chữ cái khác nhau của xâu S sau khi chuẩn hóa. Trang 1/2
2. Dữ liệu: Vào từ tệp XAU.INP gồm 2 dòng • Dòng 1 chứa số nguyên dương N (1 ≤ N ≤ 106). • Dòng 2 chứa xâu S (không quá 100000 kí tự). Kết quả: Ghi ra tệp XAU.OUT trên một dòng, một số tự nhiên thỏa mãn yêu cầu của bài toán. Ví dụ: XAU.INP XAU.OUT Giải thích 5 10 Sau khi chuẩn hóa, tổng theo quy ước là 10 và chia hết cho AbaCcA 5. Ghi ra 10. 6 4 Sau khi chuẩn hóa, tổng theo quy ước là 9 và không chia gZtAgG hết cho 6. Ghi ra 4 là số kí tự chữ cái khác nhau của xâu S. Ràng buộc: • Có 40% sấ test ấng vấi 40% sấ điấm cấa bài vấi xâu S chấ xuất hiấn ít nhất mất trong các kí tấ a, b, c hoấc A, B, C; và đấ dài xâu S tấi đa là 1000 kí tấ. • Có 40% sấ test ấng vấi 40% điấm cấa bài vấi xâu S tấi đa là 1000 kí tấ. • Có 20% sấ test ấng vấi 20% điấm cấa bài vấi xâu S có đấ dài tấi đa 100000 kí tấ. Bài 3. Dãy số Cho dãy số A có N số nguyên a1, a2, , aN . Một dãy con liên tiếp các số hạng của dãy A là dãy các số hạng từ số hạng a i đến số hạng a j (1 ≤ i ≤ j ≤ N). Hãy cho biết dãy A có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương S cho trước. Dữ liệu: Vào từ tệp DAYSO.INP gồm 2 dòng • Dòng 1 chấa hai sấ nguyên dương N và S (N ≤ 105 , S ≤ 1014). 9 • Dòng 2 chấa N sấ nguyên a1, a2, , aN (|ai| ≤ 10 ). Các sấ trên cùng mất dòng đưấc ghi cách nhau ít nhất mất dấu cách. Kết quả: Ghi ra tệp DAYSO.OUT trên một dòng, một số nguyên duy nhất là số dãy con liên tiếp thỏa mãn yêu cầu của bài toán. Ví dụ: DAYSO.INP DAYSO.OUT Giải thích 5 10 5 Các dãy con liên tiếp có giá trị tuyệt đối của tổng lớn hơn 10 là: -5 5 6 2 6 {5; 6}, {5; 6; 2}, {6; 2; 6}, {5; 6; 2; 6}, {-5; 5; 6; 2; 6} 4 4 6 Các dãy con liên tiếp có giá trị tuyệt đối của tổng lớn hơn 4 là: 5 -1 8 -5 {5}, {8}, {-5}, {-1; 8}, {5; -1; 8}, {5; -1; 8; -5} Ràng buộc: • Có 30% số test ứng với 30% số điểm của bài có N ≤ 100. • Có 50% test khác ứng với 50% số điểm của bài có N ≤ 103. • Có 20% test còn lại ứng với 20% số điểm của bài có N ≤ 105. Hết - Thí sinh không được sử dụng tài liệu; - Cán bộ coi thi không giải thích gì thêm; Họ và tên thí sinh: Số báo danh: Chữ kí của cán bộ coi thi 1: Chữ kí của cán bộ coi thi 2: . Trang 2/2