Đề thi chọn đội tuyển

PHÒNG GD-ĐT THANH SƠN

KHẢO SÁT CHUYÊN ĐỀ LẦN 1 ĐỘ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) CHIA CÁ
Ba người đi câu được một số lượng không lớn hơn N con cá. Mệt mỏi và trời đã tối, mỗi người tìm một nơi để ngủ. Khi trời gần sáng, người thứ nhất thức dậy, đếm số cá thấy nếu chia 3 thì dư một con bèn vứt một con cá xuống sông và đem về một phần ba số cá. Người thứ hai thức dậy tưởng hai người kia còn ngủ, đếm số cá thấy chia ba dư một nên vứt xuống sông một con rồi đem về một phần ba số cá. Người thứ ba thức dậy tưởng mình dậy sớm hơn cả anh ta đếm cá thấy chia ba dư một nên cũng vứt một con xuống sông và đem về một phần ba số cá.
Với một số N nhập từ bàn phím ( N<1000 ), hãy thông báo trên màn hình những khả năng có thể xảy ra về số lượng cá mà ba người câu được thoả mãn giả thiết đã cho.

Bài 2: (7,0 điểm) Dãy số tự nhiên a1 , a2 ,a3...  ak được gọi là hạnh phúc nếu nó thoả mãn các điều kiện sau : - Dãy trên là một dãy giảm dần . - Với mọi i ( 1<=i <= k ) ai hoặc là số nguyên tố , hoặc phải là ước của một trong các số a1 , a2 , ... , ai VD : 18 17 13 11 9 7 6 5 3 2 là dãy hạnh phúc Viết chương trình nhập 1 số tự nhiên N từ bàn phím và in ra màn hình một dãy số hạnh phúc càng dài càng tốt với số hạng đầu tiên là N.

Bài 3: (5,0 điểm)
Cho một dãy số gồm N số nguyên và một số nguyên dương k. Hãy tìm một dãy con dài nhất liên tiếp nhau sao cho tổng chia hết cho k.
Dữ liệu vào: từ file DAYSO.INP có dạng:
- Dòng đầu tiên là hai số N và k (N<=500000; k<=10000);
- Các dòng tiếp theo là N số nguyên của dãy (các số kiểu Longint), mỗi số trên một dòng.
Kết quả: ra file DAYSO.OUT gồm một dòng duy nhất chứa hai số m và s, trong đó m là độ dài lớn nhất tìm được và s là vị trí bắt đầu của dãy đó.

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