Kỳ thi chọn học sinh giỏi Tin học 12 - Năm học 2015-2016 - Sở GD & ĐT Vĩnh Phúc

SỞ GD&ĐT VĨNH PHÚC
KỲ THI CHỌN HSG LỚP 12 THPT NĂM HỌC 2015-2016
ĐỀ THI MÔN: TIN HỌC – THPT
Thời gian: 180 phút, không kể thời gian giao đề
(Đề thi có 02 trang)
ĐỀ CHÍNH THỨC
Tổng quan về đề thi
Tên bài
File chương trình
File dữ liệu
File kết quả
Thời gian
Điểm
Dãy số
numseq.*
numseq.inp
numseq.out
1 giây
3
Tổng chính phương
ssquare.*
ssquare.inp
ssquare.out
1 giây
4
Đếm hình chữ nhật
reccount.*
reccount.inp
reccount.out
1 giây
3
Thí sinh thay * trong File chương trình bằng CPP hoặc PAS tùy theo ngôn ngữ lập trình mà thí sinh sử dụng là C++ hoặc Pascal
Lập chương trình giải các bài toán sau đây
Bài 1. Dãy số
Cho dãy số
a0=0,a1=1an=2an-1-an-2+1 (∀n>1, n∈Z)
Đặt
X=(an+1-an)2
Lập chương trình tìm chữ số cuối cùng của X.
Dữ liệu
Một dòng duy nhất ghi số n.
Kết quả
Một dòng duy nhất ghi kết quả tìm được.
Ví dụ
Input
output
4
5
Ràng buộc dữ liệu
n≤1015;
60% điểm dành cho các test có n≤104.
Bài 2. Tổng chính phương
Sau tiết học về ‘Số chính phương’ (số chính phương là bình phương của một số tự nhiên), Minh rất thích thú và nghĩ ra một trò chơi để đố các bạn. Minh sẽ nghĩ ra một số nguyên dương bất kì và đố các bạn xem số đó có là tổng của 4 số chính phương dương hay không. Ví dụ: 53=22+22+32+62; 94=22+42+52+72.
Yêu cầu: Lập chương trình giúp các bạn của Minh tìm cách phân tích một số nguyên dương N thành tổng của 4 số chính phương dương.
Dữ liệu: Một dòng duy nhất ghi một số nguyên dương N (0 < N < 105).
Kết quả: Nếu phân tích được in ra số 1, ngược lại in ra -1.
Ví dụ:
Input
output
53
1
Bài 3. Đếm hình chữ nhật
Cho một ma trận A kích thước MxN, các phần tử A[i,j] chỉ nhận giá trị bằng 1 hoặc bằng 0.
Các phần tử có giá trị 1 liền cạnh nhau khép kín có thể tạo thành hình chữ nhật có toạ độ đỉnh trên cùng bên trái là phần tử A[i,j], toạ độ đỉnh dưới cùng bên phải là phần tử A[u,v] nếu nó thoả mãn điều kiện sau:
Các phần tử A[i-1,j], A[i-1,j+1], , A[i-1, v] đều bằng 0 nếu i>1;
Các phần tử A[u+1,j], A[u+1,j+1], , A[u+1, v] đều bằng 0 nếu u<M;
Các phần tử A[i,j-1], A[i+1,j-1], , A[u, j-1] đều bằng 0 nếu j>1;
Các phần tử A[i,v+1], A[i+1,v+1], , A[u, v+1] đều bằng 0 nếu v<N;
Hình chữ nhật gọi là đậm đặc nếu ở trong chỉ toàn phần tử có giá trị bằng 1;
Hình chữ nhật gọi là rỗng nếu ở trong chỉ toàn phần tử có giá trị bằng 0.
Viết chương trình đếm xem có bao nhiêu hình chữ nhật, bao nhiêu hình chữ nhật đậm đặc và bao nhiêu hình chữ nhật rỗng?
Dữ liệu
Dòng đầu chứa 2 số M, N (1<M, N<=200);
M dòng tiếp theo thể hiện ma trận A (các số trên cùng một dòng mỗi số cách nhau một dấu cách).
Kết quả
Dòng đầu ghi số lượng các hình chữ nhật;
Dòng thứ hai ghi số lượng các hình chữ nhật đậm đặc;
Dòng thứ ba chứa số lượng các hình chữ nhật rỗng.
Ví dụ
Input
Output
12 8
7
5
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
1
1
1
1
0
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
Ràng buộc dữ liệu
Có 30% số test ứng với 30% số điểm của bài có 1<M, N<=50;
Có 30% số test ứng với 30% số điểm của bài có 50<M, N<=100;
Có 40% số test ứng với 40% số điểm của bài có 100<M, N<=200.
=============== Hết ===============