Kỳ thi chọn học sinh giỏi cấp tỉnh lớp 9 môn thi: Tin học thời gian: 150 phút (không kể thời gian phát đề)

	SỞ GIÁO DỤC VÀ ĐÀO TẠO	KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS
	BÌNH ĐỊNH	KHÓA NGÀY: 18-3-2016
	Đề chính thức	Môn thi:	TIN HỌC
	Thời gian:	150 phút (không kể thời gian phát đề)
	Ngày thi:	18/3/2016
Tổng quan đề thi:	(Đề thi có 02 trang)
Bài
Tên bài
Tên tệp
chương trình
Tên tệp
dữ liệu vào
Tên tệp
dữ liệu ra
1
Cặp số thân thiết (6,0 điểm)
SO_TT.PAS
Bàn phím
Màn hình
2
Dãy có giá trị lớn nhất (7,0 điểm)
DAYCON.PAS
DAYCON.INP
DAYCON.OUT
3
Đường đi tốt nhất (7,0 điểm)
DUONGDI.PAS
DUONGDI.INP
DUONGDI.OUT
Bài 1: Cặp số thân thiết (6,0 điểm):
Hai số nguyên dương được gọi là thân thiết nếu chúng có cùng ước số nguyên tố lớn nhất.
Hãy viết chương trình kiểm tra xem hai số nguyên dương có là cặp số thân thiết hay không?
Dữ liệu vào là hai số nguyên dương a, b (1< a, b <1010) nhập từ bàn phím.
Dữ liệu ra gồm: 
Ước nguyên tố lớn nhất của từng số;
Kết luận: “La cap so than thiet” hoặc “Khong than thiet”. 
Ví dụ:
Input
Output
Nhap hai so: 18 2016
UNTLN tuong ung: 3, 7
Khong than thiet
Input
Output
Nhap hai so: 50 15
UNTLN tuong ung: 5, 5
La cap so than thiet
Bài 2: Dãy có giá trị lớn nhất (7,0 điểm):
Cho một xâu S có chiều dài N (1≤N≤100) chỉ gồm các chữ số từ 1 đến 9 và một số nguyên dương k (k≤N). Hãy viết chương trình xóa bớt các ký tự trong xâu S để còn lại một xâu gồm k chữ số biểu thị số lớn nhất có k chữ số thu được theo cách này?
Dữ liệu vào là tệp DAYCON.INP có cấu trúc gồm hai dòng:
- Dòng thứ nhất chứa xâu S;
- Dòng thứ hai chứa số tự nhiên k.
Dữ liệu ra là tệp DAYCON.OUT là xâu có chiều dài k cần tìm.
Ví dụ:
DAYCON.INP
DAYCON.OUT
135792468
3
968
Bài 3: Đường đi tốt nhất (7,0 điểm):
Sân chơi là một mặt phẳng chia ra thành N hàng đánh số từ 1 đến N (1<N<100). Ở hàng thứ i (1≤ i ≤ N) có i ô điểm có giá trị cho trước là những số nguyên dương (không vượt quá 1000). Trò chơi là chọn một lộ trình với ô xuất phát là ô ở hàng thứ nhất, lần lượt đi qua một trong 2 ô lân cận ở hàng tiếp theo (theo hướng mũi tên) cho đến khi đến được một ô ở hàng cuối cùng và thu nhặt các điểm số có ở các ô trên đường đi qua (lộ trình sẽ thăm đúng N ô) (Hình vẽ dưới minh họa cho một ví dụ với N=4).
Cho trước một bảng biểu thị giá trị điểm số các ô trên từng hàng. Hãy lập trình tìm một lộ trình hợp quy định của luật chơi và thu được điểm số cao nhất.
Dữ liệu vào là tệp DUONGDI.INP có cấu trúc như sau:
- Dòng thứ nhất chứa số tự nhiên N;
- N dòng tiếp theo sẽ chứa các giá trị điểm số trên các ô điểm ở dòng tương ứng. Dòng thứ i sẽ có i giá trị. Các giá trị cách nhau một khoảng trắng.
Dữ liệu ra là tệp DUONGDI.OUT gồm 2 dòng:
	- Dòng thứ nhất chứa giá trị tổng điểm lớn nhất thu được theo lộ trình tối ưu;
	- Dòng thứ 2 chứa N số nguyên là giá trị các ô điểm mà lộ trình tối ưu đi qua.
8
5
1
2
6
9
3
4
2
3
	Ví dụ:
DUONGDI.INP
DUONGDI.OUT
4
8
5 1
2 6 9
3 4 2 3
23
8 5 6 4
	Chú ý: Nếu chỉ nêu được số điểm lớn nhất mà không chỉ được lộ trình đi thì được ½ số điểm của bài.
