Kỳ thi chọn học sinh giỏi tỉnh lớp 12 năm học 2013 - 2014 - Môn Tin học

SỞ GD & ĐT NGHỆ AN KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12 
NĂ M HỌC 2013-2014 
Môn thi: TIN HỌC – THPT BẢNG A 
Thời gian: 150 phút (không kể thời gian giao đề) 
TỔNG QUAN BÀI THI 
Bài Tên file nguồn File Input File Output Thời gian chạy Điểm 
Bài 1 LAPTRINH.PAS LAPTRINH.INP LAPTRINH.OUT 1 giây 7 
Bài 2 DOANMAX.PAS DOANMAX.INP DOANMAX.OUT 1 giây 5 
Bài 3 XOASO.PAS XOASO.INP XOASO.INP 1 giây 5 
Bài 4 MAHOA.PAS MAHOA.INP MAHOA.UOT 1 giây 3 
Bài 1. (7 điểm) LAPTRINH 
Trong cuộc thi lập trình có N bài thi giải đúng yêu cầu đặt ra. Ban tổ chức quyết định trao giải phần 
thưởng đặc biệt cho bài thi tốt nhất, đó là bài thi có thời gian chạy chương trình ít nhất. Cho biết bài thi 
thứ i (1<=i<=N) có thời gian chạy là một số nguyên Ai (Tính theo đơn vị Centisecond, 1 Centisecond = 
1/100 giây). 
Yêu cầu: Hãy cho biết thời gian của bài thi được trao thưởng và có bao nhiêu bài thi được trao 
thưởng. 
Dữ liệu: Vào từ file văn bản LAPTRINH.INP 
- Dòng 1 chứa số nguyên dương N (N<=100). 
- Dòng 1 chứ N số nguyên A1 A2 An (0<=Ai<=100) 
Kết quả: Ghi ra file văn bản LAPTRINH.OUT 
- Dòng thứ 1 chứa một số nguyên là thời gian ít nhất tìm được. 
- Dòng thứ 2 chứa một số nguyên là số bài thi cùng đạt thời gian ít nhất 
Ví dụ. 
LAPTRINH.INP LAPTRINH.OUT 
5 
10 8 12 8 11 
8 
2 
Giải thích test ví dụ: thời gian ít nhất là f8 và có 2 bài cùng thời gian đó 
Bài 2. (5 điểm) ĐOẠN MAX 
Cho chuỗi ký tự S gồm các chữ cái in hoa (AZ) với độ dài không vượt quá 104. 
Yêu cầu: Hãi tìm đoạn con các kí tự liên tiếp dài nhất sao cho không có kí tự nào xuất hiện nhiều 
hơn một lần. Trong trường hợp có nhiều hơn một đoạn con có cùng chiều dài dài nhất, hãy chỉ ra đoạn 
xuất hiện đâu tiên trong chuỗi S. 
Dữ liệu: Vào từ văn bản DOANMAX.INP: 
- Gồm một dòng duy nhất chứa chuỗi S. 
Kết quả: Ghi ra file văn bản DOANMAX.OUT 
- chổ một dòng duy nhất chứa số nguyên P và L tương ứng là vị trí và chiệu dài của đoạn con dài 
nhất tìm được. 
Ví dụ: 
DOANMAX.INP DOANMAX.OUT 
ABABCDAC 3 4 
Lưu ý: Có 80% test có độ dài xâu không vượt quá 255. 
Giải thích test ví dụ: Đoạn con dài nhất tìm được là ABCD có vị trí 3 và dộ dài 4
Đề thi chính 
Bài 3. (5 điểm) XOÁ SỐ. 
Cho dãy số nguyên không âm A1 A2... An. Người ta muốn chọn 2 chỉ số i, j sao cho 1<=i<=j<=N và 
xoá khỏi dãy 2 số Ai, Aj để tổng giá trị các số còn lại trong dãy là số chẵn. 
Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thoả mãn. Hay các chọn khác nhau nếu tồn tại 
một chỉ số khác nhau. 
Dữ liệu: Vào từ file văn bản XOASO.INP 
- Dòng 1 chứ số nguyên dương N (N<=106) 
- Dòng 2 chứa N số nguyên không âm A1 A2An (Ai<=103) 
Kết quả: Ghi ra file XOASO.OUT 
- Chỉ một dòng duy nhất chứa một số nguyên là số cách chọn 2 chỉ số thoả mãn. 
Ví dụ: 
XOASO.INP XOASO.OUT 
5 
1 2 3 4 5 
6 
Lưu ý: Có 50% test có N<=1000. 
Giải thích test ví dụ: Có 6 cách chọn 2 chỉ số i, j là: 
i = 1, j=2 tổng còn lại A3+ A4+ A5 = 3 + 4 + 5 = 12 là số chẵn. 
Tương tự: i=1, j=4 và i=2; j=3 và i=2; j-5 và i=3; j=4 và i=4; j=5. 
Bài 4. MÃ HOÁ 
Nam rất thích thú với việc mã hoá dữ liệu. Trong buổi thảo luận ở lớp Nam đã trình bày một ý tưởng 
rất thú vị rằng bạn ấy vừa phát minh ra một cách mã hoá mới, có thể mã các thông tin mà không ai có thể 
giải mã. Cách mã hoá đó là: Với một số nguyên N, xoá các chữa số từ con số này bằng mọi cách có thể, ta 
sẽ nhận được các số mới. Một số cách xoá mà số mới thu được có giá trị bằng số cũ đó là khi ta xoá các 
chữ số 0 bên trái. Hãy tìm tổng của tất cả các con số mới thu được. Tổng này chính là mã hoá của N. 
Một bạn trong lớp đã có ý kiến “Mình nghĩ cách mã hoá của cậu trên máy tính sẽ thực hiện mất 
nhiều thời gian với số có nhiều chữ số, chẳng hạn só có 100 chữ số. Không thể chờ để có một mã số cho 
số có 100 chữ số. Cách mã hoá này của bạn không thể được áp dụng trên thực tế”. Nam đã trả lời “không, 
không, không”. Ngày mai mình sẽ đưa ra chương trình thực hiện cách mã hoá này, và sẽ mã hoá cho số có 
100 chữ số trong thời gian không quá 1 giây” câu trả lời của Nam được cả lớp rất hoan nghênh. Bạn hãy 
giúp Nam viết chương trình đó. 
Yêu cầu: Cho số nguyên N (1<=N<=10100) và xác định số nguyên S là mã hoá của N theo phương 
pháp mã hoá của Nam. 
Dữ liệu: Vào từ file văn bản MAHOA.INP 
Chỉ một dòng duy nhất chứa số nguyên N (chữ số bên trái các chữ số của N là khác 0). 
Kết quả: Đua ra file văn bản MAHOA.OUT 
- Chỉ một số duy nhất là số nguyên S tìm được. 
Ví dụ: 
MAHOA.INP MAHOA.OUT 
109 157 
Giải thích test ví dụ: 
N=109. Sau khi xoá chúng ta nhận được các số sau 
Vị trí xoá 1 2 3 1, 2 1, 3 2, 3 123 
Số mới 109 09 19 10 9 0 1 0 
Tổng các số thu được: 109+09+19+10+9+0+1+0=157. Vì vậy mã của 109 là 157 
Hồ Sỹ Hoàng – Trường THPT Quỳnh Lưu 2 
HƯỚNG DẪN GIẢI 
(Chú ý: Hướng dẫn không phải là đáp án của Sở, chỉ là hướng dẫn tham khảo, giải theo cách hiểu 
biết của cá nhân. Vì thế có thể không chính xác và cũng do làm trong thời gian ngắn nên có thể mắc một 
số lỗi nào đó) 
Câu 1. Câu này thì chắc các bạn đều biết cách giải. Và sẽ lấy được điểm tối đa 7 điểm. 
Program Cau1; 
Const fi='LAPTRINH.INP'; 
 fo= LAPTRINH .OUT'; 
