Đề thi chọn học sinh giỏi THPT cấp tỉnh môn Tin học - Năm học 2015-2016 - Sở GD&ĐT Ninh Bình (Đề 1) (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI THPT 
Năm học 2015 – 2016
MÔN: TIN HỌC
Ngày thi 06/10/2015
(Thời gian 180 phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
Tổng quan đề thi:
Câu
Chương trình
Dữ liệu vào
Dữ liệu ra
1- Số nguyên tố tương đương
NTTD.PAS
NTTD.INP
NTTD.OUT
2- Cắt gỗ
CATGO.PAS
CATGO.INP
CATGO.OUT
3- Số chung lớn nhất
SCLN.PAS
SCLN.INP
SCLN.OUT
Câu 1 (6 điểm): Số nguyên tố tương đương.	 
Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Ví dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5.
Yêu cầu: Cho trước hai số tự nhiên M, N. Hãy viết chương trình kiểm tra xem hai số này có là nguyên tố tương đương với nhau hay không. 
Dữ liệu vào: File văn bản NTTD.INP gồm 2 số nguyên dương M, N cách nhau ít nhất một khoảng trắng ( 2 ≤ M, N ≤ 216 - 1).
Dữ liệu ra: File văn bản NTTD.OUT chỉ in duy nhất một số K là số lượng các ước nguyên tố chung nếu hai số M, N là tương đương hoặc số 0 nếu hai số đó không tương đương.
Ví dụ: 
NTTD.INP
NTTD.OUT
75 15
2
10 12
0
Câu 2 (6 điểm): Cắt gỗ.
 Bác nghệ nhân Catgo mới mua k khúc gỗ có chiều dài bằng nhau về để chế tác các sản phẩm nghệ thuật cho đơn đặt hàng mới. Bác cắt các khúc gỗ thành n mảnh gỗ khác nhau tương ứng với từng sản phẩm trong lô hàng mới và xếp vào trong kho. Sau một tuần hoàn thiện lô hàng cũ bác bắt tay vào làm lô hàng mới nhưng các khúc gỗ của bác đã bị các chú chuột trong kho làm đảo lộn với số gỗ cũ. Bác rất bực mình vì số gỗ mới là loại gỗ rất quý hiếm. Bác đã gắng công tìm chọn ra được n khúc gỗ, khúc gỗ thứ i có chiều dài là Ai ( Ai <102) nhưng bác đang loay hoay xem n đoạn gỗ trên có ghép thành đúng k khúc gỗ có chiều dài bằng nhau hay không?
	Yêu cầu: Hãy giúp bác Catgo ghép n đoạn gỗ thành K khúc gỗ có chiều dài bằng nhau.
	Dữ liệu vào: File văn bản CATGO.INP.
	Dòng 1: Hai số nguyên dương n và k mỗi số cách nhau 1 dấu cách 0 < k ≤ n ≤15).
	Dòng 2: Là n số tương ứng với chiều dài của n mảnh gỗ mà bác Catgo tìm được.
	Dữ liệu ra: File văn bản CATGO.OUT chỉ chứa số 1 nếu ghép được hoặc là số 0 nếu không thể ghép được.
Ví dụ: 
CATGO.INP
CATGO.OUT
5 3
1 4 6 9 10
1
5 3
1 4 6 9 9
0
Câu 3 (8 điểm): Số chung lớn nhất.
Cho 2 xâu:
 X = x1x2..xM; Y = y1y2..yN ( Với xi, yj là các kí tự số từ ‘0’ đến ‘9’, M, N ≤ 250).
Ta gọi: Z = z1z2..zk là xâu chung của 2 xâu X, Y nếu xâu Z nhận được từ xâu X bằng cách xoá đi một số kí tự và cũng nhận được từ xâu Y bằng cách xoá đi một số kí tự.
	Yêu cầu: Tìm một xâu chung của 2 xâu X, Y sao cho xâu nhận được tạo thành một số lớn nhất có thể được.
	Dữ liệu vào: File văn bản SCLN.INP.
	Dòng 1 là xâu X.
	Dòng 2 là xâu Y.
	Dữ liệu ra: File văn bản SCLN.OUT ghi số lớn nhất có thể nhận được.
Ví dụ:
SCLN.INP
SCLN.OUT
19012304 034012
34
1234567
21347
2347
HẾT
Họ và tên thí sinh :....................................................... Số báo danh .............................
Họ và tên, chữ ký: 	Giám thị 1:..........................................................................
Giám thị 2:..........................................................................