Đề thi chọn học sinh giỏi tỉnh lớp 11 năm 2013 - 2014

1SỞ GD & ĐT NGHỆ AN ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11
NĂM HỌC 2013-2014
(Đề gồm 2 trang)
Môn thi: TIN HỌC – THPT BẢNG A
Thời gian: 150 phút (không kể thời gian giao đề)
Bài Tên file nguồn File Input File Outout Thời gian 
chạy Điểm
Bài 1 THANHGO.PAS THANHGO.INP THANHGO.OUT 1 giây 5
Bài 2 MIN.PAS MIN.INP MIN,OUT 1 giây 6
Bài 3 SDD.PAS SDD.INP SDD.OUT 1 giây 5
Baì 4 SUBARR.PAS SUBARR.INP SUBARR.OUT 1 giây 4
Bài 1. (5 điểm)
THANH GỖ
Cha của Pinocchio muốn làm lại cho Picochio một cái mũi mới. Ông có N thanh gỗ, 
thanh gỗ i có độ dài ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để 
lấy ra thanh gỗ có độ dài cần thiết:
- Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio.
- Nếu còn nhiều hơn một thanh gỗ thì ông ta sẽ làm như sau:
Bước 1: Chọn ra thanh gỗ i có độ dài ai nhỏ nhất, tiếp theo chọn thanh gỗ j có độ 
dài aj nhỏ nhất trong các thanh còn lại.
Bước 2: Nếu ai = aj thì vứt bỏ bớt một thanh, quay về Bước 1.
Bước 3: Nếu ai < aj thì ra sẽ cắt khỏi thanh aj đi một đoạn bằng ai, quay lại Bước 1.
Yêu cầu: Hãy tính độ dài thanh gỗ mà ông ta nhận được để làm mũi cho Pinocchio.
Giới hạn: 1<=N <=10.000; 1<=ai<=109.
Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu tiên là số N, dòng sau là 
N số a1, a2, ., an.
Kết quả: Ghi ra file văn bản THANHGO.OUT: Số X là độ dài thanh gỗ tìm được.
(Các số trên cùng một dòng của file dữ liệu vào cách nhau ít nhất một ký tự trống)
Ví dụ
THANHGO.INP THANHGO.OUT
3
2 3 4
1
Bài 2. (6 điểm)
SỐ NHỎ NHẤT
Cho một số nguyên dương K và một xâu ký tự S. Xâu S chỉ gồm các ký tự là các chữ 
cái la tinh thường ‘a’ ‘z’ và các chữ số ‘0’ ‘9’, trong đó có ít nhất K ký tự là chữ số. 
Bạn hãy viết một chương gtrình loại bỏ một số ký tự ra khỏi xâu S sao cho K ký tự còn 
lại theo đúng thứ tự đó tạo nên số nhỏ nhất. Trong K ký tự còn lại có thể cho phép các 
chữ số 0 đứng đầu.
Dữ liệu vào: Vào từ file văn bản MIN.INP: Dòng thứ nhất là số nguyên dương K 
(K<=10). Dòng thứ hai ghi xâu S có độ dài nhỏ hơn 250.
Kết quả: Ghi ra file văn bản MIN.OUT: Gồm một dòng ghi ra K ký tự còn lại tạo 
nên số nhỏ nhất
Đề thi chính thức
2Ví dụ:
MIN.INP MIN.OUT
4
307uv5xly08mnp
0108
Bài 3. (5 điểm)
SỐ ĐƠN ĐIỆU
Số a1, a2,  , an được gọi là số đơn điệu nếu ai ai+2 hoặc ai > ai+1 < ai+2 (Với 
mọi i = 1..n-2). Số có một chữ số; số có hai chữ số khác nhau cũng được gọi là số đơn 
điệu lần lượt có độ dài bằng 1; 2
Ví dụ: các số 5, 58, 3748, 32435465768 là các số đơn điệu vì:
Số 5 có 1 chữ số
Số 58 có 2 chữ số khác nhau
Số 3748 có 34<8
Số 32435465768 ta thấy: 3>23456<8
Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu của 
một số cho trước.
Dữ liệu: Vào từ file văn bản SDD.INP: Gồm một số nguyên dương N có không quá 
75 chứ số.
Kết quả: Ghi ra file văn bản SDD.OUT: Chứa số nguyên là số chữ số lơn nhất tạo 
thành số đơn điệu của số N.
Ví dụ:
SDD.INP SDD.OUT
3748 4
Bài 4. (4 điểm)
SUBARRAY
Cho một dãy số nguyên a1, a2, . aN và số nguyên dương K. Dãy con ai, ai+1,  aj
(1<=i<=j<=N) là dãy được tạo từ các phần tử liên tiếp của dãy A, bắt đầu từ phần tử i và 
kết thúc ở phần từ j.
Yêu cầu: Tìm số lượng dãy con của A có ít nhất K phần tử bằng nhau.
Dữ liệu: Vào từ file văn bản SUBARR.INP:
Dòng đầu tiên cứa 2 số nguyên dương N, K (1<=k<=N<=4.105). Dòng thứ 2 chứa N 
số nguyên a1, a2, . aN (ai<=109)
Kết quả: Ghi ra file văn bản SUBARR.OUT: Ghi ra số lượng dãy con tìm được.
(Các số trên cùng một dòng của file dữ liệu vào ghi các nhau ít nhất một ký tự 
trống)
Ví dụ: 
SUBARR.INP SUBARR.OUT
4 2
1 2 1 2
3
------- Hết------
Chú ý: Giám thị không giải thích gì thêm.
3HƯỚNG DẪN GIẢI
(Hướng dẫn chỉ ở mức độ người giải, nên hoàn toàn không phải là đáp án. Vì thế có 
thể có rất nhiều lỗi hoặc không thể lấy được 100% điểm tối đa của bộ đề )
Bài 1.
- Về dữ liệu: 
+ Có N thanh gỗ trong đó N<=10.000  Cần màng 10.000 phần tử
+ Các Ai <=10
9 phải sử dụng kiểu Longint, longint chiếm 4 byte
Nên tổng bộ nhớ chiếm toàn bộ là: 10.000 x 4 = 40.000byte vẫn đáp ứng đủ.
- Về thuật toán:
+ Nếu chỉ còn 1 thanh thì lấy thanh đó làm Mũi
+ Nếu vẫn còn hơn 1 thanh ta thực hiện 3 bước
Bước 1: Chọn ra Ai nhỏ nhất trong các thanh, chọn Aj là thanh nhỏ thứ 2 (chọn 2 thanh 
nhỏ nhất)
Bước 2: Nếu Ai = Aj thì bỏ 1 thanh rồi quay về Bước 1 (Bỏ thanh Ai)
Bước 3: Nếu Ai<Aj thì lấy Aj = Aj - Ai rồi quay về Bước 1.
Ta nhận thấy: Nếu bước 1 chọn 2 phần tử nhỏ nhất, thì sau Bước 3 2 phần tử đó cũng sẽ 
là nhỏ nhất. Vì thế ta nhận thấy 3 Bước đó tạo nên thuật toán Tìm UCLN của 2 số nhỏ 
nhất trong dãy. Khi tìm được ước chung của 2 số nhỏ nhất rồi lấy ước đó và số nhỏ nhất 
tiếp theo để tìm UCLN Bài toán này trở thành bài toán: TÌM ƯỚC CHUNG LỚN 
NHẤT CỦA dãy số.
Như vậy về mặt kết quả thì ta cứ tìm CULN là được, chẳng cần phải từ từ tìm các số nhỏ 
nhất. Nhưng vì dữ liệu nhỏ nên mình sẽ code có cả phần sắp xếp như ý đồ và yêu cầu các 
bước của thuật toán.
Program THANHGO;
const fi='THANHGO.INP
 o='THANHGO.OUT
