Đề 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

Trang 1 
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ố 
{
Đặt 
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 
 ; 
 điểm dành cho các test có . 
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 
Trang 2 
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 ===============