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

ĐỀ THI CHÍNH THỨC
SỞ GIÁO DỤC VÀ ĐÀO TẠO
NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THCS 
NĂM HỌC 2011 - 2012
Môn: Tin học 
Thời gian làm bài: 150 phút (không kể thời gian giao đề)
Đề thi gồm 03 câu được in trong 01 trang
Bài 1 - LUYTHUA. (8 điểm) – File bài làm luythua.pas
Cho 3 số nguyên dương x, n, b. Hãy tính số dư khi chia xn cho b.
Dữ liệu vào: File văn bản luythua.inp chứa 3 số x, n và b trên một dòng. 
Dữ liệu ra: File văn bản luythua.out chứa một số nguyên là đáp án của bài toán.
Giới hạn: Các số x, n, b nguyên dương và có giá trị không vượt quá 100.
Ví dụ:
luythua.inp
luythua.out
Giải thích:
302 = 900
900 mod 17 = 16
30	2	17
16
Bài 2 - TRAU. (8 điểm) – File bài làm trau.pas
Một đàn trâu có n con trâu. Trong đó có x con trâu đứng, y trâu nằm và z con trâu còn lại là trâu già. Các con trâu trong đàn ăn vừa hết m bó cỏ: mỗi con trâu đứng ăn đúng 5 bó, mỗi con trâu nằm ăn đúng 3 bó và các con trâu già thì ba con mới ăn hết 1 bó. Cho trước n và m, hỏi có bao nhiêu bộ số (x, y, z) thỏa mãn bài toán.
Dữ liệu vào: File văn bản trau.inp chứa 2 số n và m trên một dòng. 
Dữ liệu ra: File văn bản trau.out chứa một số nguyên là đáp án của bài toán.
Giới hạn: n, m, x, y, z nguyên dương và có giá trị không vượt quá 5000.
Ví dụ:
trau.inp
trau.out
Giải thích:
Có 1 bộ (x, y, z) thỏa mãn là (3, 1, 6) vì 3 + 1 + 6 = 10 và 3 x 5 + 1 x 3 + 6 / 3 = 20
10	20
1
Bài 3 - TFIB. (4 điểm) – File bài làm tfib.pas 
Cho số nguyên dương k và dãy số Fibonacci: 1, 1, 2, 3, 5, 8, ....(dãy số Fibonacci cho bởi công thức đệ quy sau: F1 = 1, F2 =1 và Fn = Fn-1 + Fn-2 với n > 2 ). Hãy biểu diễn k thành tổng của các số Fibonacci khác nhau với số lượng số hạng ít nhất có thể.
Dữ liệu vào: File văn bản tfib.inp chứa số nguyên dương k.
Dữ liệu ra: File văn bản tfib.out chứa các số hạng Fibonacci tìm được sắp xếp theo thứ tự giảm dần, các số ghi ra trên cùng một dòng.
Giới hạn: k nguyên dương và có giá trị không vượt quá109
Ví dụ:
tfib.inp
tfib.out
Giải thích:
27 = 21 + 5 + 1
và 21 > 5 > 1
27
21	5	1
Yêu cầu và giới hạn kỹ thuật: 
Ghi chính xác tên file bài làm và file dữ liệu vào ra.
Trên các file dữ liệu, 2 số cạnh nhau trên một dòng luôn cách nhau một khoảng trắng.
Mỗi bài có 60% số test có kích thước dữ liệu nhỏ.
Thời gian chạy mỗi bài không quá 1 giây / 1 test.
------ HẾT------
Họ và tên thí sinh:
Chữ ký của giám thị số 1.. 	Chữ ký của giám thị số 2..
SỞ GIÁO DỤC VÀ ĐÀO TẠO
NINH BÌNH
HƯỚNG DẪN CHẤM THI HỌC SINH GIỎI LỚP 9 THCS
Môn: Tin học
Năm học 2011 – 2012
I. HƯỚNG DẪN CHUNG
Chấm tự động bằng phần mềm AMM2 với các bộ test có sẵn trên đĩa CD.
II. ĐÁP ÁN VÀ THANG ĐIỂM
1. Cấu trúc bộ test và thang điểm
Bài
Test
Điểm
Bài 1
Gồm 16 bộ test, mỗi bộ 0.5 điểm.
8 điểm
Bài 2
Gồm 16 bộ test, mỗi bộ 0.5 điểm.
8 điểm
Bài 3
Gồm 8 bộ test, mỗi bộ 0.5 điểm.
4 điểm
2. Đáp án
const
 iFn = 'luythua.inp';
 oFn = 'luythua.out';
var
 F: Text;
 x, n, b, kq, i: LongInt;
BEGIN
 Assign(F, iFn); Reset(F);
 ReadLn(F, x, n, b);
 Close(F);
 kq := 1;
 for i:=1 to n do
 kq := kq * x mod b;
 Assign(F, oFn); ReWrite(F);
 Write(F, kq);
 Close(F);
END.
{------------------------------------}
const
 iFn = 'trau.inp';
 oFn = 'trau.out';
var
 F: Text;
 n, m: LongInt;
 dung, nam, gia: LongInt;
 dem: LongInt = 0;
BEGIN
 Assign(F, iFn); Reset(F);
 ReadLn(F, n, m);
 Close(F);
 Assign(F, oFn); ReWrite(F);
 for dung := 1 to n do
 for nam := 1 to n - dung do
 begin
 gia := n - dung - nam;
 if (gia > 0) and (dung * 15 + nam * 9 + gia = m * 3) then
Inc(dem); 
 end;
Write(F, dem);
Close(F);
END.
{------------------------------------}
const
 iFn = 'tfib.inp';
 oFn = 'tfib.out';
var
 F: Text;
 a: array[1..90] of LongInt;
 i, k: LongInt;
BEGIN
 Assign(F, iFn); Reset(F);
 ReadLn(F, k);
 Close(F);
 a[1] := 1; a[2] := 1; i := 2;
 while a[i] <= k do
 begin
 Inc(i); a[i] := a[i-1] + a[i-2];
 end;
 Assign(F, oFn); ReWrite(F);
 while k > 0 do
 begin
 if k >= a[i] then
 begin
 Write(F, a[i], ' ');
 k := k - a[i];
 end;
 Dec(i);
 end;
 Close(F);
END.