Var a:array[1..10000] of longint;
 i,j,l,n:longint;
Procedure DocDL;
Begin
 assign(input,fi); reset(input);
 readln(n);
 for i:=1 to n do read(A[i]);
 close(input);
End;
Procedure SapXep;
var tg,csm:longint;
 Begin
 for i:=1 to n -1 do
 Begin
 csm:=i;
 for j:= i+1 to n do
 if A[csm]>A[j] then csm:=j;
 if csmi then
4 Begin
 tg:=A[i];
 A[i]:=A[csm];
 A[csm]:=tg
 End;
 End;
 End;
Function Cat(a,b:integer):integer;
{thực tế đây là hàm UCLN nhưng thay vì sử dụng phép Trừ mình sử dụng phép 
Chi cho nhanh}
 Begin
 while (a0) and (b0) do
 if a>b then a:=a mod b
 else b:=b mod a;
 if a0 then Cat:=a
 else Cat:=b;
 End;
Procedure Xuly;
Begin
 for i:=1 to n-1 do
 A[i+1]:=Cat(A[i],A[i+1]);
End;
Procedure LuuKQ;
Begin
 assign(output,fo); rewrite(output);
 write(A[n]);
 close(output);
End;
Begin
 DocDL;
 XuLy;
 LuuKq;
