Kỳ thi chọn học sinh giỏi lớp 11 THPT năm học 2012 - 2013 môn thi: Tin Học

 SỞ GD&ĐT KỲ THI CHỌN HỌC SINH GIỎI LỚP 11 THPT
 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: 180 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) Tìm số TIMSO.PAS
Cho số nguyên dương X, khi đảo ngược trật tự các chữ số của X ta sẽ thu được một số nguyên dương Y, Y được gọi là số đảo ngược của X.
Ví dụ: X = 613 thì Y = 316 là số đảo ngược của X.
Số nguyên dương Y được gọi là số nguyên tố nếu nó chỉ có hai ước số là 1 và chính nó, số 1 không phải là số nguyên tố.
Cho hai số nguyên dương P và Q (1 ≤ P ≤ Q ≤ 2´109; Q - P ≤ 105).
Yêu cầu: Hãy tìm tất cả các số nguyên dương X nằm thỏa mãn P ≤ X ≤ Q và số đảo ngược của số X là số nguyên tố.
Dữ liệu vào: Cho trong file văn bản TIMSO.INP có cấu trúc như sau:
- Dòng 1: Ghi hai số nguyên dương P Q, hai 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 TIMSO.OUT trên nhiều dòng, mỗi dòng ghi một số nguyên X tìm dược.
Ví dụ:
TIMSO.INP
TIMSO.OUT
10 19
11
13
14
16
17
Câu 2: (3,5 điểm) Tính tổng	TONG.PAS
	Cho hai số nguyên dương M và N, M có p chữ số và N có q chữ số.
Yêu cầu: Tính tổng của hai số M và N.
Dữ liệu vào: Cho trong file văn bản TONG.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương p là số lượng chữ số của M (1 ≤ p ≤ 30000).
- Dòng 2: Ghi p chữ số của M theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách.
- Dòng 3: Ghi số nguyên dương q là số lượng chữ số của N (1 ≤ q ≤ 30000).
- Dòng 4: Ghi q chữ số của N theo thứ tự từ trái sang phải, các chữ 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 TONG.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương k là số lượng chữ số của tổng tìm được.
- Dòng 2: Ghi k chữ số của tổng tìm được theo thứ tự từ trái sang phải, các chữ số được ghi cách nhau ít nhất một dấu cách.
Ví dụ:
 TONG.INP
TONG.OUT
6
2 2 3 2 3 9
3
2 4 7
6
2 2 3 4 8 6 
(Có 85% số test với p, q ≤ 20000; 15% số test với p, q >20000 ).
Câu 3: (3,5 điểm) Dãy con chung dài nhất DAYCON.PAS
Cho dãy số nguyên A gồm N phần tử a1, a2, ..., aN và dãy số nguyên B gồm M phần tử b1, b2, ..., bM. Các phần tử trong một dãy số có giá trị khác nhau từng đôi một.
 (1 ≤ ai, bj ≤ 2´109; 1 ≤ N ≤ 100; 1 ≤ i ≤ N; 1 ≤ M ≤ 100; 1 ≤ j ≤ M).