var A:array[0..100] byte; 
 n,min,sl: Byte; 
Procedure Docdl; 
Var f:text; 
 i:Byte; 
 Begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 min:=255; 
 for i:=1 to n do 
 Begin 
 read(f,A[i]); 
 if min>A[i] then min:=A[i] 
 End; 
 Close(f) 
 End; 
Procedure Xuly; 
 var i:Byte; 
 Begin 
 sl:=0; 
 for i:=1 to n do 
 if A[i]=min then 
 inc(sl); 
 End; 
Procedure LuuKq; 
 var f:text; 
 Begin 
 assign(f,fo); Rewrite(f); 
 writeln(f,min) 
 write(f,sl); 
 Close(f); 
 End; 
BEGIN 
 DocDl; 
 XuLy; 
 LuuKq; 
END. 
Câu 2. Đều bài cho là XÂU nhưng lại có số lượng phần tử không vượt quá 104. Trong khi đó xâu 
chỉ có tối đa 255 ký tự. Vì vậy nếu bạn khai báo là Xâu thì chỉ lấy được 80% test tức là 4 điểm. Vậy làm 
thế nào để lấy được 100% test, bạn phải khai báo và xử lý dạng Mảng các ký tự. 
Thuật toán thì vẫn không có gì là khó vì nó gần giống bài Tìm đoạn đơn điệu dài nhất, duy chỉ khác 
nhau điểm dừng mà thôi. 
Program Cau2; 
Const fi='DOANMAX.INP'; 
 fo='DOANMAX.OUT'; 
