ĐỀ THI HSG TIN HỌC 2009 LỚP 12 TỈNH THANH HÓA

Sở Giáo dục và đào tạo
thanh hoá

ĐỀ CHÍNH THỨC
Kỳ thi học sinh giỏi tỉnh
Năm học: 2008-2009
Môn thi: Tin học
Lớp 12 THPT
Ngày thi: 28/03/2009
Thời gian: 180 phút (không kể thời gian giao đề)
Đề này có 05 câu, gồm 02 trang.


Tổng quan bài thi:


Tên bài
File chương trình
File dữ liệu vào
File kết quả

Bài 1
Số nguyên tố
BAI1.PAS
BAI1.INP
BAI1.OUT

Bài 2
Trung bình cộng
BAI2.PAS
BAI2.INP
BAI2.OUT

Bài 3
Xâu đối xứng
BAI3.PAS
BAI3.INP
BAI3.OUT

Bài 4
Biểu thức Zero
BAI4.PAS
BAI4.INP
BAI4.OUT

Bài 5
Miền 0
BAI5.PAS
BAI5.INP
BAI5.OUT

Giới hạn thời gian cho mỗi test là 3 giây.
Dữ liệu vào là đúng đắn, không cần phải kiểm tra.
Hãy lập trình giải các bài toán sau:

Bài 1: (5 điểm) Số nguyên tố
Cho dãy số gồm có N số nguyên dương a1, a2,..., aN và một số nguyên dương K.
Yêu cầu: Hãy cho biết số lượng các phần tử có giá trị nhỏ hơn K là số nguyên tố của dãy số trên.
Dữ liệu: Vào từ File văn bản BAI1.INP gồm:
Dòng đầu tiên là hai số N và K.
Dòng tiếp theo lần lượt là N số nguyên của dãy số.
Kết quả: Ghi ra File BAI1.OUT gồm duy nhất số M là số lượng các phần tử của dãy số thoả mãn yêu cầu đề bài.
Giới hạn: 0 < N < 50000; 0 < K, ai < 5000 (i = 1..N;
Ví dụ:
BAI1.INP
BAI1.OUT

7 8
1 2 3 8 7 6 11
3



Bài 2: (5 điểm) Trung bình cộng
Cho dãy gồm n số nguyên a1, a2,..., an và số nguyên K.
Yêu cầu: Cho biết trong dãy số đã cho có tồn tại hay không một cặp số mà trung bình cộng của chúng là K.
Dữ liệu: Vào từ file văn bản BAI2.INP:
Dòng đầu tiên ghi hai số n, K.
Dòng tiếp theo lần lượt ghi n số a1, a2,..., an.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách trống.
Kết quả: Ghi ra file văn bản BAI2.OUT:
Số 1 nếu tồn tại một cặp số thoả mãn yêu cầu bài toán.
Số 0 nếu không tồn tại cặp số nào thoả mãn yêu cầu bài toán.
Giới hạn: 0 < N < 50000; |K|, |ai| < 1000 (i = 1..n;
Ví dụ:
BAI2.INP
BAI2.OUT

BAI2.INP
BAI2.OUT

4 5
0 2 6 4
1

3 3
1 2 3
0


Bài 3: (4 điểm) Xâu đối xứng
Xâu đối xứng là xâu đọc giống nhau nếu ta bắt đầu đọc từ trái qua phải hoặc từ phải qua trái. Ví dụ, xâu RADAR là xâu đối xứng, xâu TOMATO không phải là xâu đối xứng.
Yêu cầu: Cho một xâu S gồm không quá 200 kí tự. Cho biết S có phải là xâu đối xứng hay không? Nếu không, cho biết số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Dữ liệu: Vào từ file văn bản BAI3.INP, gồm duy nhất 1 dòng ghi xâu S.
Kết quả: Ghi ra file văn bản BAI3.OUT, duy nhất số k là số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Nếu xâu S đã cho là đối xứng thì ghi k = 0.
Ví dụ:
BAI3.INP
BAI3.OUT

BAI3.INP
BAI3.OUT

RADAR
0

TOMATO
3


Bài 4: (3 điểm) Biểu thức Zero
Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy: 1 2 3 ... N. Cuội đố Bờm điền các dấu phép toán + hoặc - vào giữa 2 số tự nhiên liên tiếp sao cho biểu thức thu được có kết quả bằng 0.
Yêu cầu: Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán thích hợp.
Dữ liệu: Vào từ file văn bản BAI4.INP gồm 1 dòng duy nhất ghi số N. N<10
Kết quả: Ghi ra file văn bản có tên BAI4.OUT:
Dòng đầu tiên ghi số M là số