Dãy C được gọi là dãy con của dãy A nếu dãy C nhận được từ dãy A bằng cách xóa đi một số phần tử và giữ nguyên thứ tự của các phần tử còn lại. 
Nếu dãy C là dãy con của dãy A và cũng là dãy con của dãy B thì dãy C được gọi là dãy con chung của hai dãy A và B.
Yêu cầu: Hãy tìm dãy C là dãy con chung của hai dãy A và B sao cho số lượng phần tử của dãy C là lớn nhất.
Dữ liệu vào: Cho trong file văn bản DAYCON.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số lượng phần tử của dãy A.
- Dòng 2: Ghi N số nguyên là giá trị của các phần tử trong dãy A, các số được ghi cách nhau ít nhất một dấu cách.
- Dòng 3: Ghi số nguyên dương M là số lượng phần tử của dãy B.
- Dòng 4: Ghi M số nguyên là giá trị của các phần tử trong dãy B, 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 DAYCON.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương K là số lượng phần tử của dãy C.
- Dòng 2: Ghi K số nguyên là giá trị của các phần tử trong dãy C, các số được ghi cách nhau một dấu cách.
- Dòng 3: Ghi K số nguyên dương lần lượt là chỉ số của các phần tử trong dãy A tương ứng với các giá trị của phần tử đó trong dãy C, các số được ghi cách nhau một dấu cách.
- Dòng 4: Ghi K số nguyên dương lần lượt là chỉ số của các phần tử trong dãy B tương ứng với các giá trị của phần tử đó trong dãy C, các số được ghi cách nhau một dấu cách.
Ví dụ:
DAYCON.INP
DAYCON.OUT
6
9 3 1 12 6 15
5
3 12 7 6 15 
4
3 12 6 15
2 4 5 6
1 2 4 5
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.
- Đối với câu 1: Giám khảo phải tạo được 06 bộ test, chương trình học sinh đúng 01 bộ test giám khảo cho 0.5 điểm. Trong 06 bộ test giám khảo phải tạo được 01 bộ test có Q-P = 105, 01 bộ test giá trị P, Q > 65535.
- Đối với câu 2: Giám khảo phải tạo được 07 bộ test, chương trình học sinh đúng 01 bộ test giám khảo cho 0.5 điểm. Trong 07 bộ test giám khảo phải tạo được 01 bộ test có P, Q > 20000.
- Đối với câu 3: 
+ Có thể có nhiều kết quả đúng, nếu học sinh đưa ra kết quả đúng nhưng khác với kết quả của giám khảo thì vẫn cho điểm tối đa.
+ Giám khảo phải tạo được 05 bộ test, chương trình học sinh đúng 01 bộ test giám khảo cho 0.7 điểm.
+ Đối với mỗi bộ test: Nếu học sinh đưa ra đúng số lượng phần tử của dãy con chung thì giám khảo cho 0.3 điểm, nếu đưa ra đúng dãy con chung giám khảo cho 0.2 điểm, nếu đưa ra đúng chỉ số của các phần tử trong dãy A và dãy B ban đầu thì giám khảo cho 0.2 điểm. Tổng điểm của mỗi test là 0.7 điểm.
II- Chương trình gợi ý:
Câu 1: (3,0 điểm) Tìm số
Program Tim_so;
Const fi='TIMSO.INP';
 fo='TIMSO.OUT' ;
Var P,Q:longint;
 Time:Longint;
 Times:Longint absolute 0:$46C;
Function NT(K:longint):Boolean;
Var Can,i:Longint;
Begin
 If (K=2) or (K=3) then Begin NT:=True;Exit; End;
 If (K<2) or (K mod 2 = 0) or (K mod 3 = 0) then
 Begin NT:=False; Exit; End;
 NT:=True;
 i:=5;
 Can:=Trunc(sqrt(K));
 While i<=Can do
 Begin
 if (K mod i = 0) or (K mod (i+2) =0) then
 Begin NT:=False; Exit; End
 ELse inc(i,6);
 End;
End;
Function Daoso(N:longint):longint;
Var S:longint;
Begin
 S:=0;
 While N0 do
 Begin
 S:=S*10+ (N mod 10);
 N:=N div 10;
 End;
 Daoso:=S;
End;
Procedure Read_Data;
Var F:text;
Begin
 Assign(f,fi);
 Reset(f);
 Read(f,P,Q);
 Close(f);
End;
Procedure Write_Data;
Var f:text;
 j:longint;
Begin
 Assign(f,fo);
 Rewrite(f);
 for j:=P to Q do
 if NT(Daoso(j)) then Writeln(f,j);
 Close(f);
End;
BEGIN
 Time:=Times;
 Read_Data;
 Write_Data;
 Writeln((Times-Time)/18.2:0:2);
 Readln;
END. 
Câu 2: (3,5 điểm) Tính tổng
 Program Tinh_tong;