End.
Bài 2:
- Về mặt dữ liệu: Bài yêu cầu dữ liệu là 1 xâu có độ dài không quá 250 phần tử  Nó là 
xâu bình thường trong Pascal.
+ K <=10 nên số nhỏ nhất cũng chỉ có tối đa 10 chữ số (longint đủ)
+Số nhỏ nhất có thể chứa các số 0 ở đầu Số nhỏ nhất nếu là số thì cần xử lý phần chữ 
số 0 đứng đầu. Đơn giản nhất ta vẫn để nó là XÂU (khi để là xâu thì K không còn quan 
trọng nữa).
- Về thuật toán (yêu cầu): Tìm ra số nhỏ nhất được lấy ra từ xâu S.
+ Rõ ràng ta cần tách ra một xâu gồm các ký tự chữ Số riêng (không tách thì điều kiện 
phức tạp hơn chút, chi phí tách xâu rất đơn giản và ít thời gian)
5+ Ta cần tìm lần lượt K phần tử trong xâu chử số: Mỗi phần tử là số nhỏ nhất có trong 
dãy được xét:
Chú ý: Khi ta chọn phần tử thứ i thì ta phải dành ra cho K – i phần tử cuối cùng cho các 
phần tử tiếp theo. Tức là nếu K = 10 thì khi ta chọn ra chữ số cho vị trí thứ 1 thì ta phải 
dành ra 10-1=9 chữ số cuối cùng cho 9 chữ số còn lại.
function Min(i,j:byte):byte;
var csm:byte;
Begin
 csm:=i;
 for i:=i+1 to j do
 if S[csm]>S[i] then
 csm:=i;
 Min:=csm;
Hàm này trả về vị trí ký tự nhỏ nhất đầu tiên trong xâu S kể từ vị trí I đến vị trí J
 Khi tìm chữ số đầu tiên thì i=1
Khi tìm vị trí chữ số x nào đó thì i bắt đầu tính từ i trước đó cộng với 1.
Thuật toán đầy đủ là:
Program MIN;
const fi='MIN.INP';
 fo='MIN.OUT';
Var S,s1:string;
 i,l,j,k:byte;
Procedure DocDL;
Begin
 assign(input,fi); reset(input);
 readln(k);
 readln(s);
 close(input);
End;
Function Loc(S:string):string;
var i:byte;
 tam:string;
Begin
 tam:='';
 for i:=1 to length(s) do
 if('0'<=S[i]) and (S[i]<='9') then
 tam:=tam+S[i];
 Loc:=tam;
End;
function Min(i,j:byte):byte;
var csm:byte;
Begin
 csm:=i;
 for i:=i+1 to j do
6 if S[csm]>S[i] then
 csm:=i;
 Min:=csm;
End;
Procedure Xuly;
Begin
 s:=Loc(s);
 l:=length(s);
 s1:='';
 i:=0;
 for j:=1 to k do
 Begin
 i:=Min(i+1,l-k+j);
 s1:= s1+ S[i]
 End;
End;
Procedure LuuKQ;
Begin
 assign(output,fo); rewrite(output);
 write(s1);
 close(output);
End;
Begin
DocDL;
XuLy;
LuuKq;
End.
Bài 3:
- Về mặt dữ liệu: Số đang xét có tối đa 75 chữ số, điều kiện đơn điệu xét cho từng chữ số
 dãy số là Dãy các chữ số của Số LỚN. Vì thế ta nên sử dụng Xâu để lưu số lớn.
- Về mặt thuật toán: Bài này rất giống các dạng như tìm đoạn đơn điệu tăng/giảm dài 
nhất của một dãy số. Thông thường gặp dạng này ta sữ dụng 2 chỉ số để lưu vị trí Đầu 
tiên và Kết thúc dãy một dãy đơn điệu và độ dài dãy đơn điệu dài nhất. Kết thúc của dãy 
này sẽ là bắt đầu của dãy tiếp theo.
Thuật toán
Program SODD;
const fi='SDD.INP';
 fo='SDD.OUT';
Var A:string;
 d:byte;
Procedure DocDL;
Begin
 assign(input,fi); reset(input);
 readln(a);
7 close(input);
End;
Procedure Xuly;
 var l,i,j:byte;
 d1:byte;
Begin
 l:=length(a);
 a:=a+a[l]; {mục đích để thuật toán dùng tại A[L]}
 j:=1;
 for i:=2 to l do
 if not (((a[i-1]a[i+1] ))or
 ((a[i-1]>a[i] ) and( a[i]<a[i+1] ))) then
 Begin
 d1:=i-j+1;
 if d1>d then d:=d1;
 j:=i;
 End;
 if d=0 then d:=l; {Nếu có 2 phần tử For vẫn chạy, nếu có 1 phần tử thì For không 
chạy D=0 nen d lấy bằng L=1}
End;
Procedure LuuKQ;
Begin
 assign(output,fo); rewrite(output);
 write(d);
 close(output);
