Đề thi HSG Tin 9 tỉnh Bình Định năm 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH Đề chính thức KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS KHÓA NGÀY: 18-3-2016 Môn thi: Thời gian: Ngày thi: Tổng quan đề thi: TIN HỌC 150 phút (không kể thời gian phát đề) 18/3/2016 (Đề thi có 02 trang) Bài Tên bài 1 2 3 Cặp số thân thiết (6,0 điểm) Dãy có giá trị lớn nhất (7,0 điểm) Đường đi tốt nhất (7,0 điểm) 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 SO_TT.PAS Bàn phím Màn hình DAYCON.PAS DAYCON.INP DAYCON.OUT 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 Nhap hai so: 50 15 Output 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 968 3 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 (10 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); n:=Length(s); cs:=1; Repeat vt:=pos(b[cs],s); While (vt

0) 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]