Const fi= 'TONG.INP';
 fo= 'TONG.OUT';
 MaxN=30000;
 Type mmc=Array [0..MaxN] of byte;
Var N,M,Top:Longint;
 A,B:mmc;C:^mmc;
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]);
 Readln(f);
 Readln(f,M);
 New(C);
 Fillchar(C^,Sizeof(C^),0);
 For i:=1 to M do
 Read(f,C^[i]);
 Close(f);
 End;
Procedure Init;
 Var Tg,k:Longint;
 Begin
 If M=N then Begin Top:=N;B:=C^;Exit End;
 If N > M Then
 Begin
 Tg:=N-M;
 For K:=M Downto 1 do
 B[K+Tg]:=C^[K];
 Top:=N;
 End
 Else
 Begin
 Tg:=M-N;
 For K:=N Downto 1 do
 B[K+Tg]:=A[K];
 A:=C^;
 Top:=M;
 End;
 Fillchar(C^,Sizeof(C^),0);
 End;
Procedure Process;
 Var i,Nguyen,Tg:Longint;
 Begin
 Nguyen:=0;
 For i:= Top Downto 0 do
 Begin
 Tg:=(A[i]+B[i]+Nguyen);
 C^[i]:= Tg mod 10;
 Nguyen:=Tg Div 10;
 End;
 End;
Procedure Write_Data;
 Var f:text;i:Longint;
 Begin
 Assign(f,fo);
 Rewrite(f);
 if C^[0]>0 then
 Begin
 Writeln(f,Top+1);
 Write(f,C^[0],' ');
 End
 Else
 Writeln(f,Top);
 For i:=1 to Top do
 Write(f,C^[i], ' ');
 Close(f);
 Dispose(C);
 End;
BEGIN
 Read_Data;
 Init;
 Process;
 Write_Data;
END.
Câu 3: (3,5 điểm) Dãy con chung dài nhất
Program Day_con;
Const fi='DAYCON.INP';
 fo='DAYCON.OUT';
 MaxN=101;
Type mmc=Array[0..MaxN] of Longint;
 mhc=Array[0..MaxN] of mmc;
Var A,B,C:mmc;
 L:mhc;
 N,M,K:Longint;
 Time:Longint;
 Times: Longint absolute 0:$46C;
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]);
 Readln(f,M);
 For i:=1 to M do
 Read(f,B[i]);
 Fillchar(L,Sizeof(L),0);
 Close(f);
 End;
Procedure Solution;
 Var i,j:Longint;
 Begin
 For i:=1 to N do
 For j:=1 to M do
 Begin
 if A[i] = B[j] then
 L[i,j]:=L[i-1,j-1]+1
 Else
 Begin
 L[i,j]:=L[i,j-1];
 If L[i-1,j] > L[i,j-1] then
 L[i,j]:=L[i-1,j];
 End;
 End;
 End;
Procedure Write_Data;
 Var f:Text;i,j,Top:Longint;LA,LB:mmc;
 Begin
 Assign(f,fo);
 Rewrite(f);
 Writeln(f,L[N,M]);
 Top:=0;
 i:=N;j:=M;
 While (i>0) and (j>0) do
 Begin
 if A[i] = B[j] then
 Begin
 inc(Top);
 LA[Top]:=i;
 LB[Top]:=j;
 dec(i);
 dec(j);
 End
 Else
 if L[i-1,j] > L[i,j-1] then
 dec(i)
 Else
 dec(j);
 End;
 For i:=Top Downto 1 do
 Write(f,A[LA[i]],' ');
 Writeln(f);
 For i:=Top Downto 1 do
 Write(f,LA[i],' ');
 Writeln(f);
 For i:=Top Downto 1 do
 Write(f,LB[i],' ');
 Close(f);
 End;
BEGIN
 Time:=Times;
 Read_Data;
 Solution;
 Write_Data;
 Writeln((Times-Time)/18.2:0:0);
 Readln;
END.