Đề thi chọn học sinh giỏi Lớp 9 môn Tin học - Năm học 2013-2014 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THCS
Năm học 2013 – 2014
MÔN: TIN HỌC
Ngày thi: 15/3/2014
(Thời gian 150 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
Yêu cầu kỹ thuật: 
* Các file chương trình và file dữ liệu được đặt tên chính xác như sau:
Câu
File bài làm
Dữ liệu vào
Dữ liệu ra
Time
Câu 1. BỘI SỐ
boiso.pas
boiso.inp
boiso.out
2s
Câu 2. PHẦN TỬ YÊN NGỰA
yenngua.pas
yenngua.inp
yenngua.out
2s
Câu 3. ĐỘ CAO
docao.pas
docao.inp
docao.out
2s
Câu 1. BỘI SỐ (6 điểm):
	Cho số nguyên dương N. Hãy tìm số nguyên dương M nhỏ nhất (1<= M <=2.109) là bội số của N sao cho biểu diễn của M trong hệ thập phân chỉ chứa các chữ số 0 và 1.
Dữ liệu vào: file boiso.inp chứa số nguyên dương N.
Dữ liệu ra: file boiso.out ghi số nguyên dương M, nếu không có M thỏa mãn điều kiện 1 <= M <= 2.109 thì ghi 0.
Ví dụ:
boiso.inp
boiso.out
25
100
900
0
Câu 2. PHẦN TỬ YÊN NGỰA (8 điểm):
Cho mảng A kích thước M x N (trong đó: M là số lượng hàng, N là số lượng cột). Phần tử Aij (hàng i, cột j) được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng của nó và đồng thời là phần tử lớn nhất trong cột của nó.
Ví dụ trong mảng sau đây:
15	3	9
55	4	6
76	1	2
thì phần tử A22 chính là phần tử yên ngựa.
Yêu cầu: Hãy viết chương trình pascal kiểm tra xem mảng A có bao nhiêu phần tử yên ngựa.
Dữ liệu vào: file yenngua.inp :
Dòng thứ nhất chứa hai số nguyên M, N cách nhau một khoảng trắng (1<M, N<1000).
M dòng tiếp theo mỗi dòng chứa N số nguyên mỗi số cách nhau ít nhất một khoảng trắng.
Các phần tử trong mảng là các số nguyên dương không vượt quá 32000.
Dữ liệu ra: file yenngua.out ghi số lượng phần tử yên ngựa có trong mảng.
Ví dụ:
yenngua.inp
yenngua.out
3 3
15	3	9
55	4	6
76	1	2
1
3 4
10 3 9 11
20 7 6 15
30 8 5 18
0
Câu 3. ĐỘ CAO (6 điểm):
	Ta gọi độ cao h của một số là tổng các chữ số có trong số đó. Cho một số nguyên dương N, ta tạo ra một số nguyên N1 bằng cách viết liên tiếp các số nguyên từ 1 đến N. 
Yêu cầu: 
Hãy đếm xem trong N1 có bao nhiêu số N2 có cùng độ cao h cho trước. Biết N2 được tạo ra bởi dãy các chữ số liên tiếp từ vị trí i đến vị trí j trong số nguyên N1 (i<= j).
Giới hạn: 1<= N <= 255, 1 <= h <= 103
Dữ liệu vào: file docao.inp trong đó:
	- Dòng 1 chứa số nguyên dương N.
	- Dòng 2 chứa số nguyên dương h.
Dữ liệu ra: file docao.out chứa một số là số lượng các số nguyên N2 có độ cao h.
Ví dụ: 
Với N = 8, h = 9 thì: N1=12345678, có 2 số N2 có độ cao h=9 là: 234, 45
 (vì 2 + 3 + 4 = 4 + 5 = 9).
	Với N = 15, h = 15 thì: N1 = 123456789101112131415, có 8 số N2 có độ cao h = 15 là: 12345, 456, 78, 9101112, 1011121314, 0111213141, 111213141, 131415. 
docao.inp
docao.out
10
9
3
15
15
8
HẾT
Họ và tên thí sinh :....................................................... Số báo danh .............................
Họ và tên, chữ ký: Giám thị 1:..........................................................................
Giám thị 2:..........................................................................
SỞ GD&ĐT NINH BÌNH
HDC ĐỀ THI CHỌN HSG LỚP 9 THCS
Năm học 2013 – 2014
MÔN: TIN HỌC
(hướng dẫn chấm gồm 4 trang)
 Chấm bằng phần mềm Themis: 
Câu
Chương trình nguồn
Điểm
Câu 1: Bội số 
program BOI_SO;
const fi='BOISO.INP';
 fo='BOISO.OUT';
var n:longint;
 f:text;
procedure nhap;
begin
 assign(f,fi); reset(f);
 read(f,n);
 close(f);
end;
procedure xuli;
var found:boolean;
 i,b : longint;
begin
 found := true;
 i := 0;
 while found do
 begin
 inc(i);
 b := n * i;
 if n * i > 2000000000 then break;
 while (((b mod 10 = 0 ) or (b mod 10 = 1 )) and (b 0)) do
 b := b div 10;
 if b = 0 then found := false;
 end;
 assign(f, fo);
 rewrite(f);
 if n*i < 2000000000 then write(f,n*i) else write(f,0);
 close(f);
end;
begin
 nhap;
 xuli;
end.
( 6 điểm) 12 test mỗi test 0,5 điểm
Câu 2
Phần tử yên ngựa 
Program YEN_NGUA;
Var a:array[1..1000,1..1000] of Integer;
 M,N,i,j,dem:Integer;
 ok:boolean;
 f : text;
Function Max(j:Integer):Integer;
Var tg,i:Integer;
Begin
 tg:=a[1,j];
 For i:=2 to M do
 If tg<a[i,j] then tg:=a[i,j];
 Max:=tg;
End;
Function Min(i:Integer):Integer;
Var tg,j:Integer;
Begin
 tg:=a[i,1];
 For j:=2 to N do
 If tg>a[i,j] then tg:=a[i,j];
 Min:=tg;
End;
Begin
 assign(f,'yenngua.inp');
 reset(f);
 Readln(f,m,n);
 For i:=1 to M do
 For j := 1 to N do
 Read(f,a[i,j]);
 close(f);
 dem:= 0;
 assign(f,'yenngua.out');
 rewrite(f);
 For i:= 1 to M do
 For j:= 1 to N do
 If (a[i,j]=Max(j)) and (a[i,j]=Min(i)) then dem:= dem + 1;
 Write(f, dem);
 close(f);
End.
(8 điểm) cho 16 test mỗi test 0,5 điểm
Câu 3
Độ cao
Program DO_CAO;
Var k,n,i,j,dem:longint;
 s,st:ansistring;
 fi,fo:text;
function taoxau(k:longint):ansistring;
var st,q:ansistring;
 i:longint;
begin
 st:='';
 for i:=1 to n do
 begin
 str(i,q);
 st:=st+q;
 end;
 taoxau:=st;
end;
function docao(x:ansistring):longint;
var k,i,w:longint;
begin
 k:=0;
 for i:=1 to length(x) do
 k:=k+(ord(x[i])-48);
 docao:=k;
end;
begin
 assign(fi,'bai3.inp6');
 reset(fi);
 assign(fo,'Bai3.out6');
 rewrite(fo);
 readln(fi,n);
 readln(fi,k);
 s:=taoxau(n);
 dem:=0;
 n:=length(s);
 for i:=1 to n do
 for j:=1 to n-i+1 do
 begin
 st:=copy(s,i,j);
 if docao(st)=k then inc(dem);
 end;
 write(fo,dem);
 close(fi);
 close(fo);
end.
(6 điểm)
12 test mỗi test cho 0,5 điểm
--------------- Hết---------------