KỲ THI CHỌN HỌC SINH GIỎI CẤP THCS NĂM HỌC 2004-2005 ĐỀ THI MÔN : TIN HỌC LỚP 9

(1)

SỞ SỞ GD-ĐT VĨNH PHÚC --- ĐỀ CHÍNH THỨC

Thời gian làm bài 150 phút không kể thời gain giao đề ---

Bài 1: Tứ giác đồng hồ cạnh K - Tên file chương trình đặt là BL1.PAS

Cho mảng vuông A[I,j] (I,j = 1, 2, ..., N), chỉ số hàng của A được tính từ trên xuống dưới, chỉ số cột được tính từ trái qua phảI, các phần tử của nó là các số nguyên. Bốn ô: A[i,j]; A[i,j+K]; A[i+K,j+K];

a[i+K,j] thuộc mảng được gọi là bốn đỉnh của một: ‘Tứ giác đồng hồ cạnh K’ nếu từ một đỉnh nào đó theo chiều kim đồng hồ giá trị của 4 ô trên tạo thành một dãy tăng.

Yêu cầu: Lập chương trình tính số lượng các tứ giác đồng hồ cạnh K của mảng A.

Dữ liệu vào từ file văn bản: ‘BL1.INP’:

Dòng 1: Cho hai số N, K (2  N  100; 1  K  N-1)

N dòng tiếp theo, mỗi dòng có N số nguyên, mỗi số có trị tuyệt đối không vượt quá 10⁶ 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 cách nhau ít nhất một kí tự trống.

Dữ liệu ra ghi ra file văn bản: ‘BL1.OUT’

Số S là số các Tứ giác đồng hồ cạnh K.

Ví dụ:

BL1.INP BL1.OUT

4 3 4 3 2 5 4 4 5 5 2 3 5 3 3 5 6 7

1

Bài 2: Số đảo ngược - Tên file chương trình đặt là BL2.PAS

Cho số nguyên A biểu diễn trong hệ thập phân có dạng a1a2...aN-1aN. Ta gọi số nguyên A* mà biểu diễn trong hệ thập phân có dạnh aNaN-1...a2a1 (Có đúng N chữ số có nghĩa) là số đảo ngược của A.

Ta có thể định nghĩa tương tự như trên đối với số đảo ngược của một số trong hệ nhị phân.

Yêu cầu: Cho trước số nguyên dương K. Hãy tìm số lượng các số nguyên không âm A thỏa mãn A  K và biểu diễn trong hệ nhị phân của A và A* là hai số đảo ngược của nhau.

Dữ liệu vào từ file văn bản: ‘BL2.INP’

Số K (K 1000)

Dữ liệu ra ghi ra file văn bản: ‘BL2.OUT’

Số S là số lượng các số tìm được

Ví dụ :

7 5

(Giải thích: Với K = 7 Ta tìm được 5 số, đó là các số 0, 1, 3, 5, 7) Bài 3: Dãy các hình chữ nhật - Tên file chương trình đặt là BL3.PAS

Giả sử ABCD là một hình chữ nhật trên mặt phẳng tọa độ có các đỉnh: A (0;0); B(0;1); C(K;1);

D(K;0). Ta xem hình này là hình có số hiệu 1 (Hình (H1) vẽ dưới đây ứng với k = 2). Hình có số hiệu 2 xây dựng trên cạnh Bắc của hình 1 và cạnh kia gấp K lần (chiều dài gấp K lần chiều rộng). Hình có số hiệu 3 xây dựng trên cạnh Tây của hình chữ nhật hợp bởi các hình 1 và 2 và cạnh kia gấp K lần. Hình có số hiệu 4 xây dựng trên cạnh Nam của hình chữ nhật hợp bởi các hình 1, 2, 3 và cạnh kia gấp K lần.

Hình có số hiệu 5 xây dựng trên cạnh Đông của hình chữ nhật hợp bởi các hình 1, 2, 3, 4 và cạnh kia gấp K lần. Tương tự quy luật đó với các hình mang thứ tự 6, 7, ...

Yêu cầu: Cho trước 3 số nguyên K, X, Y, hãy cho biết số hiệu nhỏ nhất của hình chữ nhật chứa điểm có tọa độ (X;Y), điểm (X;Y) có thể nằm trong hoặc trên biên của hình chữ nhật.

Dữ liệu vào từ file văn bản: ‘BL3.INP’

Ba số K, X, Y với ý nghĩa nêu trên, các số cách nhau ít nhất một kí tự trống.

Kết quả ghi ra file văn bản: ‘BL3.OUT’

Số S là số hiệu của hình chữ nhật nhỏ nhất chủa điểm (X;Y)

(2)

Chú ý: 1



K



100; X, Y có giá trị tuyệt đối không quá 10

⁶

. Ví d : ụ

2 7 -2 5

---Hết---

(Giám thị coi thi không giải thích gì thêm) Tây

2 1 3

O

A 2 B C

Đông Bắc

Nam

-10 D

1 5

H 1