Đề thi chọn GVG tin học

Sở GD&ĐT Nghệ An Kỳ chi chọn giáo viên dạy giỏi tỉnh
Cấp THPT chu kỳ 2008 - 2011
Môn thi: Tin học(phần lập trình)
Thời gian: 100 phút( không kể thời gian giao đề)

(Đề gồm 2 trang)


Bài 1( 5.0 điểm) Dãy hình sin
Cho dãy N số nguyên a1,a2, ..aN, trong đó không có 2 số nào liền kề bằng nhau. Dãy được gọi là hình sin bậc M nếu có M đoạn tăng, giảm ( hoặc giảm, tăng) xen kẽ nhau. Dãy không giảm (hoặc không tăng) được gọi là dãy hình sin bậc 0.
Ví dụ dãy 1 2 5 2-1-6 -2 7 là dãy hình sin bậc 3.
Yêu cầu: Cho dãy N số nguyên, cho biết dãy đó hình sin bậc mấy?
Dữ liệu vào cho từ file văn bản DAYSO.INP có cấu trúc sau:
- Dòng đầu tiên ghi số nguyên dương N ( 2 < N <= 1000) là số phần tử của dãy.
- Dòng thứ i trong N dòng tiếp theo ghi một số nguyên ai( ) là số thứ i của dãy
Kết quả ghi ra File văn bản DAYSO.OUT, ghi số M là bậc hình sin của dãy.


Bài 2 ( 4.0 điểm) Số Hoàn thiện
Số tự nhiên N được gọi là số hoàn thiện, nếu tổng các ước số của nó (không kể nó) bằng N.
Ví dụ số 28 là số hoàn thiện vì 28 = 1 + 2 + 4 + 7 + 14.
Yêu cầu: Cho trước 2 số tự nhiên R, S ( R< S ). Hãy viết chương trình tìm các số hoàn thiện N nằm trong đoạn [R;S] ( R N S).
Dữ liệu: Vào từ file văn bản SO.INP gồm 2 số R, S ( 1< R< S < 2.106) viết trên một dòng, mỗi số cách nhau một dấu cách.
Kết quả: Ghi ra file văn bản SO.OUT chỉ một dòng duy nhất gồm các số hoàn thiện tìm được trong đoạn [R;S] ghi theo thứ tự tăng dần, nếu không có số nào thì ghi -1.


Bài 3:( 4.0 điểm) Đường đi đến số 0
Mỗi một số nguyên dương đều có thể biểu diễn dưới dạng tích của 2 số nguyên dương X, Y sao cho X Y. Nếu như trong phân tích này ta thay X bởi X-1 còn Y bởi Y+1 thì sau khi tính tích của chúng ta thu được hoặc là một số nguyên dương mới hoặc là số 0 .
Ví dụ: Số 12 có 3 cách phân tích 1*12, 3*4, 2*6. Cách phân tích thứ nhất cho ta tích mới là 0: (1-1)*(12+1) = 0, cách phân tích thứ hai cho ta tích mới 10: (3-1)*(4+1) = 10, còn cách phân tích thứ ba cho ta 7: (2-1)*(6+1)=7. Nếu như kết quả là khác không ta lại lặp lại thủ tục này đối với số thu được. Rõ ràng áp dụng liên tiếp thủ tục trên, cuối cùng ta sẽ đến được số 0, không phụ thuộc vào việc ta chọn cách phân tích nào để tiếp tục.

Yêu cầu: Cho trước số nguyên dương N (1 N 10000), hãy đưa ra tất cả các số nguyên dương khác nhau có thể gặp trong việc áp dụng thủ tục đã mô tả đối với N.
Dữ liệu: Vào từ file văn bản Zeropath.Inp chứa số nguyên dương N.
Kết quả: Ghi ra file văn b