Kỳ thi chọn học sinh giỏi lớp 9 thcs năm học 2012 - 2013 môn thi: Tin học thời gian làm bài: 150 phút (không kể thời gian giao đề)

 Së Gd&§t kú thi CHäN häc sinh giái líp 9 tHCS
 Qu¶ng b×nh	 	 n¨m häc 2012- 2013
 M«n thi: tin häc
§Ò thi chÝnh thøc	 (Khãa thi ngµy 27 th¸ng 3 n¨m 2013)
Sè B¸o Danh: ............ Thêi gian lµm bµi: 150 phót (kh«ng kÓ thêi gian giao ®Ò)
	 (Đề thi gồm có 02 trang)
ĐỀ RA
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:
Câu 1: (3,0 điểm) Phần thưởng	PT.PAS
Trong cuộc thi giải toán qua mạng internet mỗi học sinh đều có số điểm tích lũy riêng của mình. Số điểm tích lũy của mỗi học sinh là một số nguyên dương K (0 < K ≤ 2´109). Đội tuyển của trường THCS Tài Năng có N học sinh tham gia dự thi (2 ≤ N ≤ 100). Tại buổi gặp mặt trước kỳ thi cấp tỉnh, thầy hiệu trưởng quyết định thưởng cho các học sinh trong đội tuyển Q triệu đồng, biết rằng điểm tích lũy của mỗi học sinh đều chia hết cho Q.
Yêu cầu: Hãy tìm số nguyên dương Q lớn nhất.
Dữ liệu vào: Cho trong file văn bản PT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số lượng học sinh.
- Dòng 2: Ghi N số nguyên dương lần lượt là điểm tích lũy của N học sinh, các số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản PT.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương Q tìm được.
Ví dụ: 
PT.INP
PT.OUT
5
15 24 45 36 27
3
Thời gian thực hiện chương trình không quá 1 giây cho mỗi bộ dữ liệu vào.
Câu 2: (3,5 điểm) Mật khẩu	MK.PAS
Cu Tí thường xuyên tham gia thi lập trình trên mạng. Vì đạt được thành tích cao nên Tí được gửi tặng một phần mềm diệt virus. Nhà sản xuất phần mềm cung cấp cho Tí một mã số là một số nguyên dương N có không quá 255 chữ số. Để cài đặt được phần mềm, Tí phải nhập vào mật khẩu của phần mềm. Mật khẩu là một số nguyên dương M được tạo ra bằng cách tính tổng giá trị các chữ số của N.
Yêu cầu: Hãy tìm số nguyên dương M.
Dữ liệu vào: Cho trong file văn bản MK.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N.
Dữ liệu ra: Ghi ra file văn bản MK.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương M tìm được.
Ví dụ: 
MK.INP
MK.OUT
84915388247
59
Câu 3: (3,5 điểm) Tần suất	TS.PAS
Cho tập hợp S có N phần tử nguyên dương {s1, s2,, sN}.
(1 ≤ N ≤ 32000; 0 < si ≤ 32000; 1 ≤ i ≤ N)
Yêu cầu: Hãy liệt kê các phần tử trong S có số lần xuất hiện lớn hơn một lần.
Dữ liệu vào: Cho trong file văn bản TS.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N.
- Dòng 2: Ghi N số nguyên dương là giá trị các phần tử của tập hợp S, các số được ghi cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản TS.OUT trên nhiều dòng, dòng thứ i ghi 2 số si di, hai số cách nhau một dấu cách. Trong đó si là phần tử xuất hiện trong S lớn hơn một lần và di tương ứng là số lần si xuất hiện. 
Ví dụ:
TS.INP
TS.OUT
7
2 5 5 3 5 3 9
3 2
5 3
==HẾT==
 Së Gd&§t	 	 	 kú thi CHäN häc sinh giái líp 9 THCS
 Qu¶ng b×nh	 	 n¨m häc 2012 - 2013
	 m«n: tin häc
 h­íng dÉn chÊm
