Đề khảo sát HSG Tin học 11 - Bảng B - Năm học 2023-2024

Nội dung text: Đề khảo sát HSG Tin học 11 - Bảng B - Năm học 2023-2024

1. ĐỀ KHẢO SÁT ĐỘI TUYỂN HỌC SINH GIỎI BẢNG B NĂM HỌC 2023 - 2024 ĐỀ THI MÔN: TIN HỌC Thời gian làm bài: 180 phút (Đề gồm 03 trang) Ngày thi: 14/10/2023 TỔNG QUAN ĐỀ THI File nguồn nộp File dữ liệu File kết quả Biểu điểm Bài 1 BAI1.* BAI1.INP BAI1.OUT 6 điểm Bài 2 BAI2.* BAI2.INP BAI2.OUT 6 điểm Bài 3 BAI3.* BAI3.INP BAI3.OUT 8 điểm Bài 4 BAI4.* BAI4.INP BAI4.OUT 10 điểm Chú ý: - Bài thi được làm trên máy vi tính; - Dấu * là PAS, CPP hoặc PY tương đương với ngôn ngữ PASCAL, C++ hoặc PYTHON; - Học sinh đặt tên file chương trình theo đúng quy định của từng bài, không ghi bất kỳ thông tin cá nhân nào vào file bài làm (họ tên, số báo danh, ngày sinh, trường, các ký hiệu khác thường,..); - Trong quá trình làm, thường xuyên lưu bài vào đĩa cứng tránh sự cố mất điện đột ngột, có thể mất bài; - File input và output ở trong thư mục hiện hành, thí sinh không phải khai báo đường dẫn đến file input và output. BÀI 1. Rút gọn xâu Trong một văn bản thuần túy người ta chỉ dùng các chữ cái Latin in hoa ( ÷ 푍). Bạn Dương xem qua văn bản nhận thấy có nhũng vị trí liền kề nhau trong văn bản chứa những ký tự giống hệt nhau. Bạn Dương cho rằng các ký tự đó có thể viết rút gọn lại bởi số lần lặp của chúng để tiết kiệm dụng lượng lưu trữ trên bộ nhớ ngoài đồng thời có thể che dấu được thông tin gốc cũng như hạn chế được phần nào những người tò mò có thể đọc được. Ví dụ: AAAAAAAABBAABABB có thể viết gọn lại là: 8A2B2A1B1A2B. Yêu cầu: Em hãy giúp bạn Dương rút gọn văn bản nói trên. Dữ liệu: vào từ tệp văn bản BAI1.INP gồm 푛 + 1 đòng: + Dòng đầu là một số nguyên dương 푛 (1 ≤ 푛 ≤ 100); + 푛 dòng sau, mỗi dòng ghi một xâu có độ dài không quá 255 ký tự. Kết quả: ghi ra tệp văn bản BAI1.OUT gồm 푛 dòng, mỗi dòng ghi xâu rút gọn của xâu tương ứng trong file Input. Ví dụ: BAI1.INP BAI1.OUT Giải thích 1 8A2B2A1B1A2B AAAAAAAABBAABABB 2 7A2B2A1B1A1B AAAAAAABBAABAB 7A2B2A1B1A5B AAAAAAABBAABABBBBB BÀI 2. TỈA CÂY Làng XYZ có một con đường, trên đường này có trồng 푛 cây làm bóng mát được đánh số theo thứ tự lần lượt từ 1 đến 푛 và có giá trị lần lượt là 1, 2, 푛. Sau một thời gian dài các cây phát triển tán của chúng đan xen vào nhau. Người dân nơi đây lo sợ rằng cứ để như vậy dễ phát sinh sâu bệnh hơn nữa vào mùa mưa bão có thể gẫy cành, ngã đổ gây bất lợi cho việc lao động sản xuất và giao thương, lo lắng của người dân được trình lên Trưởng làng. Sau thời gian suy xét Trưởng làng đã quyết định tỉa bớt các cây theo nguyện vọng của người dân. Tuy nhiên, sau khi tỉa Trưởng làng muốn giữ lại một số cây để làm bóng mát cho con đường thỏa mãn các điều kiện sau: Trang 1/3
2. + Cây thứ phải được giữ lại; + Các cây có số thứ tự lớn hơn phải có giá trị lớn hơn; + Số lượng cây giữ lại là nhiều nhất có thể. Yêu cầu: Hãy giúp Trưởng làng thực hiện điều đó. Dữ liệu: Vào từ file văn bản BAI2.INP có cấu trúc như sau: + Dòng thứ nhất chứa số nguyên dương 푛 và (0 < ≤ 푛 ≤ 104); 9 + Các dòng tiếp theo chứa dãy số nguyên dương 1, 2, 푛. ( 푖 ≤ 10 ; 푖 = 1,2, 푛). Kết quả: Ghi ra file văn bản BAI2.OUT số nguyên dương duy nhất là số lượng cây giữ lại nhiều nhất thỏa mãn các yêu cầu trên. Ví dụ: BAI2.INP BAI2.OUT GIẢI THÍCH 7 1 4 - Giữ lại các cây có giá trị là 3 7 8 9 (4 cây) 3 7 2 8 6 9 5 7 3 5 - Giữ lại các cây có giá trị là 3 4 8 (3 cây); 3 7 4 - Giữ lại các cây có giá trị là : 3 4 5 6 9 (5 cáy). 8 5 6 9 Chú ý: 5 ✓ 70% số test tương ứng với 70% số điểm có푛 ≤ 1.000, ≤ 500; 푖 ≤ 10 ; 9 ✓ 30% số test tương ứng với 30% số điểm có 푛 ≤ 10.000, ≤ 5.000; 푖 ≤ 10 . BÀI 3. Đoạn con Cho một dãy gồm 푛 số nguyên = ( 1, 2, , 푛). Ta định nghĩa: đoạn con của dãy là một dãy các phần tử liên tiếp nhau thuộc A. Hoặc có thể viết ( 푖, 푖+1, , 푗) là một đoạn con của A với 푖 ≤ 푗. Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là 푗 − 푖 + 1. Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy . Dữ liệu: Vào từ file văn bản BAI3.INP gồm: + Dòng đầu chứa số nguyên dương 푛 (1 ≤ 푛 ≤ 105); 9 + Dòng tiếp theo chứa 푛 số nguyên 1, 2, . , 푛. (|ai| ≤ 2.10 ). Kết quả: Ghi ra file văn bản BAI3.OUT gồm một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài. Ví dụ: BAI3.INP BAI3.OUT GIẢI THÍCH 8 2 Có Min, Max tại các vị trí: 1 3 6 2 8 1 3 8 1, 5 vậy độ dài là 5; 1, 8 vậy độ dài là 8; 6, 5 vậy độ dài là 2; 6, 8 vậy độ dài là 3; Vậy độ dài bé nhất là 2. Chú ý: ✓ 75% số test tương ứng với 60% số điểm có 푛 ≤ 10.000, ≤ 105; ✓ 25% số test tương ứng với 30% số điểm có 푛 ≤ 100.000, ≤ 2.109. Trang 2/3
3. BÀI 4. Trung bình lớn nhất. Cho số nguyên dương n và dãy số 1, 2, 3, . Gọi đoạn con [ , 푣] của dãy là các phần tử liên tiếp , +1, +2, 푣 ( ≤ 푣). Dễ thấy đoạn con [ , 푣] có độ dài là 푣 − + 1 và giá trị trung bình là: A + A + A + ⋯ + A u u+1 u+2 v v − u + 1 Yêu cầu: Cho số nguyên 퐾, hãy xác định đoạn con có độ dài không nhỏ hơn 퐾 có giá trị trung bình lớn nhất. Dữ liệu vào từ file văn bản BAI4.INP: + Dòng đầu chứa 2 số nguyên dương , 퐾; 9 + Dòng thứ 2 chứa n số nguyên 1, 2, . (| 푖 | ≤ 10 , 1 ≤ 푖 ≤ ), các số được phân tách nhau bởi dấu cách. Kết quả ghi ra file văn bản BAI4.OUT một số thực duy nhất là giá trị trung bình (làm tròn đến chữ số thứ 3 sau dấu chấm thập phân). BAI4.INP BAI4.OUT Giải thích 4 2 10.333 Đoạn con có giá trị trung bình lớn nhất thỏa mãn 17 0 14 1 là đoạn [1,3] với các giá trị 17, 0, 14. 5 1 8.000 Đoạn con có giá trị trung bình lớn nhất thỏa mãn 2 8 -1 4 5 là đoạn [2,2] với giá trị là 8. Chú ý: ✓ 20% số test tương ứng với 20% điểm có ≤ 400, 퐾 = 1; ✓ 30% số test tương ứng với 30% điểm có 1 < 퐾 ≤ ≤ 400; ✓ 30% số test tương ứng với 30% điểm có 1 < 퐾 ≤ ≤ 5.103; ✓ 20% số test còn lại tương ứng với 20% số điểm có 1 < 퐾 ≤ ≤ 2. 105. --------- Hết --------- (Thí sinh không sử dụng tài liệu, Internet, cán bộ coi thi không cần giải thích gì thêm) Họ tên thí sinh.................................................................Số báo danh................................................. Cán bộ coi thi số 1................................................Cán bộ coi thi số 2................................................. Trang 3/3