Đề thi môn Tin học - Kỳ thi chọn học sinh giỏi tỉnh Lớp 11 cấp THPT - Năm học 2016-2017 - Sở GD&ĐT Nghệ An

Nội dung text: Đề thi môn Tin học - Kỳ thi chọn học sinh giỏi tỉnh Lớp 11 cấp THPT - Năm học 2016-2017 - Sở GD&ĐT Nghệ An

1. SỞ GD&ĐT NGHỆ AN KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11 CẤP THPT NĂM HỌC 2016 - 2017 Đề chính thức Môn thi: TIN HỌC - BẢNG A Thời gian: 150 phút (không kể thời gian giao đề) (Đề thi có 02 trang) Tổng quan bài thi: Tên bài File nguồn File Input File Output Thời gian chạy PERFECT PERFECT.* PERFECT.INP PERFECT.OUT 1 giây PALIN PALIN.* PALIN.INP PALIN.OUT 1 giây SEQ SEQ.* SEQ.INP SEQ.OUT 1 giây GN GN.* GN.INP GN.OUT 1 giây Chú ý: 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à ngôn ngữ lập trình PASCAL hoặc ngôn ngữ lập trình C++ Hãy lập trình giải các bài toán sau: Bài 1 (6.0 điểm): PERFECT Trong một buổi học toán, Bông được học khái niệm về số có tính chất đặc biệt: Đó là số hoàn hảo. Số A được gọi là số hoàn hảo nếu: A = B1 + B2 + + Bk trong đó Bi là ước của A và Bi < A với i (1 i k) . Ví dụ: Số 6 là số hoàn hảo vì nó có tổng các ước 1 + 2 + 3 = 6, số 8 không phải là số hoàn hảo vì 1 + 2 + 4 = 7, (7≠ 8). Yêu cầu: Cho dãy số a 1, a2, , an. Hãy giúp Bông đếm xem trong dãy có bao nhiêu số có tổng các chữ số là số hoàn hảo. Dữ liệu vào: Từ file văn bản PERFECT.INP gồm: - Dòng đầu tiên là số nguyên dương n (n ≤ 100). 9 - Dòng thứ 2 ghi n số nguyên a1, a2, , an (0 ≤ ai ≤ 10 ). Kết quả: Ghi ra file văn bản PERFECT.OUT gồm: Một số duy nhất là kết quả của bài toán. Ví dụ: PERFECT.INP PERFECT.OUT 3 2 6 123 28 Bài 2 (6.0 điểm): PALIN Một xâu S được gọi là xâu đối xứng nếu S = S' với S' là xâu nhận được từ xâu S khi đọc từ phải qua trái. Ví dụ: Xâu 'aba' là xâu đối xứng, còn xâu 'abc' là xâu không đối xứng. Cho một xâu S gồm n kí tự (1 ≤ n ≤ 100) Yêu cầu: Hãy tìm cách chia xâu S thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng. Dữ liệu vào: Từ file văn bản PALIN.INP gồm: - Dòng đầu gồm một số nguyên n là độ dài của xâu S. - Dòng thứ hai là nội dung xâu S. Kết quả: Ghi ra file văn bản PALIN.OUT gồm: Trang 1/2
2. - Dòng đầu ghi một số nguyên k (số đoạn ít nhất tìm được). - K dòng sau, mỗi dòng ghi một số nguyên ti, với ti là vị trí kết thúc của đoạn thứ i. Ví dụ: PALIN.INP PALIN.OUT 8 3 abbacdcb 4 7 8 Bài 3 (4.0 điểm): SEQ Cho dãy số gồm n số nguyên a1, a2, , an và 2 số nguyên không âm L, R (L ≤ R). Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai+ +aj| ≤ R . Dữ liệu vào: Từ file văn bản SEQ.INP gồm: - Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109) 9 - Dòng thứ hai chứa n số nguyên dương a1, a2, , an (ai ≤ 10 ) Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) đếm được. Ví dụ: SEQ.INP SEQ.OUT 3 0 1 4 1 -1 2 Hạn chế: - Có 50% số test ứng với 0 < n ≤ 103 - Có 50% số test ứng với 103 < n ≤ 105 Bài 4 (4.0 điểm):GN Người ta đo độ giống nhau của hai xâu X, Y có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số i thỏa mãn X[i] = Y[i]. Ví dụ: X = 'avbc'; Y = 'avvv' có độ giống nhau bằng 2. Cho một xâu S có độ dài n và một xâu T có độ dài m (m n), độ giống nhau giữa xâu S và xâu T là tổng số độ giống nhau giữa xâu T và mọi xâu con gồm các kí tự liên tiếp của S có độ dài m. Yêu cầu: Cho hai xâu S và T. Tính độ giống nhau giữa xâu S và xâu T. Dữ liệu vào: Từ file văn bản GN.INP như sau: Dòng đầu ghi xâu T. Dòng thứ 2 ghi xâu S. Các kí tự trong hai xâu thuộc 'a' 'z' và có độ dài không quá 2.106 kí tự. Kết quả: Ghi ra file văn bản GN.OUT gồm một số nguyên duy nhất là độ giống nhau giữa xâu S và xâu T. Ví dụ: GN.INP GN.OUT abaab 12 aababacab Hạn chế: - Có 25% số test ứng với 0 < n ≤ 102 - Có 25% số test ứng với 102 < n ≤ 104 - Có 50% số test ứng với 104 < n ≤ 2.106 (Hết) Họ và tên thí sinh: Số báo danh: Trang 2/2