I- Phương pháp:
- Giám khảo tạo bộ dữ liệu vào, tính toán kết quả. Thực hiện chương trình của học sinh và so sánh kết quả.
- Giám khảo có thể sử dụng chương trình gợi ý dưới đây để tính toán kết quả của dữ liệu vào.
- Chương trình học sinh đúng một bộ test, giám khảo cho 0.5 điểm. Như vậy, nếu một câu có 3 điểm thì giám khảo phải tạo 6 bộ test.
- Đối với câu 1: Giám khảo phải tạo được 01 bộ test có N = 100, 01 bộ test có các giá trị K > 65535 và 01 bộ test chấm được thời gian thực hiện chương trình của học sinh với N=100 và K > 65000´103.
- Đối với câu 2: Giám khảo phải tạo được 01 bộ test có K > 200.
- Đối với câu 3: Giám khảo phải tạo được 01 bộ test có N = 32000.
II- Chương trình gợi ý:
Câu 1: (3,0 điểm) Phần thưởng
Program Phan_thuong;
Const fi='PT.INP';
 fo='PT.OUT';
Type mmc=Array[0..101] of Longint;
Var N:Longint;
 A:mmc;
Function UCLN(x,y:Longint):Longint;
 Var sodu:Word;
 Begin
 sodu:=x mod y;
 While sodu0 do
 Begin
 x:=y;
 y:=sodu;
 sodu:=x mod y;
 End;
 UCLN:=y;
End;
Procedure Read_Data;
 Var f:text;
 i:Longint;
 Begin
 Assign(f,fi);
 Reset(f);
 Readln(f,N);
 For i:=1 to N do
 Read(f,A[i]);
 Close(f);
 End;
Function USC:Longint;
Var f:text;
 i,mUSC:longint;
Begin
 mUSC:=UCLN(A[1],A[2]);
 for i:= 3 to N do
 mUSC:=UCLN(mUSC,A[i]);
 USC:=mUSC;
End;
Procedure Write_Data;
Var f:Text;
Begin
 Assign(f,fo);
 Rewrite(f);
 Write(f,USC);
 Close(f);
End;
BEGIN
 Read_Data;
 Write_Data;
End.
Câu 2: (3,5 điểm) Mật khẩu
Program Mat_khau;
Const fi='MK.INP';
 fo='MK.OUT';
 A:Array['0'..'9'] of Byte = (0,1,2,3,4,5,6,7,8,9);
Var N:byte;
 St:String;
Procedure Read_Data;
 Var f:text;
 Begin
 Assign(f,fi);
 Reset(f);
 Readln(f,St);
 Close(f);
 End;
Function Tong:Longint;
Var f:text;
 i,T:Longint;
Begin
 T:=0;
 For i:=1 to Length(St) do
 T:=T+A[St[i]];
 Tong:=T;
End;
Procedure Write_Data;
Var f:Text;
Begin
 Assign(f,fo);
 Rewrite(f);
 Write(f,Tong);
 Close(f);
End;
BEGIN
 Read_Data;
 Write_Data;
End.
Câu 3: (3,5 điểm) Tần suất
{$R+}
const fi='TS.INP';
 fo='TS.INP';
type mmc=array[0..32000] of word;
var a:mmc;
 f:text;
 n,d:word;
 i,x:word;
 Time:Longint;Times:Longint absolute 0:$46C;
Begin
 Time:=Times;
 Fillchar(A,sizeof(A),0);
 assign(f,fi);
 reset(f);
 readln(f,n);
 For i:=1 to n do
 Begin
 read(f,x);
 a[x]:=a[x]+1;
 End;
 close(f);
 assign(f,fo);
 rewrite(f);
 For i:=0 to 32000 do
 if a[i]>1 then writeln(f,i,' ',a[i]);
 close(f);
 Writeln((Times-Time)/18.2:0:0);
 Readln;
End.