var A:array[0..10000] of char; 
 n,cs,max:integer; 
Procedure Docdl; 
Var f:text; 
 Begin 
 assign(f,fi); reset(f); 
 n:=0; 
 while not eof(f) do 
 Begin 
 inc(n); 
 read(f,A[n]); 
 End; 
 Close(f) 
 End; 
Procedure Xuly; 
 var i,j,sl:integer; 
 tam:string; 
 Begin 
 max:=0; 
 for i:=1 to n-1 do 
 Begin 
 tam:=A[i]; 
 sl:=1; 
 j:=i+1; 
 while (pos(A[j],tam)=0) and (j<=n) do 
 Begin 
 tam:=tam+A[j]; 
 inc(sl); 
 inc(j); 
 End; 
 if sl>max then 
 Begin 
 max:=sl; 
 cs:=i; 
 End; 
 End; 
 End; 
Procedure LuuKq; 
 var f:text; 
 Begin 
 assign(f,fo); Rewrite(f); 
 writeln(f,cs,' ',Max); 
 Close(f); 
 End; 
BEGIN 
 DocDl; 
 XuLy; 
 LuuKq; 
END. 
Câu 3. Câu này nếu bạn xét tất cả mọi trường hợp i, j thì chắc chắn không thể lưu mảng với 1 triệu 
phần tử được. Và vòng lặp cũng rất lớn. 
Còn nếu bạn chỉ cần lấy 50% như trong đề thì hoàn toàn có thể vét cạn các trường hợp bằng cánh 
1. Đầu tiên tính tổng các phần tử vào biến T (tính 1 lần). 
2. Thử tất cả các trường hợp 
 For i:=1 to n-1 do 
 For j:=i+1 to n do 
 If (tong – A[i]-A[j] ) mod 2 = 0 then 
 Inc(dem); 
Nhưng để lấy được 100% test thì ta chú ý rằng. 
- Gọi SL là số phần tử lẽ, SN là số phần tử chẵn  SL có giá trị lẽ thì ta có Tổng là số lẽ, ngược lại 
SL có giá trị chẵn thì Tổng sẽ được số Chẵn. 
Vì vậy 
TH1: Nếu SL là số lẽ  cần xoá 1 số lẽ và một số chẵn  số cách xoá là SL*SN. 
TH2: Nếu SL là số chẵn  cần xoá 2 số lẽ hoặc 2 số chẵn  Sẽ có (SL2-SL + SN2-SN) cách xoá 
(Các bạn nhóm dãy số thành 2 nhóm sẽ nhận thấy được điều đó). 
Vậy bài toán của ta trở thành bải toán Đếm số lượng phần tử Lẽ và số lượng phần tử chẵn. 
Thuật toán như sau 
Program Cau3; 
Const fi='XOASO.INP'; 
 fo='XOASO.OUT'; 