_______________________________
Bài 1: Cặp số thân thiết:
Program So_TT;
Uses Crt;
Var a,b:Longint;
Procedure Nhap;
Begin
 Clrscr;
 Write('Nhap hai so: ');
 Readln(a,b);
End;
Function Kt(n:Longint):Boolean;
Var i:Longint;
 d:Shortint;
Begin
 d:=0;
 Kt:=True;
 For i:=2 to Round(Sqrt(n)) do
 Begin
 If (n mod i)=0 then d:=d+1;
 If d>0 then
 Begin
 Kt:=False;
 Break;
 End;
 End;
End;
Procedure Xuli;
Var aa,bb,i,j:Longint;
Begin
 aa:=0;
 bb:=0;
 For i:=a downto 2 do
 If (a mod i =0) and (Kt(i)) then
 Begin
 aa:=i;
 Break;
 End;
 For j:=b downto 2 do
 If ((b mod j = 0) and Kt(j)) then
 Begin
 bb:=j;
 Break;
 End;
 Writeln('UNTLN tuong ung: ',aa,', ',bb);
 If aa=bb then
 Writeln('La cap so than thiet')
 Else
 Writeln('Khong than thiet');
 Readln
End;
Begin
 Nhap;
 Xuli;
End.
Bài 2: Dãy có giá trị lớn nhất:
Program Daymax;
Type
 Strings=String[100];
Const
 A:Array['1'..'9'] of Byte = (1,2,3,4,5,6,7,8,9);
 B:Array[1..9] of String = ('1','2','3','4','5','6','7','8','9');
 fi='D:\Daycon.Inp';
 fo='D:\Daycon.Out';
Var
 S:Strings;
 k:Byte;
 f:Text;
Procedure Nhap;
Begin
 Assign(f,fi);
 Reset(f);
 Readln(f,s);
 Read(f,k);
 Close(f);
End;
Function Vitri(S:Strings):Strings;
Var i,n,max:Byte;
Begin
 n:=Length(s);
 max:=1;
 For i:=2 to n-k+1 do
 If a[s[max]] < a[s[i]] then
 max:=i;
 Vitri:=Copy(s,max,n-max+1);
End;
Procedure Xuli;
Var cs,vt,n:Byte;
Begin
 Assign(f,fo);
 Rewrite(f);
 n:=Length(s);
 If n=k then Write(f,s)
 Else
 Begin
 s:=Vitri(s);
 cs:=1;
 Repeat
 vt:=pos(b[cs],s);
 While (vt0) and (n>k) do
 Begin
 Delete(s,vt,1);
 vt:=pos(b[cs],s);
 n:=Length(s);
 End;
 inc(cs);
 Until n=k;
 Writeln(f,s);
 End;
 Close(f);
End;
Begin
 Nhap;
 Xuli;
End.
Bài 3: Đường đi tốt nhất:
Program DuongDi;
Const
 maxN =100;
 fi='D:\Duongdi.Inp';
 fo='D:\Duongdi.Out';
Var 
 n:Word;
 A :Array[1..maxN,1..maxN] of Word;
 F :Array[0..maxN,0..maxN] of Word;
 g:Text;
 Procedure Nhap;
 Var i,j :Word;
 Begin
 Assign(g,fi);
 Reset(g);
 Read(g,n);
 For i:=1 to n do
 Begin
 For j:=1 to i do Read(g,A[i,j]);
 Readln(g);
 End;
 Close(g);
 End;
 Function Max(i,j:Word):Word;
 Begin
 If i>j then max:=i
 Else max:=j;
 End;
 Procedure Toiuu;
 Var i,j :Word;
 Begin
 For i:=1 to n-1 do
 Begin
 F[i,0]:=-1; F[i,i+1]:=-1;
 End;
 F[0,0]:=0; F[1,1]:=A[1,1];
 For i:=2 to n do
 For j:=1 to i do
 F[i,j]:=Max(F[i-1,j-1],F[i-1,j])+A[i,j];
 End;
 Procedure Truyvet(i,j :Word);
 Begin
 If (F[i,j]=F[i-1,j-1]+A[i,j]) then
 Dec(j);
 Dec(i);
 If (i>0) then
 Begin
 Trace(i,j);
 Write(g,a[i,j],' ');
 End;
 End;
 Procedure Xuat;
 Var i,iMax :Word;
 Begin
 Assign(g,fo);
 Rewrite(g);
 iMax:=1;
 For i:=2 to n do
 If (F[n,iMax]<F[n,i]) then iMax:=i;
 Writeln(g,F[n,iMax]);
 Truyvet(n,iMax);
 Write(g,a[n,iMax]);
 Close(g);
 End;
Begin
 Nhap;
 Toiuu;
 Xuat;
End.