Đề thi môn Tin học - Kỳ thi học sinh giỏi Lớp 9 - Năm học 2018-2019 - Sở GD&ĐT tỉnh Quảng Nam

Nội dung text: Đề thi môn Tin học - Kỳ thi học sinh giỏi Lớp 9 - Năm học 2018-2019 - Sở GD&ĐT tỉnh Quảng Nam

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI LỚP 9 TỈNH QUẢNG NAM Năm học 2018 - 2019 ĐỀ CHÍNH THỨC Môn thi : Tin học Thời gian : 150 phút (Không kể thời gian giao đề) (Đề thi này có 3 trang) Ngày thi : 04/4/2019 TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Thời Bài Tên bài Điểm chương trình dữ liệu vào dữ liệu ra gian 1 Số đẹp BEAUTY.* BEAUTY.INP BEAUTY.OUT 5 1s 2 Xóa ký tự LCS.* LCS.INP LCS.OUT 5 1s 3 Sắp xếp SORT.* SORT.INP SORT.OUT 5 1s dãy số 4 Phần quà LUCKY.* LUCKY.INP LUCKY.OUT 5 1s may mắn 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à Free Pascal hoặc C++. Bài 1. (5,0 điểm) Số đẹp 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ó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ. 12 là số đẹp vì 12 + 22 = 5 là số nguyên tố. Trong dãy số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1. Yêu cầu: Cho số nguyên dương n (1 ≤ 푛 ≤ 100000). Hãy tìm số đẹp thứ n. Dữ liệu: Vào từ file văn bản BEAUTY.INP gồm nhiều dòng, mỗi dòng là một bộ kiểm thử chứa một số nguyên dương n. Kết quả: Ghi ra file văn bản BEAUTY.OUT ghi kết quả của mỗi bộ kiểm thử, mỗi bộ được ghi trên một dòng. Ví dụ: BEAUTY.INP BEAUTY.OUT 1 11 6 23 Bài 2. (5,0 điểm) Xóa ký tự Khoa và Hiếu đang mải mê cùng nhau giải quyết một bài toán hấp dẫn. Mỗi người viết ra một xâu, chỉ gồm các ký tự latinh in thường từ ‘a’ đến ‘z’. Sau đó hai bạn cố gắng xóa một số lượng ít nhất ký tự có thể (có thể không xóa ký tự nào) để nhận được hai xâu có ký tự giống nhau, có nghĩa là xâu này có các ký tự giống xâu kia và ngược lại. Trông đơn giản Trang 1/tổng số 3 trang
2. nhưng bài toán lại trở nên hóc búa khi độ dài của hai xâu quá lớn so với tốc độ tính toán của hai bạn. Hãy giúp Khoa và Hiếu tính toán ra đáp số của bài toán nhé. Yêu cầu: Cho trước hai xâu ký tự do Khoa và Hiếu viết ra, hãy tính tổng số lượng ký tự ít nhất cần xóa (ở cả hai xâu) để nhận được hai xâu có ký tự giống nhau. Dữ liệu: Vào từ file văn bản LCS.INP gồm - Dòng đầu tiên chứa xâu 푆1 do Khoa viết ra. - Dòng tiếp theo chứa xâu 푆2 do Hiếu viết ra. Kết quả: Ghi ra file văn bản LCS.OUT một số nguyên duy nhất là số lượng ký tự ít nhất cần xóa để nhận được hai xâu có ký tự giống. Dữ liệu đảm bảo bạn luôn tìm được một phương án xóa thỏa mãn đề bài. Ví dụ: LCS.INP LCS.OUT hocsinhgioi 4 lopchin (Giải thích: Xóa ký tự ‘s’ và ‘g’ ở xâu 푆1, xóa ký tự ‘l’ và ‘p’ ở xâu 푆2, ta được hai xâu có giống nhau Ràng buộc: - Có 70% số test ứng với 70% số điểm của bài có |푆1|, |푆2| ≤ 200. - 30% số test còn lại ứng với 30% số điểm của bài có |푆1|, |푆2| ≤ 300. Bài 3. (5,0 điểm) Sắp xếp dãy số Cho hai số nguyên dương n và m. Ta sắp xếp n số nguyên dương liên tiếp 1; 2; 3; ; n thành một dãy gồm có m đoạn liên tiếp như sau: Đoạn thứ nhất gồm tất cả các số chia hết cho m; đoạn thứ hai gồm tất cả các số chia m dư 1; đoạn thứ ba gồm tất cả các số chia m dư 2; ; đoạn thứ m gồm tất cả các số chia m dư m – 1. Các số trong mỗi đoạn cũng được sắp xếp theo thứ tự tăng dần. Yêu cầu: Cho trước 3 số nguyên dương n; m; t. Tìm số thứ t trong dãy sắp thứ tự như trên. Ví dụ: Với n = 10; m = 4; t = 8. Dãy số được sắp xếp như sau: 4; 8; 1; 5; 9; 2; 6; 10; 3; 7 Số hạng thứ 8 trong dãy trên là 10 Dữ liệu: Vào từ file văn bản SORT.INP gồm ba số nguyên dương n; m; t nằm trên một dòng (1 < m < n ≤ 1016 ; m ≤ 106 ; t ≤ n), mỗi số cách nhau ít nhất một dấu cách. Kết quả: Ghi ra file văn bản SORT.OUT một số X là số hạng thứ t trong dãy sắp thứ tự như trên. Ví dụ: SORT.INP SORT.OUT 10 4 8 10 Trang 2/tổng số 3 trang
3. Bài 4. (5,0 điểm) Phần quà may mắn Thầy Nam có N phần quà cho N thí sinh dự thi kì thi học sinh giỏi lớp 9 năm nay. Trên hộp quà thứ i có ghi số nguyên ai. Sau khi tặng quà cho các thí sinh, thầy Nam có thêm những phần quà may mắn cho mỗi cặp thí sinh có cặp số trên hộp quà là ai, aj (i≠j) sao cho |ai+ aj|= K với K là một số cho trước. Yêu cầu: Hãy cho biết thầy Nam phải chuẩn bị bao nhiêu phần quà may mắn. Dữ liệu: Vào từ tệp văn bản LUCKY.INP gồm hai dòng: - Dòng 1: Gồm 2 số N và K; - Dòng 2: Gồm N số là các phần tử trong dãy, các phần tử cách nhau bởi dấu cách. Kết quả: Ghi ra tệp văn bản LUCKY.OUT Gồm 1 dòng duy nhất ghi số lượng cặp số may mắn. Ví dụ: LUCKY.INP LUCKY.OUT 7 5 4 4 3 4 1 4 3 4 5 11 0 -4 -1 0 7 -4 Ràng buộc: 5 18 18 Kích thước dữ liệu vào: 0<N ≤ 10 ,| ai| ≤ 10 ,0 ≤ K ≤ 10 Có ít nhất 60% số test ứng với N<=2000. HẾT (Giám thị không giải thích gì thêm) Trang 3/tổng số 3 trang