var A:array[0..1] of longint; 
 n:longint; 
 Sl:longint; 
Procedure Docdl; 
Var f:text; 
 tam:integer; 
 Begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 for n:=1 to n do 
 Begin 
 read(f,tam); 
 inc(A[tam mod 2]); 
 End; 
 Close(f) 
 End; 
Procedure Xuly; 
 Begin 
 if( A[1] mod 2) = 1 then 
 Begin 
 Sl:=A[1]*A[0] 
 End 
 else 
 Begin 
 Sl:=(A[0]*A[0]-A[0]+A[1]*A[1]-A[1]) div 2 
 End; 
 End; 
Procedure LuuKq; 
 var f:text; 
 Begin 
 assign(f,fo); Rewrite(f); 
 write(f,Sl); 
 Close(f); 
 End; 
BEGIN 
 DocDl; 
 XuLy; 
 LuuKq; 
END. 
A[0] là số lượng phần tử Chẵn, A[1] là số lượng phần tử Lẽ 
Bạn cũng có thể thay phần đọc dữ liệu bằng 
Procedure Docdl; 
Var f:text; 
 tam:integer; 
 Begin 
 assign(f,fi); reset(f); 
 readln(f,n); 
 for n:=1 to n do 
 Begin 
 read(f,tam); 
 if tam mod 2 = 0 then inc(A[0]) 
 End; 
 A[1]:=n-A[0]; 
 Close(f) 
 End; 
Câu 4. Câu này thực tế mình chưa nghĩa ra thuật toán nào khác ngoài thuật toán Sinh xâu nhị phân. 
-B1: Đọc số trong tệp vào một xâu hoặc biến mảng ký tự. 
Giả sử độ dài số đó là N. 
Thì ta sẽ có 2N cách xoá. Nên ta dùng thuật toán sinh ra xâu nhị nhân N bít từ 
- B2: tạo xâu SD là xâu đầu tiên sẽ là: 0000 
- B3: tạo xâu SC là xâu cuối cùng sẽ là:11.11 
 Sẽ có 2N xâu như thế 
- B4: Ta sẽ cho SD chạy tới SC. 
- B5: Với mỗi giá trị của xâu SD ta lấy ra một sô. Bằng cách: Nếu SD[i]=’1’ thì giữ nguyên chữ số 
thứ i trong số ta đọc vào. 
Khi đó chương trình sẽ là 
Program Cau4; 
Const fi='MAHOA.INP'; 
 fo='MAHOA.OUT'; 
var 
 So:String; 
 n:Byte; 
 t:real; 
Procedure Docdl; 
Var f:text; 
 Begin 
 assign(f,fi); reset(f); 
 n:=0; 
 while not eof(f) do 
 Begin 
 inc(n); 
 read(f,So[n]); 
 End; 
 Close(f) 
 End; 
Function Conver(S:string): Real; 
 var i:byte; 
 tam:string; 
 num:real; 
 code:integer; 
 Begin 
 tam:=''; 
 for i:=1 to n do 
 if S[i]='1' then 
 tam:=tam+So[i]; 
 val(tam,num,code); 
 Conver:=Num 
 End; 
Procedure Xuly; 
 var i:integer; 
 Sd,Sc:String; 
 Begin 
 t:=0; Sd:=''; Sc:=''; 
 for i:=1 to n do 
 Begin 
 Sd:=Sd+'0'; 
 SC:=Sc+'1' 
 End; 
 while Sd<Sc do 
 Begin 
 i:=n; 
 while (Sd[i]='1') do 
 Begin 
 Sd[i]:='0'; 
 dec(i); 
 End; 
 Sd[i]:='1'; 
 t:=t+Conver(Sd); 
 End; 
 End; 
Procedure LuuKq; 
 var f:text; 
 Begin 
 assign(f,fo); Rewrite(f); 
 write(f,t:1:0); 
 Close(f); 
 End; 
BEGIN 
 DocDl; 
 XuLy; 
 LuuKq; 
END.