Luyện thi HSG Tin học THCS Đề số 8

PHòng giáo dục và đạo tạo
KIẾM
Đề học sinh giỏi
Năm học: 2012 – 2013
Môn: Tin học THCS
Thời gian làm bài: 90 phút

Tổng quan
TT
Tên bài
File
chương trình
File
dữ liệu
File
kết quả
Thời
gian

1
Cùng một tích
CUNGTICH.PAS
CUNGTICH.INP
CUNGTICH.OUT
1s/test

2
Biến đổi bảng số
BDBANG.PAS
BDBANG.INP
BDBANG.OUT
1s/test

3
Số phản nguyên tố
PHANNT.PAS
PHANNT.INP
PHANNT.OUT
1s/test


Bài 1 (7 điểm) Cùng một tích
Cho n số x1, x2, ..., xn chỉ nhận một trong các giá trị -1, 0, 1, và cho một số nguyên P.
Yêu cầu: Xác định số lượng tất cả các cách gán giá trị khác nhau cho n số trên sao cho
(với i =1..n, j =1..n, i
j).
Hai cách gán được gọi là khác nhau nếu số lượng các số xi = 0 là khác nhau.
Dữ liệu: cho trong file CUNGTICH.INP, gồm nhiều phương án, mỗi phương án trên một dòng, trên dòng đó ghi hai số nguyên dương n và P.
Kết quả: ghi ra màn hình và file CUNGTICH.OUT, mỗi phương án trên một dòng, trên dòng đó ghi số các cách chọn khác nhau tìm được.
Ví dụ:
CUNGTICH.INP
CUNGTICH.OUT

1000 2
30


Bài 2 (7 điểm) Biến đổi bảng số
Trên một bảng N x N, các ô được ghi các số 1 hoặc -1. Bảng đó được biến đổi theo quy tắc: một ô nào đó có thể được thay thế bằng tích của các số trong các ô có cạnh chung với nó.
Yêu cầu: Lập chương trình thực hiện các phép biến đổi nói trên sao cho sau một số bước, bảng còn lại toàn số 1.
Dữ liệu: cho trong file BDBANG.INP, gồm N dòng, mỗi dòng ghi N số 1 hoặc -1.
Kết quả: đưa ra màn hình và file BDBANG.OUT, gồm K+1 dòng:
dòng đầu tiên ghi số K là số lượng các phép biến đổi cần thực hiện.
K dòng tiếp theo, mỗi dòng ghi tọa độ của ô biến đổi (từ -1 sang 1 hoặc ngược lại).
Ví dụ:
BDBANG.INP
BDBANG.OUT

 1 -1 1 -1 -1
-1 1 -1 1 1
-1 -1 -1 1 1
1 1 1 1 -1
1 1 -1 1 1
12
[1, 2]
[3, 1]
[3, 3]
[4, 5]
[5, 3]
[2, 1]
[2, 3]
[3, 2]
[2, 4]
[1, 4]
[1, 5]
[2, 4]


Bài 3 (6 điểm) Số phản nguyên tố
Một số nguyên dương N được gọi là số phản nguyên tố nếu số các ước số của nó là nhiều nhất trong n số tự nhiên đầu tiên.
Yêu cầu: Cho số K (K <= 2 tỷ),. Tìm và ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.
Dữ liệu: cho trong file PHANNT.INP, gồm M dòng, mỗi dòng ghi một số K.
Kết quả: đưa ra màn hình và file PHANNT.OUT, gồm M dòng, mỗi dòng ghi số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng số K tương ứng, tiếp sau là số ước số của nó.
Ví dụ:
PHANNT.INP
PHANNT.OUT

1000
840 32








Tệp CUNGTICH.INP
1000 2
1004 10
1001 30
1001 8

Tệp CUNGTICH.OUT
30
28
27
28

Tệp PHANNT.INP
1000
10000
50000
100000

Tệp PHANNT.OUT
840 32
9240 64
45360 100
98280 128