End;
Begin
DocDL;
XuLy;
LuuKq;
End.
Bài 4. (4 điểm)
SUBARRAY
Cho một dãy số nguyên a1, a2, . aN và số nguyên dương K. Dãy con ai, ai+1,  aj
(1<=i<=j<=N) là dãy được tạo từ các phần tử liên tiếp của dãy A, bắt đầu từ phần tử i và 
kết thúc ở phần từ j.
Yêu cầu: Tìm số lượng dãy con của A có ít nhất K phần tử bằng nhau.
Dữ liệu: Vào từ file văn bản SUBARR.INP:
Dòng đầu tiên cứa 2 số nguyên dương N, K (1<=k<=N<=4.105). Dòng thứ 2 chứa N 
số nguyên a1, a2, . aN (ai<=109)
Kết quả: Ghi ra file văn bản SUBARR.OUT: Ghi ra số lượng dãy con tìm được.
(Các số trên cùng một dòng của file dữ liệu vào ghi các nhau ít nhất một ký tự 
trống)
8- Về mặt dữ liệu: Ai<=1.000.000.000 nên phải dùng Longint 4 Byte.
+ Gồm 400.000 phần tử Bộ nhớ cần cấp 400.000 x 4 = 1.600.000B vượt mức cho 
phép trong Pascal. Đây là vấn đề lớn, bởi lẽ chương trình THPT chỉ hướng dẫn trong 
khuôn khổ Pascal mà thôi. Nhưng thực tế phần mềm chấm điểm bây giờ lại sử dụng bộ 
dịch của Free Pascal vì thế bạn có thể khai báo lớn hơn nhiều sơ với Pascal.
Đây cũng là một điều mình thắc mắc trong các đề thi những năm gần đây. Liệu có thuật 
toán nào mà chỉ sử dụng trong phạm vi Pascal để giải quyết mọi trường hợp bài toán đặt 
ra hay không?
Nếu bạn lo về bộ nhớ lớn thì khuyên tạo ra nhiều code với các bộ dữ liệu lớn và 
nhỏ tách riêng ra. Nhằm lấy tối đa các Test.
Một vấn đề nữa là: nếu dãy có 400.000 phần tử bằng nhau cả, và với k=2 thì số lượng 
dãy số có ít nhất 2 phần tử bằng nhau sẽ là 400.000 + 399.999 + 399.998 +..+1+0 ~= 40
tỷ thì số Nguyên không thể chứa được ngoại trừ Int46 trong Free Pascal, Còn nếu không 
ta sử dụng số thực với kiểu Double
Là câu khó vì: Ta phải kiểm tra tất cả các dãy con có độ dài lớn hơn hoặc bằng k với số 
lượng phần tử là 400.000 phần tử. Thuật toán có thể không khó, nhưng chắc chắn sẽ vấp 
phải thời gian chạy (chạy quá thời gian nếu xét từng dãy 1).
- Thuật toán: 
+ Ta sử dụng một mảng để lưu Số lượng từng phần tử có trong dãy.
+ Dãy được xét bắt đầu từ i, lần lượt bổ sung phần tử j vào, bổ sung 1 phần tử thì tăng 
biến đếm của phần tử đó lên 1. Nếu biến đếm đó = K thì ta thấy đoạn Ai..Aj là một dãy 
thảo mãn đoạn Ai..Aj là đoạn con của Ai..AN nên ta có N-j+1 dãy con như thế.
+ Ta tăng i lên để xét doạn tiếp theo, khi tăng i tức là ta đã loại bỏ đi Ai ra khỏi danh sách 
 cần từ biếm đếm của phần tử Ai. Sau khi tăng i ta vẫn tiếp tục kiểm tra số lượng phần 
tử trong dãy  chỉ cần kiểm tra phần tử Aj (Loại bỏ thì chỉ giảm số lượng phần tử, nếu 
giảm đúng phần tử vừa bổ sung thì Aj mới giảm).
Trong đó biến I chạy từ 1 đến N-K +1; J chạy từ 1 đến N. 2 biến này chạy cùng nhau, tuỳ 
trường hợp mà cái nào tăng cái nào không tăng nên ta phải dùng lặp While.
Program SUBARRAY;
const fi='SUBARR.INP';
 fo='SUBARR.OUT';
Var
A:Array[1..400000] of longint;
D:Array[1..1000000000] of word; {K~65000}
sl:int64;
i,j,n,k:longint;
Procedure DocDL;
Begin
 assign(input,fi); reset(input);
 readln(n,k);
 for i:= 1 to N do
read(A[i]);
 close(input);
End;
9Procedure XuLy;
Begin
i:=1;
j:=0;
while (i<=n-k+1)and(j<=n) do
Begin
if D[A[j]]<k then 
Begin
j:=j+1;
D[A[j]]:=D[A[j]]+1;
End
Else
Begin
sl:=sl+1+N-j;
D[A[i]]:=D[A[i]]-1;
i:=i+1;
End;
End;
End;
Procedure LuuKq;
Begin
 assign(output,fo); rewrite(output);
 write(sl);
 close(output);
End;
Begin
DocDL;
XuLy;
LuuKq;
End.