Đề thi chọn học sinh giỏi môn Tin học Lớp 12 - Năm học 2019-2020 - Trường THPT Đồng Đậu

-1-

TRƯỜNG THPT ĐỒNG ĐẬU --------  --------

KỲ THI CHỌN HỌC SINH GIỎI CẤP TRƯỜNG LỚP 12 NĂM HỌC 2019-2020 MÔN: TIN HỌC Thời gian làm bài: 180 phút (không kể thời gian giao đề)

Tổng quan về các bài thi trong đề:

TT Tên bài Tên file chương trình Dữ liệu vào Dữ liệu ra Thời gian chạy 1 test Điểm

1 Ghi số ghiso.* Ghiso.inp ghiso.out 1s 6

2 Trung bình cộng tbc.* tbc.inp tbc.out 1s 6

3 Xây thành Xaythanh.* xaythanh.inp xaythanh.out 1s 8

Yêu cầu các thí sinh đọc kỹ phần hướng dẫn dưới đây:

 Dấu (*) trong tên file chương trình được thay thế bằng PAS, C hoặc CPP tuỳ theo thí sinh viết chương trình bằng ngôn ngữ Pascal, C hoặc C++

 Chương trình chỉ in kết quả theo yêu cầu của đề bài, không in bất kỳ thông tin nào khác  Đối với các bài tập đọc và in dữ liệu từ file văn bản, tên các file này phải đặt đúng theo yêu cầu đề bài, không có đường dẫn phía trước.

Viết chương trình giải các bài toán sau:

Bài 1: Ghi số Cho dãy S ( có chiều dài |S|≤ 103) chỉ chứa các dấu “>”, “<” và “=”. Yêu cầu: Tìm số nguyên dương P nhỏ nhất sao cho ta có thể điền các số nguyên dương trong đoạn [1;P] và dãy dấu trên sao cho mỗi dấu đề có 2 số kề bên, và dãy số được điền vào là dãy đúng Ví dụ:

Dãy dấu: <<<, dãy số khi điền: 1<2<3<4, P=4 Dãy dấu: <=>, dãy dấu sau khi điền: 1<2=2>1 Dữ liệu vào: Đọc từ tệp ghiso.inp

Dòng 1 ghi một số nguyên dương N là số dãy S N dòng tiếp theo(Các dòng 1+i với i=1..N): dòng 1+i chứa dãy Si Dữ liệu ra: Ghi vào tệp ghiso.out

Gồm N dòng, dòng thứ j chứa số nguyên Pi cần tìm(i=1..N) Ví dụ

GHISO.INP GHISO.OUT 2 <<< <=>

4 2

ĐỀ THI CHÍNH THỨC

DeThi.edu.vn

-2-

Bài 2: Trung bình cộng Tý là một bạn rất thích học Tin học. Nhân dịp Xuân về, lớp tổ chức trò chơi “ Ai làm toán nhanh”. Cách chơi như sau: có n gói kẹo được đánh số từ 1 đến n, gói thứ i có ai chiếc kẹo; nhiệm vụ của người chơi là chọn một số gói kẹo liên tiếp trong n gói kẹo đã cho sao cho trung bình cộng của số kẹo trong các gói được chọn là k cho trước; người thắng cuộc là người chọn được nhiều gói kẹo nhất và toàn bộ số kẹo đó sẽ là phần thường dành cho người đó. Yêu cầu: Hãy lập trình giúp Tý là người thắng cuộc trong cuộc thi Dữ liệu: Đọc từ tệp tbc.inp

Dòng đầu tiên chứa 2 số nguyên n và k; (1≤ n ≤ 105, 1≤ k ≤ 109) Dòng thứ 2 chứa n số nguyên a1, a2,...,an (1≤ ai ≤109, i=1,1,3,...,n) Kết quả: Ghi vào tệp tbc.out

Số nguyên ghi độ dài của dãy tìm được hoặc só 0 nếu không tồn tại cách chọn Ví dụ:

TBC.INP TBC.OUT 5 3 3

Bài 3 Xây thành

Để đảm bảo an ninh chống lại sự tấn công của kẻ xâm lăng, Vua An Dương Vương quyết định cho xây dựng các thành luỹ quanh các điểm dân cư đông đúc. Theo lời khuyên của Rùa thần, tên của các thành luỹ phải được chọn là một xâu con các kí tự liên tiếp nhau của tên Rùa thần. Tên của Rùa thần là một xâu ký tự Q chỉ gồm các chữ cái tiếng Anh in hoa. Ví dụ, nếu Q là ‘ABAB’ thì tên của thành luỹ có thể là : ’A’, ‘B’, ‘AB’, ‘BA’, ‘ABA’, ‘BAB’, ’ABAB’ (Chú ý là các tên khác nhau phải là các dãy ký tự khác nhau). Nhà Vua muốn biết là có thể xây dựng được tối đa bao nhiêu thành luỹ dựa vào số tên có thể đặt. Yêu cầu: Ghi vào tệp xaythanh.inp

Dòng duy nhất chứa xâu ký tự Q, trong đó chỉ có các chữ cái tiếng Anh in hoa và có độ dài không quá 255. Dữ liệu: Ghi vào tệp xaythanh.out

In ra màn hình duy nhất một số nguyên dương là số lượng tên khác nhau.

Xaythanh.inp Xaythanh.out ABAB 7

---------------------------------------Hết----------------------------------------------

DeThi.edu.vn