Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học - Năm học 2013-2014 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT 
Kỳ thi thứ hai - Năm học 2013 – 2014
MÔN: TIN HỌC
Ngày thi: 03/12/2013
(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:
Bài
Chương trình
Input
Output
Thời gian chạy
1- Quà
QUA.PAS
QUA.INP
QUA.OUT
1giây/test
2- Số thân thiện
THANTHIEN.PAS
THANTHIEN.INP
THANTHIEN.OUT
1giây/test
3- Dãy không giảm
DAYCON.PAS
DAYCON.INP
DAYCON.OUT
2giây/test
Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên.
Câu 1: Quà (6 điểm).
Nhân dịp Lễ khai giảng năm học mới, một tổ chức từ thiện đã tặng quà cho học sinh của 1 trường ở địa phương dựa vào kết quả xếp loại năm học trước với mức quà như sau: Mỗi học sinh Giỏi được nhận 15 quyển vở, mỗi học sinh Khá được nhận 7 quyển vở, những học sinh còn lại được tặng mỗi em 1 quyển vở. 
Yêu cầu: Hãy xác định số học sinh Giỏi: G, số học sinh Khá: K và số học sinh còn lại: C. Biết rằng số quà đã được trao cho n học sinh và số quyển vở là m quyển. Cho trước n, m (10 < n < m < 10000). 
Dữ liệu vào: Tệp QUA.INP gồm 2 số nguyên n và m.
Dữ liệu ra: Tệp QUA.OUT Tất cả các đáp án tìm được, mỗi đáp án trên 1 dòng gồm 3 số G, K, C các số cách nhau ít nhất 1 dấu cách. 
Ví dụ:
QUA.INP
QUA.OUT
5 25
1 1 3
11 85
1 10 0
4 3 4
Câu 2: Số thân thiện (7 điểm).
Một số tự nhiên được gọi là số thân thiện nếu ta viết số đó theo chiều ngược lại thì sẽ được 1 số nguyên tố cùng nhau với chính số đó. Ta có số 23 là số thân thiện vì số 32 là số viết ngược của 23 và UCLN(23, 32) = 1. Số 12 là số không thân thiện vì 21 là số viết ngược của 12 và UCLN(12, 21) = 3. 
Yêu cầu: Hãy kiểm tra xem trong đoạn [10..n] có tất cả bao nhiêu số thân thiện.
Dữ liệu vào: Tệp THANTHIEN.INP chỉ có duy nhất 1 số n <= 30000.
Dữ liệu ra: 	Tệp THANTHIEN.OUT chỉ có duy nhất 1 số là số lượng số thân thiện trong đoạn [10..n].
Ví dụ: 
THANTHIEN.INP
THANTHIEN.OUT
20
6
30
9
Câu 3: Dãy không giảm (7 điểm).
Cho dãy số A gồm N số a1, a2, a3,, aN. Dãy số ai1, ai2,, aik thỏa mãn ai1 ≤ ai2 ≤≤ aik (1≤ i1 < i2 <  < ik ≤ N, k ³ 1) được gọi là dãy con không giảm của dãy A. Lưu ý các phần tử của dãy con có thể chọn có thể liên tiếp hoặc không liên tiếp từ các phần tử dãy A nhưng phải theo đúng thứ tự. Độ dài của dãy con là số lượng phần tử của dãy con đó.
Yêu cầu: Hãy tìm độ dài lớn nhất tìm được của dãy con không giảm của dãy A.
Dữ liệu: Vào từ tệp văn bản DAYCON.INP gồm 2 dòng:
Dòng đầu chứa một số nguyên dương N (1≤ N ≤ 105) là số phần tử dãy A;
Dòng thứ hai chứa N số nguyên dương ai (ai ≤ 105), giữa hai số cách nhau bởi một dấu cách.
Kết quả: Ghi ra tệp văn bản DAYCON.OUT một số nguyên dương là độ dài lớn nhất tìm được của dãy con không giảm của dãy A.
Ví dụ:
DAYCON.INP
DAYCON.OUT
8
5 1 6 4 5 2 1 7
4
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:..........................................................................