De thi HSG mon Tin

UBND HUYỆN BÌNH XUYÊN
PHÒNG GIÁO DỤC VÀ ĐÀO TẠO


KỲ THI CHỌN HSG LỚP 9 THCS NĂM HỌC 2011 – 2012
ĐỀ THI MÔN: TIN HỌC (VÒNG 1)
Thời gian làm bài: 150 phút, không kể thời gian giao đề.
——————————



TỔNG QUAN BÀI THI
TT
Tên bài
File
chương trình
File
dữ liệu
File
kết quả

1
Giai thừa
BAI1.PAS
BAI1.INP
BAI1.OUT

2
Phần tử thứ n
BAI2.PAS
BAI2.INP
BAI2.OUT

3
Đổi chỗ trong mảng
BAI3.PAS
BAI3.INP
BAI3.OUT

4
Giải mã chuỗi nhị phân
BAI4.PAS
BAI4.INP
BAI4.OUT


Hãy lập chương trình giải các bài toán sau:
Bài 1. Giai thừa
Cho số nguyên dương N. Giai thừa của N, kí hiệu là N!, là tích của các số tự nhiên từ 1 đến N. Gọi T là số lượng ước lớn hơn 1 của N!. Ví dụ với N = 4, ta có 4! = 24. Như vậy 4! có 7 ước lớn hơn 1 là: 2, 3, 4, 6, 8, 12, 24.
Yêu cầu: Cho N, hãy xác định T.
Dữ liệu vào:
Đọc từ file BAI1.INP trong đó chứa duy nhất số N (N
20, trong đó 70% số test có N
10).
Dữ liệu ra: Ghi ra file BAI1.OUT
Số T tìm được
Ví dụ:
BAI1.INP
BAI1.OUT

BAI1.INP
BAI1.OUT

4
7

10
269

Bài 2. Phần tử thứ n
Dãy số a0, a1, …, an xác định bằng quy nạp như sau :
a0 = 1
ai = i.ai-1 nếu i chẵn
ai = i+ai-1 nếu i lẻ
Yêu cầu : Xác định giá trị an.
Dữ liệu vào: Đọc từ file BAI2.INP:
Chứa duy nhất số nguyên n (1
n
19)
Dữ liệu ra: Ghi ra file BAI2.OUT
Chứa giá trị của an tìm được
Ví dụ:
BAI2.INP
BAI2.OUT

BAI2.INP
BAI2.OUT

1
2

10
16490

Bài 3. Đổi chỗ trong mảng
Cho mảng số nguyên vuông A có kích thước 2n x 2n. Hãy lập một mảng mới bằng cách đổi chỗ các khối vuông kích thước n x n của A theo cách sau:


Dữ liệu vào: Đọc từ file BAI3.INP
Dòng đầu tiên chứa số n ( 1≤ n ≤ 50)
2n dòng tiếp theo, mỗi dòng chứa 2n số nguyên, mỗi số có giá trị tuyệt đối không vượt quá 106 là giá trị các phần tử tương ứng của mảng đã cho.
Hai số liên tiếp của file dữ liệu vào cách nhau ít nhất một kí tự trống
Dữ liệu ra: Ghi ra file BAI3.OUT
Mảng sau khi đã đổi chỗ các khối vuông
Ví dụ:
BAI3.INP
BAI3.OUT
BAI3.INP
BAI3.OUT

1
10 2
7 4
7 10
4 2
3
11 22 33 44 55 66
77 88 99 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36
19 20 21 11 22 33
25 26 27 77 88 99
31 32 33 13 14 15
22 23 24 44 55 66
28 29 30 10 11 12
34 35 36 16 17 18

Bài 4. Giải mã chuỗi nhị phân
Mọi thông tin đều được mã hoá dưới dạng một chuỗi số nhị phân. Để nâng cao độ tin cậy khi truyền tin, mỗi bít được biểu diễn lặp lại 3 lần. Ví dụ, các bít tin ‘011’ được biểu diễn thành ‘000111111’ để thực hiện truyền. Do nhiễu của môi trường nên khi về đến đích, các bít tin có thể bị sai lệch. Vì vậy, khi nhận được thông tin cứ mỗi đoạn 3 bít được giải mã thành một bít. Bít này có giá trị 0 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 0, bít này có giá trị 1 nếu trong nhóm 3 bít xuất hiện ít nhất 2 bít 1. Ví dụ, nếu các bít tin nhận được là ‘000110010011’, sau khi đã giải mã ta thu được ‘0101’.
Yêu cầu: Cho chuỗi nhị phân biểu diễn thông tin nhận được, hãy giải mã chuỗi nhị phân đó.
Dữ liệu vào: Đọc từ file BAI4.INP:
Ghi chuỗi nhị phân cần giải mã, là một dãy các số 0, 1 ghi liền nhau. Dữ liệu đảm bảo luôn có chuỗi nhị phân được giải