Đề thi HSG cấp Cơ sở Tin học 11 - Năm học 2022-2023 - Sở GD&ĐT Bắc Giang (Có đáp án)

Nội dung tài liệu: Đề thi HSG cấp Cơ sở Tin học 11 - Năm học 2022-2023 - Sở GD&ĐT Bắc Giang (Có đáp án)

1. SỞ GD&ĐT BẮC GIANG ĐỀ THI HỌC SINH GIỎI CẤP CƠ SỞ CỤM THPT HUYỆN ................. NĂM HỌC 2022-2023 Môn thi: TIN HỌC 11 ĐỀ CHÍNH THỨC Thời gian làm bài: 150 phút (không kể thời gian giao đề) (Đề thi gồm 03 trang) Họ và tên thí sinh:.............................................................SBD:........................................ Tổng quan đề thi: Tên bài Bài 1 Bài 2 Bài 3 Bài 4 File chương trình Sodep Xaukitu Fibo Eiffel Dữ liệu vào Sodep.inp Dlnen.inp Fibo.inp Eiffel.inp Dữ liệu ra Sodep.out Dlnen.out Fibo.out Eiffel.out Điểm 7.0 6.0 4.0 3.0 - Bài thi được làm trên ngôn ngữ lập trình Pascal, Free Pascal, C++. - Thí sinh bắt buộc phải đặt tên file chương trình như trên và lưu vào thư mục có tên SBD của mình ví dụ: D:\04001. ĐỀ BÀI BÀI 1: SỐ ĐẸP (7 điểm) Một số nguyên dương được gọi là số đẹp nếu tổng bình phương các chữ số của nó là một số nguyên tố. Ví dụ: 12 là một số đẹp vì 12 + 22=5 là một số nguyên tố. Các số đẹp được đánh số thứ tự tăng dần của giá trị, bắt đầu từ 1. Yêu cầu: Cho số nguyên n (1<=n<=106). Hãy tìm số đẹp thứ n. Dữ liệu: Tệp văn bản SODEP.INP gồm nhiều dòng, các dòng tiếp theo mỗi dòng là một bộ kiểm thử chứa một số nguyên n. Kết quả: Ghi ra tệp văn bản SODEP.OUT là kết quả của mỗi bộ kiểm thử, mỗi bộ ghi trên một dòng. Ví dụ: SODEP.INP SODEP.OUT 1 11 6 23 BÀI 2: XÂU KÝ TỰ (6 điểm) Biết rằng thông tin được lưu trong máy tính dưới dạng file dữ liệu và được lưu trữ trên các thiết bị lưu trữ. Hiện nay lượng thông tin được đưa vào máy tính là rất lớn. Vì vậy con người liên tiếp nghĩ ra các cách để có thể lưu được lượng thông tin nhiều nhất, trong một thiết bị lưu trữ có dung lượng không đổi. Một trong các cách đó là nén dữ liệu theo một thuật toán như sau: Ví dụ xâu dữ liệu là: ‘aaaaabccc’ được nén thành ‘5ab3c’ ‘aaaaaaaaaaabbbcc’ được nén thành ‘11a3b2c’ Yêu cầu: Hãy viết chương trình pascal thực hiện phương pháp giải nén để có được xâu dữ liệu ban đầu trước khi nén. Dữ liệu vào: File DLNEN.INP có một dòng là một xâu nén chỉ có các kí tự chữ cái in thường và kí tự số. Kết quả: Ghi ra file DLNEN.OUT có một dòng là kết quả của xâu giải nén. Ví dụ: 1
2. DLNEN.INP DLNEN.OUT DLNEN.INP DLNEN.OUT 5ab3c aaaaabccc 11a3b2c aaaaaaaaaaabbbcc BÀI 3: FIBONACI (4 điểm) Dãy Fibonaci là dãy gồm các số: 1, 1, 2, 3, 5, 8, .... được xác định bởi công thức sau: F1=1, F2=1, Fi=Fi-1+Fi-2 với i>2. Yêu cầu: Hãy biểu diễn số nguyên dương X i thành tổng của ít nhất các số Fibonaci khác nhau. Dữ liệu: Từ tệp văn bản FIBO.INP gồm: - Dòng 1 là số nguyên dương N (N≤100) 100 - Từ dòng 2 đến dòng N+1 mỗi dòng chứa 1 số nguyên dương Xi (Xi≤10 , 1≤i≤N) Kết quả: Ghi ra file văn bản FIBO.OUT gồm N dòng, dòng i là biểu diễn tổng các số fibonaci theo thứ tự từ bé đến lớn của số Xi Ví dụ: FIBO.INP FIBO.OUT 3 19=1+5+13 19 129=1+5+34+89 129 8=8 8 BÀI 4: THÁP EIFFEL (3 điểm) Sắp đến Ngày Quốc tế Phụ nữ 8/3/2023 người ta dự định tổ chức một trò chơi cho những du khách thăm quan tháp Eiffel như sau: Mọi người được đưa lên máy bay lượn một vòng thăm thành phố Paris, sau đó nhảy dù xuống đỉnh của tháp, rồi đi từ đỉnh xuống dưới mặt đất qua các cầu thang nối các phòng ở tầng trên xuống các phòng ở tầng dưới. Biết rằng trong quá trình đi xuống thì ở một phòng bất kì du khách chỉ có thể đi từ phòng này xuống một trong hai phòng bên dưới theo hướng cầu thang bên phải hoặc bên trái. Khi đi qua mỗi phòng du khách được tặng một phần quà có giá trị X nào đó. Hình sau thể hiện một cách xếp giá trị quà trên tháp có 7 tầng. Đỉnh 3 Tầng 6 3 6 Tầng 5 5 1 4 Tầng 4 2 7 4 4 Tầng 3 4 4 2 6 5 Tầng 2 6 9 5 7 5 5 Tầng 1 1 7 4 1 4 4 6 Yêu cầu: Hãy viết một chương trình hướng dẫn du khách cách đi thăm các phòng khi đi từ đỉnh tháp xuống mặt đất sao cho tổng giá trị của các phần quà du khách nhận được là lớn nhất. Dữ liệu vào: File EIFFEL.INP + Dòng đầu tiên là số nguyên N ghi số lượng tầng của tháp tính cả đỉnh. + N dòng tiếp theo, dòng thứ i ghi i số nguyên ứng với giá trị của món quà. Kết quả: Ghi ra file EIFFEL.OUT chỉ ghi một số duy nhất là tổng giá trị các phần quà theo cách đi mà du khách lựa chọn. 2
3. Ví dụ: EIFFEL.INP EIFFEL.OUT EIFFEL.INP EIFFEL.OUT 4 17 7 38 1 3 1 2 3 6 3 4 5 5 1 4 6 7 8 9 2 7 4 4 4 4 2 6 5 6 9 5 7 5 5 1 7 4 1 4 4 6 -----Hết----- 3