Đề thi thử môn Tin học - Kỳ thi chọn học sinh giỏi Lớp 11 cấp tỉnh - Năm học 2016-2017 - Trường THPT Nghi Lộc 3

Nội dung text: Đề thi thử môn Tin học - Kỳ thi chọn học sinh giỏi Lớp 11 cấp tỉnh - Năm học 2016-2017 - Trường THPT Nghi Lộc 3

1. Trường THPT Nghi Lộc 3 KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11 CẤP THPT Đề thi thử NĂM HỌC 2019 - 2020 Môn thi: TIN HỌC ĐỀ CHÍNH THỨC Thời gian: 150 phút (không kể thời gian giao đề) Họ và tên thí sinh: Số báo danh: TỔNG QUAN ĐỀ THI Bài Tên bài File chương trình File dữ liệu File kết quả Thời gian 1 COVID-19 COVID-19.* COVID-19.INP COVID-19.OUT 1 giây 2 DODO DODO.* DN.INP DN.OUT 1 giây 3 HAI GIÁ TRỊ TWOVALS.* TWOVALS.INP TWOVALS.OUT 1 giây 4 ĐẾM SỐ NM.* NM.INP NM.OUT 1 giây Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình sử dụng tương ứng là Pascal hoặc C++ Bài 1: COVID-19 Trong khi dịch bệnh covid-19 đang diến biết phức tập, theo các nhà chuyên môn thì cứ 1 người nhiễm bệnh có thể lây lan cho n người khi có tiếp xúc gần với người nhiệm bệnh đó, với trường hợp lây thế này được gọi là lây thế hệ F1, mỗi người trong n người nhiễm bệnh F1 đó lại tiếp xúc gần với n người khác, lây trường hợp này gọi là lây thế hệ F2, tương tự có F3, F4, Fm. Em hãy viết chương trình cho biết số người lây nhiễm virut tối đa có thể mắc phải ở thế hệ Fm, cho biết số người tiếp xúc gần trong mỗi thế hệ lây là n người , với m,n là các sô nguyên dương cho trước và không vượt qua 100. DỮ LIỆU VÀO Từ tệp COVID_19.INP: là 2 số nguyên dương m,n ghi theo thứ tự trên một dòng cách nhau 1 dấu cách DỮ LIỆU RA Từ tệp COVID_19.OUT: Là số người lây nhiễm cao nhất có thể COVID_19.UNP COVID_19.OUT 2 3 13 Bài 2(6 điểm) ĐỘ ĐO Hai xâu ký tự được gọi là đảo của nhau nếu ta có thể hoán vị các ký tự của một xâu để được xâu còn lại. Ví dụ: xâu “occurs” là đảo của xâu “succor”, tuy nhiên xâu “dear” không phải là đảo của xâu “dared” (vì chữ ‘d’ xuất hiện 2 lần trong “dared” nhưng chỉ xuất hiện trong “dear” 1 lần). Độ đo giữa hai xâu ký tự là số ký tự ít nhất cần phải xóa (trên cả hai xâu) để hai xâu còn lại đảo của nhau. Ví dụ độ đo giữa hai xâu “sleep” và “leap” là 3, độ đo giữa hai xâu “dog” và “cat” là 6. Yêu cầu: Hãy tính độ đo giữa hai xâu cho trước. Dữ liệu: Vào từ file văn bản AD.INP gồm hai dòng, mỗi dòng chứa một xâu ký tự chỉ gồm các chữ cái tiếng Anh thường, mỗi dòng có không quá 1 triệu ký tự. Kết quả: Ghi ra file văn bản AD.OUT một số nguyên duy nhất là độ đo giữa hai xâu trong file dữ liệu. Ví dụ: AD.INP AD.OUT Begin 4 End Trang1
2. Hạn chế: 60% số test có độ dài của mỗi xâu không quá 255 ký tự. Hạn chế: - Có 50% số test ứng với 50% số điểm có n ≤ 105 và k = 1; - Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105; Bài 3(5 điểm) HAI GIÁ TRỊ Cho dãy số nguyên 1, 2, , . Tìm độ dài đoạn con dài nhất gồm các phần tử liên tiếp của dãy chỉ bao gồm hai giá trị khác nhau. Ví dụ dãy 1, 3, 2, 3, 3, 1, 2 thì đoạn con dài nhất cần tìm là 3, 2, 3, 3 độ dài 4 gồm hai giá trị là 2 và 3. Dữ liệu: Vào từ file văn bản TWOVALS.INP: Dòng đầu tiên ghi số nguyên (1 ≤ ≤ 106); 9 Dòng thứ hai ghi số nguyên 1, 2, , (1 ≤ 푖 ≤ 10 ). Kết quả: Ghi ra file văn bản TWOVALS.OUT một số nguyên duy nhất là độ dài đoạn con dài nhất chỉ bao gồm hai giá trị khác nhau theo phương án tìm được. Ví dụ TWOVALS.INP TWOVALS.OUT 7 4 1 3 2 3 3 1 2 Bài 4(4 điểm) ĐẾM SỐ An được Cô Hợi cho đi trại hè tập huấn Tin học tại vương quốc XYZ. Sau khi trở về An khoe với Cô dạy Tin mình đã trở thành chuyên gia lập trình máy tính. Cô dạy Tin không tin nên đã thử tài An bằng cách đưa ra hai số nguyên dương n, m rồi yêu cầu An đếm số lượng số nguyên dương có không quá n chữ số và tổng các chữ số bằng m. Loay hoay gần nửa tiếng đồng hồ mà An đếm chưa xong. Bạn hãy giúp An giải bài toán này nhé. Dữ liệu: Vào từ file văn bản NM.INP: Dòng đầu chứa số nguyên dương T (T ≤ 10) là số bộ dữ liệu; T dòng sau, mỗi dòng chứa hai số nguyên n, m; Kết quả: Ghi ra file văn bản NM.OUT: gồm T dòng, mỗi dòng là số lượng số nguyên dương có không quá n chữ số và tổng các chữ số bằng m tương ứng với bộ dữ liệu vào. NM.INP NM.OUT 1 2 2 1 Hạn chế: Có 50% số test có:n, m ≤ 12; Có 50% số test có:n, m ≤120. Các số trên một dòng của các file dữ liệu vào được ghi cách nhau bởi ít nhất một dấu cách Hết Trang2