Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học (Kì thứ hai) - Năm học 2014-2015 - Sở Giáo dục và Đào tạo Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HSG LỚP 12 THPT, GDTX 
Kỳ thi thứ hai - Năm học 2014 – 2015
MÔN: TIN HỌC
Ngày thi: 26/11/2014
(Thời gian 180, phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
Tổng quan đề thi:
Câu
Tên bài
Tên file bài làm
Tên file Input
Tên file Otput
1
Dãy số
DAYSO.PAS
DAYSO.INP
DAYSO.OUT
2
Số nguyên tố liên tiếp
SNT.PAS
SNT.INP
SNT.OUT
3
Đèn điện
DENDIEN.PAS
DENDIEN.INP
DENDIEN.OUT
( Yêu cầu học sinh đặt tên file bài làm đúng như trên)
Câu 1: Dãy số (7 điểm). 
 Cho 1 dãy số A được xây dựng theo quy luật như sau: Bắt đầu là một số 1, tiếp theo là hai số 2, ba số 3, bốn số 4,
A = 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 
Yêu cầu: Hãy viết chương trình nhập vào hai số i và j, tìm tổng các phần tử có thứ tự bắt đầu từ i đến j của dãy số A.
Ví dụ: i = 3 và j = 8 thì tổng cần tìm là: 2 + 3 + 3 + 3 + 4 + 4 = 19. 
Dữ liệu vào: File ‘DAYSO.INP’ gồm 2 số i và j cách nhau ít nhất một khoảng trắng.
 ( 1 i j 1700000)
Dữ liệu ra: File ‘DAYSO.OUT’ chứa tổng cần tìm.
Ví dụ: 
DAYSO.INP
DAYSO.OUT
DAYSO.INP
DAYSO.OUT
3 8
19
5 12
32
(60% số test có j 1000)
Câu 2: Số nguyên tố liên tiếp (7 điểm).
Hai số nguyên tố được gọi là liên tiếp nếu giữa hai số nguyên tố đó không có số nguyên tố nào khác.
Ví dụ: 13 và 17 là hai số nguyên tố liên tiếp.
Yêu cầu: Cho một số nguyên dương N. Hãy phân tích N thành tổng của 4 số nguyên tố liên tiếp.
Dữ liệu vào: File ‘SNT.INP’ chỉ chứa một số nguyên dương N (N 200000).
Dữ liệu ra: File ‘SNT.OUT’ là 4 số nguyên tố lên tiếp thỏa mãn có tổng bằng N và được sắp xếp theo thứ tự từ nhỏ đến lớn mỗi số cách nhau một khoảng trắng hoặc là chỉ ghi một số 0 nếu không có cách phân tích thỏa mãn.
Ví dụ:
SNT.INP
SNT.OUT
SNT.INP
SNT.OUT
17
2 3 5 7
37
0
(60% số test có n 20000)
Câu 3: Đèn điện (6 điểm).
	Trong một buổi trình diễn ánh sáng đèn điện người ta bố trí các bóng điện theo một lưới hình ô vuông có kích thước N x N. Tại mỗi thời điểm các bóng điện có thể ở trạng thái đang sáng hoặc là không sáng. Thùy Trang được bố đưa đi xem nên dùng điện thoại chụp lại một bức ảnh của cuộc biểu diễn điện này về làm kỉ niệm.
Yêu cầu: Hãy giúp Thùy Trang xác định xem trong bức ảnh chụp được dãy liên tiếp dài nhất các bóng điện đang sáng có số lượng bóng điện là bao nhiêu (các bóng điện liên tiếp có thể là theo hàng ngang, hàng dọc hay là theo hàng chéo).
Dữ liệu vào: File ‘DENDIEN.INP’. 
	+ Dòng đầu tiên là số N là kích thước của lưới hình vuông (N 5000).
	+ N dòng tiếp theo mỗi dòng là N số 0 hoặc 1 tương ứng với vị trí của bóng điện đang ở trạng thái tối hoặc sáng. Mỗi số cách nhau ít nhất một khoảng trắng.
Dữ liệu ra: File ‘DENDIEN.OUT’ chỉ ghi một số là số lượng bóng điện sáng liên tiếp nhiều nhất.
Ví dụ:
DENDIEN.INP
DENDIEN.OUT
10
0 1 0 1 0 1 0 0 0 0
1 0 0 1 1 0 0 1 0 1
1 0 1 0 0 0 1 1 1 1
0 0 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 1
1 0 0 1 1 0 0 0 0 0
0 1 0 0 0 1 1 0 1 0
1 0 0 1 1 0 0 0 0 0
0 1 0 0 0 1 1 0 1 0
4
DENDIEN.INP
DENDIEN.OUT
5
0 1 0 0 1
1 0 0 0 1
1 1 0 0 0
0 0 1 0 0
0 0 0 0 0
3
(60% số test có n 500)
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 12 THPT, GDTX
Kỳ thi thứ hai - Năm học 2014 – 2015
MÔN: TIN HỌC
Ngày thi: 26/11/2014
 (hướng dẫn chấm gồm 03 trang)
Chấm thi bằng phần mềm THEMIS 1.6.8.723 của LÊ MINH HOÀNG & ĐỖ ĐỨC ĐÔNG
Câu
Đáp án
Điểm
1
( 7 điểm)
const
 ifn = 'DAYSO.INP';
 ofn = 'DAYSO.OUT';
var f : text;
 di : longint;
 m, n, i, s : longint;
begin
 assign( f, ifn);
 reset( f);
 readln( f, m, n);
 close( f);
 di := 0;
 i := 0;
 s := 0;
 while i < m do
 begin
 di := di + 1;
 i := i + di;
 end;
 s := ( i - m + 1) * di;
 while i <= n do
 begin
 di := di + 1;
 i := i + di;
 s := s + di * di;
 end; 
s := s - di * ( i - n);
 assign( f, ofn);
 rewrite( f);
 writeln( f, s);
 close( f);
end.
Cho 14 bộ test mỗi bộ 0.5 điểm
2
( 7 điểm)
program SNT;
uses crt;
Var n,k,i,luu,cs:longint;
 f1,f2:text;
 kt:boolean;
 a:array[1..100000] of longint;
function nto(a:longint):boolean;
var i:longint;
 kt: boolean;
Begin
 kt := true;
 i :=2;
 if a < 2 then kt := false
 else if a >= 4 then
 while (i <= (a div 2)) do
	begin
	 if a mod i = 0 then
	 begin
	 kt := false;
	 break
	 end;
	 inc(i);
	end;
 nto := kt;
end;
BEGIN
 assign(f1,'SNT.INP');reset(f1);
 read(f1,n);
 i:=0;
 k := 2;
 while k <= n-1 do
 begin
 	if nto(k) then
 	 begin
 i:=i+1;
 a[i]:=k;	
 end;
 inc(k);
 end;
 luu:=i;KT:=false;
 if luu>=4 then
 for i:=1 to (luu - 3) do
 begin
 if (a[i]+a[i+1]+a[i+2]+a[i+3]=n)then
 begin kt:=true; cs:=i;break;end;
 if (a[i]+a[i+1]+a[i+2]+a[i+3]>n) then break;
 end;
 assign(f2,'SNT.OUT');
 rewrite(f2);
 if kt then
 write(f2,a[cs],' ',a[cs+1],' ',a[cs+2],' ',a[cs+3])
 else write(f2,0);
 close(f1);
 close(f2);
END.
Cho 14 bộ test mỗi bộ 0.5 điểm
3
( 6 điểm)
const nm = 5001;
Var a: array[0..nm,0..nm] of byte;
 i,j,i1,j1,m,n,d,dm : longint;
 f1,f2: text;
Procedure nhap ;
Begin
 Assign(f1,'DENDIEN.INP'); reset (f1) ;
 Readln(f1,n);
 Fillchar(a,sizeof(a),0);
 i := 1;
 while i <= n do
 begin
 j := 1;
 while j <= n do
 begin
 read( f1, a[i,j]);
 inc(j);
 end;
 inc(i);
 readln(f1);
 End;
 Close(f1);
End;
Procedure xuly;
Begin
 dm:= 0;
 i :=1;
 while i <= n do
 Begin
 j := 1;
 while j <=n do
 begin
 if a[i,j] = 1 then
 begin
 d := 1; i1 :=i; j1 :=j;
 while a[i1 + 1, j1] = 1 do
 begin
 inc(d); inc(i1);
 end;
 if d > dm then dm := d;
 d := 1; i1 :=i; j1 :=j;
 while a[i1, j1 + 1] = 1 do
 begin
 inc(d); inc(j1);
 end;
 if d > dm then dm := d;
 d := 1; i1 :=i; j1 :=j;
 while a[i1 + 1, j1 + 1] = 1 do
 begin
 inc(d); inc(j1); inc(i1);
 end;
 if d > dm then dm := d;
 d := 1; i1 :=i; j1 :=j;
 while a[i1 - 1, j1 + 1] = 1 do
 begin
 inc(d); inc(j1); dec(i1);
 end;
 if d > dm then dm :=d;
 end;
 inc(j);
 end;
 inc(i);
 end;
 assign(f2,'DENDIEN.OUT');
 rewrite(f2);
 write(f2,dm);
 close(f2);
end;
BEGIN
 nhap;
 xuly;
END.
Cho 12 bộ test mỗi bộ 0.5 điểm
-----------Hết-----------