Kỳ thi chọn học sinh giỏi tỉnh lớp 12 năm học 201 3- 2014 môn Tin học 8

SỞ GD & ĐT NGHỆ AN KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12

NĂ M HỌC 2013-2014

Môn thi: TIN HỌC – THPT BẢNG A Thời gian: 150 phút (không kể thời gian giao đề)

TỔNG QUAN BÀI THI Bài Tên file nguồn File Input File Output Thời gian chạy Điểm Bài 1 LAPTRINH.PAS LAPTRINH.INP LAPTRINH.OUT 1 giây 7 Bài 2 DOANMAX.PAS DOANMAX.INP DOANMAX.OUT 1 giây 5 Bài 3 XOASO.PAS XOASO.INP XOASO.INP 1 giây 5 Bài 4 MAHOA.PAS MAHOA.INP MAHOA.UOT 1 giây 3 Bài 1. (7 điểm) LAPTRINH Trong cuộc thi lập trình có N bài thi giải đúng yêu cầu đặt ra. Ban tổ chức quyết định trao giải phần thưởng đặc biệt cho bài thi tốt nhất, đó là bài thi có thời gian chạy chương trình ít nhất. Cho biết bài thi thứ i (1<=i<=N) có thời gian chạy là một số nguyên Ai (Tính theo đơn vị Centisecond, 1 Centisecond = 1/100 giây).

Yêu cầu: Hãy cho biết thời gian của bài thi được trao thưởng và có bao nhiêu bài thi được trao thưởng.

Dữ liệu: Vào từ file văn bản LAPTRINH.INP - Dòng 1 chứa số nguyên dương N (N<=100). - Dòng 1 chứ N số nguyên A1 A2… An (0<=Ai<=100) Kết quả: Ghi ra file văn bản LAPTRINH.OUT - Dòng thứ 1 chứa một số nguyên là thời gian ít nhất tìm được. - Dòng thứ 2 chứa một số nguyên là số bài thi cùng đạt thời gian ít nhất Ví dụ.

LAPTRINH.INP LAPTRINH.OUT 5 10 8 12 8 11

8 2

Giải thích test ví dụ: thời gian ít nhất là f8 và có 2 bài cùng thời gian đó Bài 2. (5 điểm) ĐOẠN MAX Cho chuỗi ký tự S gồm các chữ cái in hoa (A…Z) với độ dài không vượt quá 104.

Yêu cầu: Hãi tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn xuất hiện đâu tiên trong chuỗi S.

Dữ liệu: Vào từ văn bản DOANMAX.INP: - Gồm một dòng duy nhất chứa chuỗi S. Kết quả: Ghi ra file văn bản DOANMAX.OUT - chổ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiệu dài của đoạn con dài nhất tìm được.

Ví dụ:

DOANMAX.INP DOANMAX.OUT ABABCDAC 3 4

Lưu ý: Có 80% test có độ dài xâu không vượt quá 255. Giải thích test ví dụ: Đoạn con dài nhất tìm được là ABCD có vị trí 3 và dộ dài 4

Đềthi chính

ThuVienDeThi.com

Bài 3. (5 điểm) XOÁ SỐ.

Cho dãy số nguyên không âm A1 A2... An. Người ta muốn chọn 2 chỉ số i, j sao cho 1<=i<=j<=N và xoá khỏi dãy 2 số Ai, Aj để tổng giá trị các số còn lại trong dãy là số chẵn.

Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Dữ liệu: Vào từ file văn bản XOASO.INP - Dòng 1 chứ số nguyên dương N (N<=106) - Dòng 2 chứa N số nguyên không âm A1 A2…An (Ai<=103) Kết quả: Ghi ra file XOASO.OUT - Chỉ một dòng duy nhất chứa một số nguyên là số cách chọn 2 chỉ số thoả mãn. Ví dụ:

XOASO.INP XOASO.OUT 5 1 2 3 4 5

6

Lưu ý: Có 50% test có N<=1000. Giải thích test ví dụ: Có 6 cách chọn 2 chỉ số i, j là: i = 1, j=2 tổng còn lại A3+ A4+ A5 = 3 + 4 + 5 = 12 là số chẵn. Tương tự: i=1, j=4 và i=2; j=3 và i=2; j-5 và i=3; j=4 và i=4; j=5. Bài 4. MÃ HOÁ Nam rất thích thú với việc mã hoá dữ liệu. Trong buổi thảo luận ở lớp Nam đã trình bày một ý tưởng rất thú vị rằng bạn ấy vừa phát minh ra một cách mã hoá mới, có thể mã các thông tin mà không ai có thể giải mã. Cách mã hoá đó là: Với một số nguyên N, xoá các chữa số từ con số này bằng mọi cách có thể, ta sẽ nhận được các số mới. Một số cách xoá mà số mới thu được có giá trị bằng số cũ đó là khi ta xoá các chữ số 0 bên trái. Hãy tìm tổng của tất cả các con số mới thu được. Tổng này chính là mã hoá của N.

Một bạn trong lớp đã có ý kiến “Mình nghĩ cách mã hoá của cậu trên máy tính sẽ thực hiện mất nhiều thời gian với số có nhiều chữ số, chẳng hạn só có 100 chữ số. Không thể chờ để có một mã số cho số có 100 chữ số. Cách mã hoá này của bạn không thể được áp dụng trên thực tế”. Nam đã trả lời “không, không, không”. Ngày mai mình sẽ đưa ra chương trình thực hiện cách mã hoá này, và sẽ mã hoá cho số có 100 chữ số trong thời gian không quá 1 giây” câu trả lời của Nam được cả lớp rất hoan nghênh. Bạn hãy giúp Nam viết chương trình đó.

Yêu cầu: …