Đề khảo sát đội tuyển

PHÒNG GD-ĐT THANH SƠN

KHẢO SÁT CHUYÊN ĐỀ LẦN 3 ĐỘI TUYỂN THI TỈNH
NĂM HỌC 2013 – 2014.
Môn Tin học- Lớp 9
(Thời gian làm bài 150 phút không kể thời gian giao đề )
( Đề thi có 01 trang )


Bài 1: (8,0 điểm) CHỮ SỐ THỨ M CỦA DÃY SỐ FIBONACI
Viết liền nhau liên tiếp các số FIBONACI từ 1 đến N theo thứ tự từ trái sang phải tạo thành một dãy các chữ số. Đánh số thứ tự các chữ số trong dãy bắt đầu từ một. Hãy viết chương trình đưa ra màn hình chữ số thứ M trong dãy hoặc thông báo KHONG TON TAI nếu không có chữ số thứ M. Các giá trị N, M nhập vào từ bàn phím

Bài 2: (7,0 điểm) Do sự phát triển của hệ thống thông tin, đất nước X cần phóng một vệ tinh truyền hình để có thể tiếp sóng cho các đài truyền hình địa phương. Đất nước X có n đài truyến hình địa phương cần phủ sóng: (n ≤ 1000): a1, a2, …, an. Đài a1 có tọa độ (xi, yi), (xi,yi nguyên, ( xi(, ( yi( ≤ 1000 )
Vùng phủ sóng của vệ tinh viến thông là một hình tròn. Để tiết kiệm chi phí, bạn cần xác định vùng phủ sóng có bán kính nhỏ nhất cho vệ tinh sao cho vệ tinh có thể phủ sóng cho tất cả n đài địa phương
Dữ liệu vào ghi vào một file văn bản có tên TVSAT.INP, có nội dung:
Dòng 1 ghi số n
N dòng tiếp theo ghi cặp số xi, yi
Dữ liệu ra ghi vào một file văn bản có tên TVSAT.OUT, có nội dung:
Dòng 1 ghi bán kính nhỏ nhất của vùng phủ sóng
Dòng 2 ghi tọa độ xM, yM của tâm vùng phủ sóng
( Các số thực được ghi với 2 chữ số sau dấu phẩy)

Bài 3: (5,0 điểm)
DÃY CON
Cho dãy N số nguyên A= (a1, a2, …, aN) và số nguyên dương M. Hãy tìm cách xóa bỏ trong dãy A một số phần tử sao cho dãy con thu được có nhiều phần tử nhất đồng thời trong dãy con này không có 2 phần tử nào có tổng chia hết cho M.
Chẳng hạn, với N = 5, M = 3, A = (1, 2, 3, 4, 5), dãy con dài nhất thu được có độ dài 3, có 4 dãy con như vậy, đó là (1, 2, 3); (1, 3, 4); (2, 3, 5); (3, 4, 5).
Dữ liệu (CONFLICT.INP)
Dòng 1: hai số nguyên N, M (1 ≤ N ≤ 105; 2 ≤ M ≤ 105).
Dòng 2: N số nguyên a1, a2, …., aN (|ai| ≤ 109
i = 1
N).
Kết quả (CONFLICT.OUT)
Dòng 1: số nguyên K là số phần tử của dãy con thu được.
Dòng 2: K số nguyên là chỉ số trong dãy ban đầu của các phần tử dãy con thu được, các số đưa theo trật tự tăng. Nếu có nhiều cách xóa cho dãy con độ dài K thỏa mãn yêu cầu bài toán thì chỉ cần đưa ra 1 cách.

––––––––––––––––––– Hết ––––––––––––––––––––
Chú ý: Cán bộ coi thi không giải thích gì thêm