SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN
ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng A)
Ngày thi: 30/9/2014
Thời gian: 180 phút (không kể phát đề)

Câu 1: TONG.PAS (7 điểm)
Cho dãy N số nguyên dương x1, x2, …, xn. Một dãy con của dãy nói trên là dãy được lập từ dãy
đã cho bằng cách bỏ đi một vài số hạng của dãy vàgiữ nguyên trật tự các số còn lại. Hãy tìm một
dãy con thoả mãn tính chất:
 Không cóba số liên tiếp nào của dãy ban đầu cómặt trong dãy con.
 Trong ba số liên tiếp của dãy ban đầu cóí
t nhất một số cómặt trong dãy con.
 Tổng các số hạng của dãy con được chọn làlớn nhất cóthể được.
Dữ liệu: Vào từ tệp CHONSO.INP:
 Dòng đầu tiên chứa số nguyên dương N (N≤1000)
 N dòng tiếp theo, dòng thứ i chứa số nguyên dương ai (ai≤30000)
Kết quả: Ghi ra tệp văn bản CHONSO.OUT:
 Dòng đầu tiên chứa hai số nguyên dương T vàM, trong đó T làtổng các số của dãy con
được chọn, M làsố lượng các số hạng của dãy con được chọn.
 M dòng tiếp theo lần lượt môtả vị trícủa số hạng được chọn trong dãy ban đầu.
Vídụ:
CHONSO.INP
CHONSO.OUT
6
21 4
2
2

6
3
5
5
1
6
7
3
Câu 2: DOCHOI.PAS (7 điểm)
Chia đồ chơi
Ba bạn An, Lợi, Bình cùng góp tiền để đi mua N món đồ chơi. Các đồ chơi được đánh số từ
1 đến N (N20). Trong đó món đồ chơi thứ i cósố tiền làa[i] (1a[i]10000). Cần chia N các đồ
chơi cho 3 người. Để công bằng ba bạn nhờ anh Nam phân chia giúp.
Gọi T1,T2,T3 lần lượt làtổng số tiền các món đồ chơi của mỗi người.
Gọi TongMax, TongMin lần lượt làgiátrị lớn nhất vànhỏ nhất của T1, T2, T3.
Yêu cầu :
Các bạn hãy giúp anh Nam phân chia đồ chơi cho các bạn sao cho chêch lệch TongMax và
TongMin lànhỏ nhất
Dữ liệu vào : Cho trong tệp văn bản DOCHOI.INP gồm 2 dòng:
 Dòng đầu chứa số nguyên N.
 Dòng thứ hai có N số nguyên a[i], các số cách nhau ít nhất một dấu cách.
Dữ liệu ra : Cho ra tệp văn bản DOCHOI.OUT gồm các dòng:
 Dòng đầu chứa số nguyên cho biết độ chênh lệch nhỏ nhất tìm được
 3 dòng tiếp theo, mỗi dòng cho biết thứ tự các món đồ chơi mà ba bạn trên nhận được.
Vídụ:


DOCHOI.INP
15
3 5 10 2 4 1 7 18 6 8 9 11 12 13 14


DOCHOI.OUT
0
1 2 3 4 5 6 7 11
8 12 13
9 10 14 15

Câu 3: DUONGDI.PAS (6 điểm)
Đường đi ngắn nhất
CóN tỉnh thành. An đi du lịch từ tỉnh P đến tỉnh Q. Biết rằng đường đi giữa 2 tỉnh thành làbất kỳ (nếu
có) đều là đường đi hai chiều. Sơ đồ mạng lưới giao thông của N tỉnh thành này cho bởi bảng vuông NxN
giátrị (ma trận) đối xứng A[i,j], trong đó A[i,i]=0 vàA[i,j]  0, A[i,j] làsố nguyên vàcóthể cócác giátrị
sau:
 A[i,j]>0 là độ dài đường đi từ thành phố i đến thành phố j.
 A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
 A[i,j] = A[j,i].
Dữ liệu vào: Cho trong tệp DUONGDI.INP gồm N+2 dòng:
 Dòng đầu làsố N ( N nguyên dương, N 50) .
 Dòng i+1 ( 1  i  N ) ghi N số nguyên dương A[i,1], A[i,2] .....A[i,N].
 Dòng N+2 ghi 2 số P vàQ.
Kết quả: Xuất ra tệp DUONGDI.OUT gồm 2 dòng:
 Dòng 1: Xuất ra câu thông báo độ dài của đường đi ngắn nhất từ P đến Q (như ví dụ), ngược lại
thông báo không có đường đi.
 Dòng 2: Sơ đồ đường đi (nếu có).
Vídụ:
DUONGDI.OUT
DUONGDI.INP
6
0
5

0
0
0
9
1
4
0
2
3
0
2

5
0
6
0
0
0
5

0
6
0
7
0
0

0
0
7

0
8
0

0
0
0
8
0
9

9
0
0
0
9
0

Duong di ngan nhan tu 1 den 5 dai 18
165

Khong co duong di tu 2 den 4
2
0
5
0
4

3
5

0
0

0
0
0
0

-----HẾT----Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ vàtên thísinh: ................................................... Số báo danh:.................................................
Chữ kýgiám thị 1: .................................................... Chữ kýgiám thị 2: ........................................


SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
LONG AN
Môn thi: TIN HỌC (bảng A)
Ngày thi: 30/09/2014
Thời gian: 180 phút (không kể thời gian phát đề)
(Hướng dẫn gồm 01 trang)
ĐỀ THI CHÍNH THỨC
HƯỚNG DẪN CHẤM THI
Câu 1: (7 điểm)
Gồm 4 test:
STT
1
2
3
4


CHONSO.INP
CHONSO1.INP
CHONSO2.INP
CHONSO3.INP
CHONSO4.INP

CHONSO.OUT
CHONSO1.OUT
CHONSO2.OUT
CHONSO3.OUT
CHONSO4.OUT

Các tệp dữ liệu vào vàra test được ghi trong CD đính kèm.
Câu 2: (7điểm)
Gồm 4 test:
STT
DOCHOI.INP DOCHOI.OUT
1
DOCHOI1.INP DOCHOI1.OUT
2
DOCHOI2.INP DOCHOI2.OUT
3
DOCHOI3.INP DOCHOI3.OUT
4
DOCHOI4.INP DOCHOI4.OUT

ĐIỂM
0,5+0,5
1+1
1+1

1+1

ĐIỂM
0,5+0,5
1+1
1+1
1+1

Các tệp dữ liệu vào vàra test được ghi trong CD đính kèm.
Câu 3: (6 điểm)
Gồm 4 test:
STT
1
2
3
4

DUONGDI.INP
DUONGDI1.INP
DUONGDI2.INP
DUONGDI3.INP
DUONGDI4.INP

DUONGDI.OUT
DUONGDI1.OUT
DUONGDI2.OUT
DUONGDI3.OUT
DUONGDI4.OUT

ĐIỂM

0,75+0,75
0,75+0,75
0,75+0,75
0,75+0,75

Các tệp dữ liệu vào vàra test được ghi trong CD đính kèm.
SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN
ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng B)
Ngày thi: 30/9/2014
Thời gian: 180 phút (không kể phát đề)

Câu 1: BAI1.PAS (7 điểm)
Cho số nguyên dương M, khi đảo ngược trật tự các chữ số của M ta sẽ thu được một số
nguyên dương N, N được gọi làsố đảo ngược của M.


Vídụ: M=38 thìN=83 làsố đảo ngược của M.
Cho hai số nguyên dương X và Y (1 ≤ X ≤ Y ≤ 2108; Y-X ≤ 105).
Yêu cầu: Hãy viết chương trình tìm tất cả các số nguyên dương M thỏa mãn X ≤ M ≤ Y
vàsố đảo ngược của số M làsố nguyên tố.
Dữ liệu vào: Cho trong tệp văn bản SO.INP cócấu trúc như sau:
Cho hai số nguyên dương X và Y, hai số được ghi cách nhau í
t nhất một dấu cách.
Dữ liệu ra: Ghi ra tệp văn bản SO.OUT trên nhiều dòng, mỗi dòng ghi một số nguyên M
tìm được.
Vídụ:

SO.INP
SO.OUT
12 22
13
14
16
17
20
Câu 2: BAI2.PAS (7 điểm)
Ma trận làmột bảng số gồm cóM dòng vàN cột. Một ma trận xoắn ốc làmột ma trận gồm các
con số được sắp xếp tăng dần theo một đường xoắn ốc.
Yêu cầu: Nhập vào một bảng số, sau đó sắp xếp các số để được một ma trận xoắn ốc.
Dữ liệu vào: Vào từ tệp văn bản MATRAN.INP

Dòng 1: Hai số M, N(2≤ M, N≤50)

M dòng tiếp theo mỗi dòng cóN số nguyên.
Dữ liệu ra: Ghi ra tệp MATRAN.OUT làma trận xoắn ốc kích thước MxN.
Vídụ: ( M=4, N =5)
Ma trận đã cho
Ma trận xoắn ốc
Chiều sắp xếp
2 5 1 7 9
0 1 1 1 2
1 12 2 5 6
5 6 7 8 2
0 3 3 1 8
5 12 11 9 2
4 11 4 2 3
4 4 3 3 3



Câu 3: BAI3.PAS (6 điểm)
Vào dịp cuối năm, công ty thưởng quàcho nhân viên, các phần quàđược sắp xếp thành một dãy,
đánh số từ 1 đến N, phần quàthứ i cógiátrị làai. Nhân viên được phép chọn phần quàcho mì
nh
theo nguyên tắc không được chọn ba phần quàliên tiếp nhau trong dãy các phần quà.
Yêu cầu: Hãy viết chương trình giúp nhân viên chọn các phần quàcủa công ty sao cho tổng giá
trị của các phần quàmànhân viên đó nhận được làlớn nhất.
Dữ liệu: Vào từ tệp văn bản PHANQUA.INP:

Dòng đầu ghi số nguyên N làsố phần quàcủa công ty (N25000)

Trong N dòng tiếp theo, dòng thứ i ghi số nguyên ai làgiátrị của phần quàthứ i (ai106)
Kết quả: Ghi ra tệp văn bản PHANQUA.OUT:

Dòng đầu tiên làtổng giátrị của các phần quà được lựa chọn.

Các dòng tiếp theo, lần lượt ghi vị trícủa các phần quàmànhân viên đó chọn, mỗi dòng
ghi đúng 10 vị trí,trừ dòng cuối cùng cóthể ít hơn 10.
Vídụ:
PHANQUA.INP
5
6
9
1
3
5

PHANQUA.OUT

23
1 2 4 5

-----HẾT----Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ vàtên thísinh: ................................................... Số báo danh:.................................................
Chữ kýgiám thị 1: .................................................... Chữ kýgiám thị 2: ........................................


SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
LONG AN
Môn thi: TIN HỌC (bảng B)
Ngày thi: 30/09/2014
Thời gian: 180 phút (không kể thời gian phát đề)
(Hướng dẫn gồm 02 trang)
ĐỀ THI CHÍNH THỨC
HƯỚNG DẪN CHẤM THI
Câu 1: (7 điểm)
Gồm 4 test:
STT
1

SO.INP
30
40

2

1000
1020


3

9956
10000

4

199999900
200000000

SO.OUT
30
31
32
34
35
37
38
1003
1004
1007
1009
1010
1015
1016
1018
9956
9958
9961

9962
9967
9968
9974
9986
9991
9992
9994
9998
199999900
199999904
199999918
199999919
199999925
199999931
199999934
199999940
199999942
199999952

ĐIỂM
1

2

2

2



199999972
199999988
199999991
200000000
Các tệp dữ liệu vào SO1.INP, SO2.INP, SO3.INP, SO4.INP tệp test được ghi trong CD
đính kèm.
Câu 2: (7điểm)
Gồm 4 test:
STT
1
2
3
4

MATRAN.INP
MATRAN1.INP
MATRAN2.INP
MATRAN3.INP
MATRAN3.INP

MATRAN.OUT
MATRAN1.OUT
MATRAN2.OUT
MATRAN3.OUT
MATRAN4.OUT

ĐIỂM
1
2
2

2

Các tệp dữ liệu vào vàra được ghi trong CD đính kèm.
Câu 3: (6 điểm)
Gồm 4 test:
STT
1
2
3
4

PHANQUA.INP
PHANQUA1.INP
PHANQUA2.INP
PHANQUA3.INP
PHANQUA4.INP

PHANQUA.OUT
PHANQUA1.OUT
PHANQUA2.OUT
PHANQUA3.OUT
PHANQUA4.OUT

ĐIỂM
0,75+0,75
0,75+0,75
0,75+0,75
0,75+0,75

Lưu ý: Trong câu 3 nếu tổng giátrị đúng, nhưng sai cách xuất ( mỗi dòng đúng 10 vị trí

, dòng
cuối cùng cóthể ít hơn 10) thì trừ 1,0 điểm.
Các tệp dữ liệu vào vàra được ghi trong CD đính kèm.
SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN
ĐỀ THI CHÍNH THỨC
(Đề thi gồm 3 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
LỚP 12 VÒNG 2 NĂM 2014
Môn thi: TIN HỌC
Ngày thi: 30 / 10 / 2014 (Buổi thi thứ nhất)
Thời gian: 180 phút (không kể thời gian phát đề)

Bài 1: Biểu thức – BIEUTHUC.PAS ( 6 điểm)
Cho một biểu thức chỉ gồm các kítự (, ), [, ], {, }. Một biểu thức đúng là một biểu thức khi
xóa từng cặp dấu ngoặc tương ứng ta thu được một xâu rỗng.
Yêu cầu: Nhập vào một biểu thức gồm nhiều kítự (chứa 6 loại kítự nêu trên) vàtìm cách
thêm một số í
t nhất các kítự thuộc một trong 6 loại kítự nêu trên để nhận được biểu thức đúng.
Vídụ: ( ] ) ( { ( } ) ( làbiểu thức không đúng
Biểu thức đúng là:
([])({()})()
Vìkhi xóa từng cặp dấu ngoặc (được in đậm) bên vế trái thu được kết quả bên vế phải lần
lượt như sau:


 Xóa ( [ ] ) ( { ( ) } ) ( )  ( ) ( { ( ) } ) ( )
 Xóa ( ) ( { ( ) } ) ( )  ( ) ( { } ) ( )
 Xóa ( ) ( { } ) ( )  ( { } ) ( )

 Xóa ( { } ) ( )  ( ) ( )
 Xóa ( ) ( )  ( )
 Xóa ( )  xâu rỗng.
Dữ liệu vào: Cho trong tệp BIEUTHUC.INP chứa một xâu thể hiện biểu thức gồm n kítự (n ≤
5000).
Dữ liệu ra: Ghi ra tệp BIEUTHUC.OUT làmột số nguyên chứa số lượng í
t nhất các kítự cần
phải thêm vào để được một biểu thức đúng.
Vídụ:
BIEUTHUC.INP
BIEUTHUC.OUT
(])({(})(
3
Giải thích: Xâu được thêm vào tối thiểu 3 kítự [ , ) , ) thành xâu ( [ ] ) ( { ( ) } ) ( ) là
một biểu thức đúng.
Bài 2: Vé tàu hỏa - VETAUHOA.PAS ( 7 điểm)
Tuyến đường sắt từ thành phố A đến thành phố B đi qua N nhà ga (1N104). Ta cóthể biểu
diễn các nhà ga như là các điểm trên đoạn thẳng AB. Nhàga A cósố hiệu 1, nhàga tiếp theo là
2,..., nhàga N tại B. Giá vé đi thẳng giữa hai nhà ga nào đó phụ thuộc vào khoảng cách giữa
chúng (km). Gọi khoảng cách giữa hai ga là x, cách tính giá vé như sau:
- Nếu 0  x  L1 thìgiávélàC1 (USD) ;
- Nếu L1< x  L2 thìgiávélàC2 (USD) ;
- Nếu L2 < x  L3 thìgiávélàC3 (USD) ;
Với L1, L2, L3 là độ dài đoạn đường xác định giávé( 1L1C1, C2, C3 lần lượt làgiávéứng với L1, L2, L3 ( 1C1Vé đi thẳng từ nhà ga này đến nhàga khác chỉ cóthể đặt mua nếu khoảng cách giữa chúng
không vượt quáL3. Vìthế để đi từ nhà ga này đến nhàga khác, nhiều khi ta phải mua một số vé.
Bạn Cường muốn đi du lịch từ thành phố S đến thành phố T. Vìkinh phíhạn hẹp nên Cường
quyết định đi bằng đường sắt.
1 Km

2 Km
4 Km
3 Km
5 Km
8 Km

Ga 1
A

Ga 2
S

Ga 3

Ga 4

Ga 5

Ga 6
T

Ga 7
B

Vídụ: với L1 = 3, L2 = 6, L3 = 8 ; C1 = 20 , C2 = 30 , C3 = 40.
Trên tuyến đường sắt đã cho, khoảng cách giữa ga 2 vàga 6 là12 > L3 = 8. Mặc dùkhoảng
cách từ ga 2 đến ga 6 là 12 nhưng không thể đặt mua 2 vévới giá C2 = 30 (chi phítổng cộng là
60) để đi từ ga 2 đến ga 6 vìmỗi véchỉ cógiátrị đi lại giữa hai nhà ga tương ứng. Ta cũng không
thể mua một vé đi thẳng từ ga 2 đến ga 6 vìkhoảng cách lớn hơn L3; có nhiều cách giải quyết
khác nhau, chẳng hạn:

Cách 1: Đi từ ga 2 đến ga 4 (khoảng cách 5 km < L2) thìmua vécógiáC2 = 30;
Đi từ ga 4 đến ga 5 (khoảng cách 5 Km < L2) thìmua vécógiáC2 = 30;
Đi từ ga 5 đến ga 6 (khoảng cách 2 Km < L1) thìmua vécógiáC1= 20.
Tổng tiền mua vétheo cách này là30 + 30 + 20 = 80.
Cách 2: Đi từ ga 2 đến ga 3 (khoảng cách 4 km < L2) thìmua vécógiáC2 = 30;
Đi từ ga 3 đến ga 6 (khoảng cách 8 Km < L3) thìmua vécógiáC3= 40;


Tổng tiền mua vétheo cách này là30 + 40 = 70.
Trong 2 cách trên thìcách 2 làcách mua vétiết kiệm hơn.
Yêu cầu: Bạn hãy giúp Cường tìm cách đặt mua vé để đi lại giữa hai nhà ga cho trước với
chi phí mua vé thấp nhất.
Dữ liệu vào: từ tệp văn bản VE.INP gồm
- Dòng đầu tiên ghi các số L1, L2, L3, C1, C2, C3;
- Dòng thứ 2 ghi số N làsố lượng nhàga;
- Dòng thứ 3 ghi 2 số nguyên lần lượt làsố hiệu nhàga S vàT ;
- Dòng thứ i trong N-1 dòng tiếp theo ghi một số nguyên làkhoảng cách từ nhàga 1 (tại A)
đến nhàga i+1 (i=1,2,...,N-1) .
Dữ liệu ra: ghi ra tệp VE.OUT một con số duy nhất làchi phíthấp nhất tìm được (biết rằng luôn
có cách mua vé để đi lại giữa hai ga bất kỳ).
Lưu ý: Các số trên cùng một dòng ghi cách nhau một dấu cách.
Vídụ:
VE.INP
VE.OUT
3 6 8 20 30 40
70
7
26
3
7

8
13
15
23
Bài 3: Giao hàng cho đại lý – GIAOHANG.PAS (7 điểm)
Công ty C làm ăn phát triển, hiện đang có N đại lý. N đại lýnày cần hàng gấp để giao hàng cho
các nơi bán lẻ. Đại lýi cần D[i] đơn vị hàng (1≤ 𝑖 ≤N). Hàng được cung cấp từ hai kho A vàkho
B của công ty C. Cước vận chuyển một đơn vị hàng từ kho A đến đại lýi làA[i] (1≤ 𝑖 ≤N). Cước
vận chuyển một đơn vị hàng từ kho B đến đại lýi làB[i] (1≤ 𝑖 ≤N). Biết kho A có R đơn vị hàng
và tổng số hàng của cả hai kho vừa đủ cung cấp cho N đại lý.
Yêu cầu: Hãy giúp công ty phân phối hàng từ hai kho A và B đến các đại lý sao cho tổng
cước phí vận chuyển là ít nhất.
Dữ liệu: vào từ tệp văn bản GIAOHANG.INP gồm 4 dòng:
 Dòng thứ nhất: chứa 2 số N vàR;
 Dòng thứ hai: chứa N số D[1], D[2], …, D[N] ;
 Dòng thứ ba: chứa N số A[1], A[2], …, A[N] ;
 Dòng thứ tư: chứa N số B[1], B[2], …, B[N] ;
Lưu ý:
- Dữ liệu là các số nguyên dương ;
- Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản GIAOHANG.OUT gồm 1 con số duy nhất là tổng chi phívận
chuyển í
t nhất.
Vídụ:
GIAOHANG.INP
5 50
15 40 40 25 20

Số lượng hàng 2 kho A, B giao cho các đại lý:
Đại Đại Đại Đại Đại

lý1 lý2 lý3 lý4 lý5
Kho hàng A
15
10
0
25
0
Kho hàng B
0
30
40
0
20

GIAOHANG.OUT
535


3 5 10 4 23
4 6 2 7 4
Tổng cước phívận chuyển (theo phương án giao hàng được tìm ra) được tính như sau:
(15* 3+10*5 + 0*10 + 25*4 + 0*23) + (0*4 + 30*6 + 40*2 +0*7 +20*4) = 535.

----- HẾT ----Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ tên thísinh: ................................................ SBD: .................................................................
Giám thị 1: ....................................................... Giám thị 2: .......................................................
Sở Giáo dục và Đào
KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
tạo

LỚP 12 VÒNG 2 NĂM 2014
LONG AN
Môn thi: TIN HỌC
ĐỀ CHÍNH THỨC

Ngày thi: 31 / 10 / 2014 (Buổi thi thứ hai)

HƯỚNG DẪN CHẤM
Bài 1: (6 điểm) NHOMXE.PAS. Đúng mỗi test được 1 điểm.
INPUT
OUTPUT
STT
File
Dữ liệu
File
Dữ liệu
500.00
1
NHOMXE1.INP Trong file NHOMXE1.OUT
2 4 6 8 10
67.53
NHOMXE2.
2
NHOMXE2.INP Trong file
1 2 4 5 6 7 9 11 12 13
OUT
15
61.75
NHOMXE3.
1 2 4 5 7 8 10 11 12 13

3
NHOMXE3.INP Trong file
OUT
14 15 16 17 18 21 23
25
173.29
NHOMXE4.
4
NHOMXE4.INP Trong file
1 4 5 7 9 11 12 14 15
OUT
20
173.51
1 2 6 7 8 9 11 12 15 16
NHOMXE5.
5
NHOMXE5.INP Trong file
17 18 20 21 22 26 27
OUT
28 29 30 31 32 34 35
39
227.88
4 7 8 10 11 12 14 15 16
NHOMXE6.
19 21 22 23 24 25 26
6
NHOMXE6.INP Trong file
OUT
27 28 32 34 36 37 39
40 41 42 43 45 46 48

49 51 52 53 54
Bài 2: (7 điểm) FOOD.PAS. Đúng mỗi test được 1 điểm.
INPUT
OUTPUT
Điểm

Điểm
0.5
0.5
0.5
0.5
0.5
0.5

0.5
0.5
0.5
0.5

0.5
0.5


ST
T
1

File

Dữ liệu

File

Dữ
liệu

FOOD.INP Trong file FOOD.OUT 4
1
1
1
2 FOOD.INP Trong file FOOD.OUT 3
1
2
2
3 FOOD.INP Trong file FOOD.OUT 8
1
3
3
4 FOOD.INP Trong file FOOD.OUT 1
1
4
4
5 FOOD.INP Trong file FOOD.OUT 2
1
5
5
6 FOOD.INP Trong file FOOD.OUT 3
1
6
6

7 FOOD.INP Trong file FOOD,OUT 2
1
7
7
Bài 3: (7 điểm) MAUTHEP.PAS. Đúng mỗi test được 1 điểm.
INPUT
OUTPUT
ST
Điểm
T
File
Dữ liệu
File
Dữ liệu
1 MAUTHEP
Trong file MAUTHEP
8.9443
1
1.INP
1.OUT
2 MAUTHEP2.INP Trong file MAUTHEP2.
13.1803
1
OUT
3 MAUTHEP3.INP Trong file MAUTHEP3.
9.2426
1
OUT
4 MAUTHEP4.INP Trong file MAUTHEP4.
195137.9701

1
OUT
5 MAUTHEP5.INP Trong file MAUTHEP5.
38058.3725
1
OUT
6 MAUTHEP6.INP Trong file MAUTHEP6.
69265.4380
1
OUT
7 MAUTHEP7.INP Trong file MAUTHEP7.
521400.3884
1
OUT
Lưu ý: Giải quyết trường hợp đồng điểm:
Giám khảo xem xét thuật giải của thí sinh để giải quyết.
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng A)
LONG AN
Ngày thi: 09/10/2015
ĐỀ CHÍNH THỨC
Thời gian: 180 phút (không kể phát đề)
(Đề thi gồm có03 trang)
Học sinh tạo thư mục làsố báo danh của mình trong đĩa D, lưu các bài làm với tên
BAI1.PAS, BAI2.PAS, BAI3.PAS vào thư mục vừa tạo
Bài 1: BAI1.PAS (7 điểm)
Trong trò chơi Zuma, cho một dãy các viên bi cóbốn màu bất kỳ là: xanh, đỏ, tím, vàng
liên tiếp nhau. Chúếch Zuma sẽ bắn một viên bi (cũng có màu là một trong bốn màu trên) chèn
vào dãy. Nếu viên bi mới chèn vào kết hợp với các viên bi bên trái hoặc bên phải vị tríchèn tạo
ra một dãy cótừ ba viên bi cùng màu trở lên thìchúếch sẽ ăn được các viên bi cùng màu đó. Các

viên bi còn lại sẽ sáp nhập lại, nếu tại vị trísáp nhập tạo ra một dãy cótừ ba viên bi cùng màu trở
lên thìchúlại tiếp tục được ăn. Cứ như vậy cho đến khi không còn dãy ba viên bi cùng màu trở
lên tạo ra từ vị trísáp nhập.
Vídụ: Cho dãy 11 viên bi như sau (X: xanh, D: đỏ, T: tím, V: vàng): TTXDDXXXVVV
Zuma bắn một viên bi màu đỏ vào vị tríthứ 4 sẽ tạo ra dãy bi sau (bi đỏ được chèn vào vị
tríthứ 4): TTXDDDXXXVVV.
Bi bắn vào tạo ra dãy 3 bi đỏ, như vậy chú ăn được 3 bi đỏ, dãy còn lại là: TTXXXXVVV.
Một bi xanh bên trái sáp nhập với ba bi xanh bên phải tạo thành một dãy 4 bi xanh nên Zuma ăn
tiếp 4 bi này, dãy còn lại là: TTVVV (Dù dãy này có 3 bi vàng nhưng không được ăn vì 3 bi này
không phải do sáp nhập từ hai phía). Vậy Zuma ăn được tổng cộng 7 bi (3 đỏ, 4 xanh).
Yêu cầu: Cho trước dãy bi cóbốn màu X, D, T, V bất kỳ vàmột viên bi dùng để bắn ra có
một trong bốn màu trên vàvị trík chúếch sẽ bắn, bạn hãy giúp Zuma tính xem ăn được bao nhiêu
viên bi khi bắn vào vị trík.
Dữ liệu vào: Cho trong tệp BANBI.INP cóhai dòng:
- Dòng đầu tiên gồm dãy kýtự X, D, T, V biểu thị màu sắc các viên bi. Các kýtự
được viết sát nhau .
- Dòng thứ hai làmột số nguyên k (1≤k≤chiều dài của dãy bi) làvị tríbắn vàmột
kýtự làmột trong bốn kýtự X, D, T, V).
Dữ liệu ra: ghi ra tệp BANBI.OUT chứa kết quả là tổng số viên bi mà Zuma ăn được.
VÍ DỤ
BANBI.INP
BANBI.OUT
1
TTXDDXXXVVV
7
4D
2
XDTV

0
3T
3
XXXXXX
0
4T
Bài 2: BAI2.PAS (7 điểm)
Người ta xây dựng một dãy số A gồm các phần tử là các số nguyên dương tăng dần từ
1 đến vôcùng theo quy tắc: phần tử đầu tiên là số chia hết cho 1 (hiển nhiên là số 1), tiếp theo là
hai số chia hết cho 2, tiếp theo là ba số chia hết cho 3, .....
Theo quy tắc trên ta có dãy số A:
(chia hết 4)
(chia hết 2)
1, 2, 4, 6, 9, 12, 16, 20, 24, 28, 30, 35, 40, 45, 50, ..........
(chia hết 3)

(chia hết 5)

Yêu cầu: Cho số nguyên K, hãy xác định số nguyên có vị trí thứ K của dãy số A.
Dữ liệu vào: Cho từ tệp CHIAHET.INP gồm một dòng duy nhất chứa số K (1≤K≤100000).
Dữ liệu ra: Ghi ra tệp CHIAHET.OUT một dòng duy nhất chứa số thứ K trong dãy số.
Ví dụ:
CHIAHET.INP
CHIAHET.OUT
10
28
Giải thí
ch:
Dãy số: 1, 2, 4, 6, 9, 12, 16, 20, 24, 28, 30, 35, 40, 45, 50, ….. Số thứ 10 của dãy số
là28.

Bài 3: BAI3.PAS (6 điểm)
Sau một số rủi ro và thất bại trong kinh doanh, tổng giám đốc công ty A quyết định tổ chức
cho các giám đốc của các đại lý thuộc công ty gặp mặt và thảo luận với nhau. Công ty A là một
công ty cực kì lớn trải khắp toàn cầu nên một vấn đề lớn đặt ra là làm sao tổ chức cho hai giám
đốc gặp nhau trong thời gian sớm nhất. Vấn đề đặc biệt trở nên hóc búa vì các giám đốc của công
ty chỉ được đi bằng mạng giao thông của công ty để đảm bảo an toàn, bảo mật và chi phí. Nhưng
mạng này lại hơi tệ:
- Các giám đốc buộc phải di chuyển theo các tuyến giao thông giữa các đại lý.
- Mạng giao thông của công ty làmạng gồm các tuyến đường một chiều.
- Các giám đốc khi đi trong mạng thìmỗi giờ đi được theo đúng một tuyến đường
vàphải liên tục di chuyển cho đến khi hai giám đốc gặp nhau tại một đại lý nào đó thì dừng lại
(các giám đốc không được dừng lại để chờ giám đốc kia đến).
- Các giám đốc khi đi phải xuất phát cùng lúc.
Tuy mạng hơi tệ nhưng là mạng nội bộ nên không có chuyện tắc đường. Vì vậy, trong một
giờ luôn có thể di chuyển từ đại lý này sang đại lý khác nếu có đường. Tổng giám đốc muốn nhân
viên của mình không lãng phí thời gian. Bởi vậy, ông muốn tính thời gian ngắn nhất mà hai giám
đốc ở hai đại lý cho trước có thể gặp nhau. Đáng tiếc là tổng giám đốc chỉ giỏi kinh doanh, còn
lập trình thì quá yếu kém.
Yêu cầu: Bạn hãy viết chương trình giúp tổng giám đốc sắp xếp lịch đi của hai giám đốc
sao cho thời gian ít nhất.
Dữ liệu vào: Cho từ tệp DAILY.INP gồm ba dòng:
- Dòng đầu ghi hai số N, M làsố đại lývàsố tuyến đường trong mạng giao thông
của công ty A. (0- Dòng thứ hai ghi S,T lần lượt làsố thứ tự hai đại lýcóhai giám đốc cần phải gặp
nhau (0- M dòng tiếp theo mỗi dòng ghi hai số nguyên U, V thể hiện có đường đi một chiều
từ U tới V (0- Các số trên một dòng viết cách nhau ít nhất một dấu cách.

Dữ liệu ra: Ghi ra tệp DAILY.OUT gồm một dòng duy nhất chứa thời gian nhỏ nhất hai
giám đốc có thể gặp nhau.
Ví dụ:
DAILY.INP
DAILY.OUT
67
3
15
12
45
23
34
41
54
56
Giải thích :
Giám đốc 1: Đi từ đại lý 1 đại lý 2 đại lý 3 đại lý 4. Tổng thời gian: 3 giờ.
Giám đốc 2: Đi từ đại lý 5 đại lý 4 đại lý 5 đại lý 4. Tổng thời gian: 3 giờ (Vì
các giám đốc liên tục di chuyển không được dừng lại).
Vậy tổng thời gian gặp nhau ngắn nhất của hai giám đốc là 3 giờ.
---- Hết ----


Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ vàtên thísinh:................................................Số báo danh: ...................................................
Chữ kýgiám thị 1: ...............................................Chữ kýgiám thị 2: ..........................................


SỞ GIÁO DỤC VÀ ĐÀO TẠO

LONG AN
ĐỀ CHÍNH THỨC
(Hướng dẫn gồm có01 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng A)
Ngày thi: 09/10/2015
Thời gian: 180 phút (không kể phát đề)
HƯỚNG DẪN CHẤM

Câu 1: BAI1.PAS(7 điểm)
Gồm 4 test
STT
BANBI.INP
BANBI.OUT
1
BANBI1.INP
3
2
BANBI2.INP
10
3
BANBI3.INP
22
4
BANBI4.INP
61
Các tệp dữ liệu vào và ra test được ghi trong CD đính kèm
Câu 2: BAI2.PAS(7 điểm)
Gồm 4 test:

STT
CHIAHET.INP
CHIAHET.OUT
1
CHIAHET1.INP
198
2
CHIAHET2.INP
754
3
CHIAHET3.INP
7532
4
CHIAHET4.INP
235316
Các tệp dữ liệu vào và ra test được ghi trong CD đính kèm.
Câu 3: BAI3.PAS(6 điểm)
Gồm 4 test:
STT
DAILY.INP
DAILY.OUT
1
DAILY1.INP
6
2
DAILY2.INP
2
3
DAILY3.INP
5

4
DAILY4.INP
4

ĐIỂM
1
2
2
2

ĐIỂM
1
2
2
2

ĐIỂM
1.5
1.5
1.5
1.5

Các tệp dữ liệu vào và ra test được ghi trong CD đính kèm.
* Nếu đồng điểm thìchọn thísinh cóthuật toán tốt hơn

SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng B)

Ngày thi: 09/10/2015
Thời gian: 180 phút (không kể phát đề)

ĐỀ CHÍNH THỨC
(Đề thi gồm có02 trang)
Học sinh tạo thư mục làsố báo danh của mì
nh trong đĩa D, lưu các bài làm với
tên BAI1.PAS, BAI2.PAS, BAI3.PAS vào thư mục vừa tạo
Bài 1: BAI1.PAS (7 điểm)


Cho hai chuỗi là ngày tháng năm M, N. Ngày tháng năm có dạng dd/mm/yyyy. Nếu ngày
nhỏ hơn 10 vàtháng nhỏ hơn 3 thìcósố 0 ở phía trước. Vídụ: 05/6/2015; 12/01/2015; 04/02/2015;
25/10/2015 (01/01/1900≤MYêu cầu: Tính số ngày giữa hai giátrị ngày tháng năm.
Dữ liệu vào: cho tệp NGAY.INP gồm hai dòng:
- Dòng đầu tiên ngày tháng năm thứ nhất (M).
- Dòng thứ hai ngày tháng năm thứ hai (N).
Dữ liệu ra: ghi vào tệp NGAY.OUT số ngày giữa hai giátrị ngày tháng năm.
Vídụ BIẾN NGAY.INP
NGAY.OUT
M
01/12/2015
9
1
N
10/12/2015
M
22/9/2015
110

2
N
10/01/2016
Bài 2: BAI2.PAS (7 điểm)
Xét dãy A các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89…
Dãy B gồm các số thu được từ dãy A bằng cách ghép hai số liên tiếp trong A: 23, 57, 1113,
1719, 2329, 3137, 4143, 4753, 5961, 6771, 7379, 8389…
Trong dãy B có những phần tử là số nguyên tố. VD: 23, 3137, 8389, 157163…
Các số nguyên tố trong dãy B gọi là số nguyên tố ghép.
Yêu cầu: Cho trước số nguyên dương K ≤ 500, hãy tìm số nguyên tố ghép thứ K.
Dữ liệu vào: Cho từ tệp NT.INP gồm một số nguyên dương K duy nhất.
Dữ liệu ra: Ghi ra tệp NT.OUT một số nguyên dương duy nhất là số nguyên tố ghép thứ K.
Ví dụ:
NT.INP
NT.OUT
2
3137
Bài 3: BAI3.PAS (6 điểm)
Có N người xếp hàng mua vé, được đánh số theo thứ tự từ 1 đến N. Thời gian phục vụ bán
vé cho người thứ i làti. Mỗi người cần mua một vé nhưng được quyền mua tối đa hai vé, vìthế
một số người cóthể nhờ người đứng ngay trước mì
nh mua hộ. Người thứ i nhận mua hộ vécho
người thứ i+1 thìthời gian mua vécho hai người làri.
Yêu cầu: Tìm phương án sao cho N người đều cóvévới thời gian í
t nhất.
Dữ liệu vào: Cho từ tệp VE.INP gồm ba dòng:
- Dòng thứ nhất ghi số nguyên dương N (1- Dòng thứ hai ghi N số nguyên dương t1, t2, ..., tn
- Dòng thứ ba ghi N-1 số nguyên dương r1, r2, ..., rn-1

Dữ liệu ra: ghi ra tệp VE.OUT một dòng duy nhất là tổng thời gian phục vụ bán vé
Vídụ
VE.INP
5
2 5 7 8 4
3 9 10 10

VE.OUT
17

Giải thí
ch:
Người 1 mua hộ vé cho người 2 chi phí là 3 giây (Vì nếu người 1 và người 2 mua vé
thì chi phí là 2+5=7 giây lớn hơn chi phí người 1 mua hộ là 3 giây).
Người 2 rời khỏi hàng.


Người 3 mua hộ vé cho người 4 chi phí là 10 giây (Vì nếu người 3 và người 4 mua
thì chi phí là 7+8=15 giây lớn hơn chi phí người 3 mua hộ là 10 giây).
Người 4 rời khỏi hàng.
Người 5 mua vé chi phí là 4 giây.
Tổng chi phí ít nhất mua cho cả 5 người là: 3+10+4 =17 giây.
-----HẾT----Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ vàtên thísinh:................................................Số báo danh: ...................................................
Chữ kýgiám thị 1: ...............................................Chữ kýgiám thị 2: ..........................................


SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN

ĐỀ CHÍNH THỨC
(Hướng dẫn gồm có01 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 VÒNG 1
Môn thi: TIN HỌC (bảng B)
Ngày thi: 09/10/2015
Thời gian: 180 phút (không kể phát đề)
HƯỚNG DẪN CHẤM

Câu 1: BAI1.PAS(7 điểm)
Gồm 4 test
STT NGAY.INP
NGAY.OUT
1
NGAY1.INP
1785
2
NGAY2.INP
974
3
NGAY3.INP
2390
4
NGAY4.INP
18627
Các tệp dữ liệu vào và ra test được ghi trong CD đính kèm
Câu 2: BAI2.PAS(7điểm)
Gồm 4 test:
STT
NT.INP

NT.OUT
1
NT1.INP
91879199
2
NT2.INP
59275939
3
NT3.INP
1519915217
4
NT4.INP
6903169061
Các tệp dữ liệu vào và ra được ghi trong CD đính kèm.
Câu 3: BAI3.PAS(6 điểm)
Gồm 4 test:
STT
VE.INP
VE.OUT
1
VE1.INP
86
2
VE2.INP
2449932
3
VE3.INP
3551603
4
VE4.INP

5084206

ĐIỂM
1
2
2
2

ĐIỂM
1
2
2
2

ĐIỂM
1.5
1.5
1.5
1.5

Các tệp dữ liệu vào và ra được ghi trong CD đính kèm.
* Nếu đồng điểm thìchọn thísinh cóthuật toán tốt hơn
SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN
ĐỀ CHÍNH THỨC
(Đề thi gồm 3 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12
VÒNG 2 NĂM 2015
Môn thi: TIN HỌC

Ngày thi: 05 / 11 / 2015 (Buổi thi thứ nhất)
Thời gian: 180 phút (không kể thời gian phát đề)

Học sinh tạo thư mục làsố báo danh của mình trong đĩa D, lưu các bài làm với tên tương
ứng KHOBAU.PAS, WINDOWS.PAS, PAGES.PAS vào thư mục vừa tạo.
Bài 1: Tìm kho báu – KHOBAU.PAS (6 điểm)
Một nhóm nhà thám hiểm đi tìm kho báu. Kho báu được cất giấu ở phòng bên phải nhất
của tầng dưới cùng trong một hầm (có M tầng được đánh số từ 1 đến M theo thứ tự từ trên xuống,
mỗi tầng có N phòng). Các phòng được ngăn cách bằng các cửa rất khó phá. Mỗi phòng có cửa
xuống phòng ngay phía dưới và có cửa sang phòng kế bên. Từ trên mặt đất có N cửa xuống phòng


tầng 1. Mỗi cửa được làm bằng một kim loại khác nhau với độ dày khác nhau nên việc phá cửa
cần một khoảng thời gian khác nhau.
Yêu cầu: Bạn hãy chỉ đường cho nhóm nhà thám hiểm để đi từ mặt đất xuống phòng chứa
kho báu một cách nhanh nhất để lấy được kho báu.
Dữ liệu vào: Cho trong tệp KHOBAU.INP
 Dòng 1 ghi M vàN (1 ≤ M ≤ 2222, 1 ≤ N ≤ 10);
 Từ dòng 2 đến dòng 2M + 1: dòng chẵn ghi N số là khoảng thời gian phá các cửa từ
trên xuống, dòng lẻ ghi N - 1 số làkhoảng thời gian để phácác cửa ngăn giữa các phòng
cùng tầng.
Lưu ý: Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp KHOBAU.OUT một con số duy nhất làkhoảng thời gian nhỏ nhất để
nhóm nhà thám hiểm đến phòng chứa kho báu.
Vídụ:
KHOBAU.INP
KHOBAU.OUT
42
44

99 10
1
10 99
1
99 10
1
10 99
1
Giải thích:

: Hướng đi của nhóm nhà thám hiểm
: Kho báu
Khoảng thời gian nhỏ nhất:
10 + 1 + 10 + 1 + 10 + 1 + 10 + 1 = 44

Sơ đồ đường đi
Bài 2: Các cửa sổ chương trình – WINDOWS.PAS (7 điểm)
Màn hì
nh máy tính làmột lưới 10000 x 10000 ô vuông đơn vị. Các dòng của lưới này được
đánh số từ 1, 2, … từ trên xuống dưới, các cột được đánh số 1, 2, … từ trái sang phải. Khi làm
việc trong môi trường Windows, ta mở nhiều chương trình. Mỗi chương trình là một cửa sổ hì
nh
chữ nhật (gồm một số ôtrong lưới) cócác cạnh song song với các cạnh màn hì
nh. Như vậy mỗi
cửa sổ được xác định bởi tọa độ của ôở góc trái trên vàôở góc phải dưới. Nếu bấm chuột vào ô
ở góc phải trên của cửa sổ thìcửa sổ đó sẽ đóng lại.
Ô ở góc
trái trên
(U, V)

Bấm chuột vào ô
này sẽ đóng cửa sổ
(nếu ônày không
bị che)


Ô ở góc phải dưới
(X, Y)

Trong quátrình mở các cửa sổ, các cửa sổ sau cóthể che một phần cửa sổ trước vàmột cửa sổ
chỉ cóthể đóng lại nếu ôở góc phải trên của nókhông bị che.
Yêu cầu: Cho dãy N cửa sổ với tên 1, 2, …, N được mở theo thứ tự đó, cần phải dùng í
t nhất
bao nhiêu lần đóng cửa sổ để cóthể đóng được cửa sổ 1.
Dữ liệu vào: từ tệp văn bản WINDOWS.INP gồm:
 Dòng thứ nhất chứa số N (N ≤ 100) ;
 Dòng thứ i trong N dòng tiếp theo ghi 4 số U, V, X, Y với ý nghĩa là tọa độ của ôở góc
trái trên của cửa sổ thứ i là(U, V), tọa độ của ô ở góc phải dưới cửa sổ thứ i là(X, Y).
(0Kết quả: Ghi ra tệp văn bản WINDOWS.OUT gồm 2 dòng:
 Dòng thứ nhất cho biết S làsố lần đóng cửa sổ;
 Dòng thứ hai ghi chỉ số của những cửa sổ cần đóng (theo thứ tự thực hiện đóng).
Lưu ý: Các số trên cùng một dòng được ghi cách nhau í
t nhất một dấu cách.
Ví dụ:

WINDOWS.INP

WINDOWS.OUT

3
1
1 4 7 6
1
3 2 5 7
3 9 5 11
Giải thí
ch: Cửa sổ 1 cóôở góc phải trên không bị che. Nên chỉ cần đóng cửa sổ 1.
1

2

3

4

5

6

7

8

9

10 11 12

1

2

2
3

1

4
5
6
7
8

3

9
10
11
12

Bài 3: Canh lề văn bản – PAGES.PAS (7 điểm)
Trong một tệp (file) văn bản cóN từ. Mỗi từ làmột dãy các kítự chữ cái tiếng Anh (chữ
hoa và thường) vàcác dấu câu (như , . : ; ? ! ( ) ‘ “
) liền nhau. Người ta cần căn lề
trái cho file với độ rộng M kítự trên mỗi dòng. Mỗi từ cần được xếp trọn trên một dòng, mỗi dòng
cóthể chứa nhiều từ vàtrật tự các từ được giữ nguyên.
Yêu cầu: Giả thiết rằng mỗi từ đều có1 dấu cách ở cuối, dấu cách này được tí
nh vào
chiều dài từ. Hãy tìm một phương án căn lề sao cho phần thừa lớn nhất ở bên phải tất cả các dòng
làcon số nhỏ nhất.

Chiều dài của các từ
được bố trítrên dòng

Phần thừa của dòng
W e

c a n


Chiều dài (M) của dòng

Dữ liệu vào: từ tệp văn bản PAGES.INP gồm:
 Dòng đầu tiên chứa hai số N và M;
 N dòng tiếp theo, mỗi dòng chứa một từ (không có dấu cách phía sau).
Kết quả: Ghi ra tệp văn bản PAGES.OUT gồm:
 Dòng đầu tiên chứa hai số H và K, trong đó H là phần thừa lớn nhất (tính theo số kí
tự) của phương án tìm được; K là số dòng của văn bản đã được căn lề;
 Tiếp đến là K dòng, mỗi dòng thể hiện các từ được xếp vào dòng đó (trật tự các từ
được giữ nguyên).
Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một dấu cách.
PAGES.INP
6 16
We
can
program
the
FIFA
games.

PAGES.OUT

1 2
We can program
the FIFA games.

Giải thích:
Từ
We
có chiều dài 3 kí tự (tính luôn dấu cách).
Từ
can
có chiều dài 4 kí tự (tính luôn dấu cách)
Từ
program
có chiều dài 8 kí tự (tính luôn dấu cách)
Từ
the
có chiều dài 4 kí tự (tính luôn dấu cách)
Từ
FIFA
có chiều dài 5 kí tự (tính luôn dấu cách)
Từ
games.
có chiều dài 7 kí tự (tính luôn dấu cách)
Cần xếp 6 từ này trên các dòng cótối đa 16 kí tự.
 Nếu xếp thành 3 dòng là
W e
c a n
p r o g r a m
t h e
F I F A

g a m e s .
thìphần thừa tối đa là 9 (trên dòng 1)
 Nếu xếp thành 2 dòng là
W e
c a n
p r o g r a m
t h e
F I F A
g a m e s .
thìphần thừa tối đa là 1 (trên dòng 1).
Như vậy, ta chọn cách xếp thứ 2.
----- HẾT ----Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gìthêm.
Họ tên thísinh: ...................................................... SBD: .......................................................................
Giám thị 1:............................................................. Giám thị 2: .............................................................

SỞ GIÁO DỤC VÀ ĐÀO TẠO
LONG AN
ĐỀ CHÍNH THỨC
(Đề thi gồm 3 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
LỚP 12 VÒNG 2 NĂM 2015
Môn thi: TIN HỌC
Ngày thi: 06 / 11 / 2015 (Buổi thi thứ hai)
Thời gian: 180 phút (không kể thời gian phát đề)


Học sinh tạo thư mục làsố báo danh của mình trong đĩa D, lưu các bài làm với tên tương
ứng RUTGON.PAS, ROBO.PAS, KHOANLO.PAS vào thư mục vừa tạo.
Bài 1: Rút gọn – RUTGON.PAS (6 điểm)

Cho hình vuông H kích thước 2x2 được ghép từ 4 hình vuông đơn vị. Mỗi hình vuông đơn
vị tô một màu khác nhau. Có hai phép biến đổi:
Phép S – Đổi chỗ 2 hình vuông đơn vị bên trên 1 lần.
Phép R – Đổi chỗ vòng tròn các hình vuông đơn vị theo chiều kim đồng hồ 1 lần.

Trạng thái ban đầu





Phép S

Phép R

Yêu cầu: Cho dãy phép biến đổi, hãy tìm dãy biến đổi ngắn nhất cho cùng kết quả. Nếu có
nhiều dãy kết quả (có cùng độ dài ngắn nhất) thì đưa ra dãy có thứ tự từ điển nhỏ nhất. Ví dụ: giả
sử RSR và SRS là dãy phép biến đổi ngắn nhất có cùng độ dài là 3, thì kết quả được chọn là RSR
vì R đứng trước S trong bảng chữ cái.
Dữ liệu vào: Từ tệp văn bản RUTGON.INP chứa một xâu cóđộ dài không quá 255 kí tự gồm
hai loại kí tự R, S.
Kết quả: Ghi ra tệp văn bản RUTGON.OUT xâu ngắn nhất và có thứ tự từ điển nhỏ nhất cho
cùng kết quả biến đổi.
Ví dụ:
RUTGON.INP
RUTGON.OUT
RRSRRRSRSRSRRSRRS
S
Bài 2: Robocon – ROBO.PAS (7 điểm)
Cuộc thi vòng loại Robocon năm nay có chủ đề “Gặp gỡ”. Các đội sẽ tranh tài trên một

lưới ô vuông gồm N hàng, N cột. Các hàng của lưới được đánh số từ 1 đến N, từ trên xuống dưới.
Các cột của lưới được đánh số từ 1 đến N, từ trái sang phải. Trên K ô vuông của lưới có đặt
chướng ngại vật (𝐾 < 𝑁 2 ). Ở phần thi Robot tự động, mỗi đội sẽ phải sử dụng đồng thời hai con
Robot.
Tại thời điểm xuất phát, Robot thứ nhất được đặt tại ô (1,1) và Robot thứ hai được đặt tại
ô(1,N). Robot thứ nhất mỗi bước chỉ được phép di chuyển sang ô kề cạnh bên phải, hoặc xuống
ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía dưới bên phải. Robot thứ hai mỗi bước chỉ được
phép di chuyển sang ô kề cạnh bên trái hoặc xuống ô kề cạnh bên dưới hoặc xuống ô kề đỉnh phía
dưới bên trái.
Bắt đầu từ thời điểm xuất phát được tính là 0, hai Robot phải di chuyển liên tục theo qui
tắc đã nêu. Thời gian di chuyển từ một ô sang ô kế tiếp được tính là 1 giây. Nhiệm vụ của đội
chơi là phải lập trình điều khiển hai Robot xuất phát cùng lúc, di chuyển tránh chướng ngại vật
để gặp nhau tại một ô vuông không có chướng ngại vật. Hai Robot gặp nhau càng sớm đội chơi
càng được nhiều điểm. Lưới ô vuông được thiết kế đảm bảo là luôn có cách đi để hai Robot gặp
được nhau.
Yêu cầu: Hãy tìm cách điều khiển sao cho hai Robot gặp nhau ở thời điểm sớm nhất.
Dữ liệu vào: Cho trong tệp ROBO.INP
 Dòng thứ nhất chứa hai số nguyên dương N, K (N ≤ 500, K ≤ 10000; K< 𝑁 2 );


Dòng thứ i trong số K dòng tiếp theo chứa 2 số nguyên dương Ui, Vi tương ứng là tọa độ
hàng và cột của ô có đặt chướng ngại vật (i = 1, 2, …, K).
Lưu ý: Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra tệp ROBO.OUT một con số nguyên dương duy nhất là thời điểm sớm nhất
hai robot gặp nhau.
Ví dụ:
ROBO.INP
ROBO.OUT
55
3

22
14
23
35
42
Giải thích:


Robot
1

Robot
2

: Chướng ngại vật
: Hướng đi robot

Hướng đi của robot1: (1,1)(2,1)(3,2)(3,3): chi phí 3 giây.
Hướng đi của robot2: (1,5)(2,5)(3,4)(3,3): chi phí 3 giây.
Thời điểm sớm nhất hai robot gặp nhau: 3 giây.
Bài 3: Kính khoan lỗ – KHOANLO.PAS (7 điểm)
Có N tấm kính hình vuông kích thước K x K (gồm K hình vuông đơn vị theo hàng ngang và K
hình vuông đơn vị theo hàng dọc). Tại tâm của mỗi hình vuông đơn vị trên mỗi tấm kính, người
ta vẽ các hình tròn có bán kính bằng nhau (với đường nét rất mỏng), sao cho nếu tất cả các hình
tròn được khoan thủng thì các vị trí khoan (tạm gọi là cột) là trùng nhau khi xếp các tấm kính
thành một chồng, cho dù có một tấm nào đó đã xoay 900 , 1800 , 2700 theo chiều kim đồng hồ.
Trên mỗi tấm kính, có một số hình tròn được khoan thủng. Chúng được xếp thành một chồng.
Yêu cầu: Hãy chỉ ra một số ít nhất các tấm kính cần được xoay, sao cho trên mỗi cột đều
có ít nhất một hình tròn được khoan thủng, hoặc cho biết điều này không thể thực hiện được.
Dữ liệu vào: Từ tệp văn bản KHOANLO.INP gồm:

 Dòng thứ nhất: chứa 2 số nguyên N, K (1 ≤ 𝑁 ≤ 20; 2 ≤ 𝐾 ≤ 10);
 Dòng thứ i trong N dòng tiếp theo chứa K × K số 0, 1 cho biết trạng thái các hình tròn trên
tấm kính thứ i, liệt kê theo hàng ngang, từ trái sang phải và từ trên xuống dưới. Trong đó,
số 1 (0) chỉ ra vị trí tương ứng là vòng tròn được khoan thủng (không khoan).
Kết quả: Ghi ra tệp văn bản KHOANLO.OUT gồm
 Dòng thứ nhất: chứa số nguyên M là số tấm kính cần xoay, M = -1 làkhông cócách xoay.




Trong trường hợp M ≥ 0 thì dòng thứ i trong M dòng tiếp theo chứa chỉ số của tấm kính
cần xoay và 1 (hoặc 2, hoặc 3) cho biết tấm kính tương ứng cần xoay 900 (hoặc 1800 , hoặc
2700 ) theo chiều kim đồng hồ.
Lưu ý: Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Ví dụ:
KHOANLO.INP
5
0
1
1
0
1

3
1
0
0
1
0

0
0
0
0
0

1
0
0
0
1

0
1
1
0
0

0
0
0
0
0

0
0
0
1
0

0
0
0
0
0

0
0
1
0
0

KHOANLO.OUT
2
1 2
2 1

Giải thích:
Vòng tròn không khoan
thủng.
Vòng
tròn
được
khoan
thủng.

Chồng lên nhau

Qua

y
𝟏𝟖𝟎𝟎

Qua
y
𝟗𝟎𝟎

Giữ
Giữ
Giữ
nguyê nguyê nguyê
Kết quả

----- HẾT ----Thí sinh không được sử dụng tài liệu. Giám thị không giải thí
ch gìthêm.
Họ tên thísinh: ................................................ SBD: .................................................................
Giám thị 1: ....................................................... Giám thị 2: .......................................................
Sở Giáo dục và Đào
tạo
LONG AN
ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH
LỚP 12 VÒNG 2 NĂM 2015
Môn thi: TIN HỌC
Ngày thi: 05 / 11 / 2015 (Buổi thi thứ nhất)

HƯỚNG DẪN CHẤM
Câu 1: Tìm kho báu - KHOBAU.PAS (6 điểm) Đúng mỗi test được 1 điểm.
INPUT

OUTPUT
ST
T
File
Dữ liệu
File
Dữ liệu
1 KHOBAU1.INP
Trong file KHOBAU1.OUT
219
2 KHOBAU2.INP
Trong file KHOBAU2.OUT
3117

Điểm
1
1


3
4
5
6

KHOBAU3.INP
KHOBAU4.INP
KHOBAU5.INP
KHOBAU6.INP

Trong file

Trong file
Trong file
Trong file

KHOBAU3.OUT
KHOBAU4.OUT
KHOBAU5.OUT
KHOBAU6.OUT

9127
639434
459048
835234

1
1
1
1

Câu 2: Các cửa sổ chương trình – WINDOWS.PAS (7 điểm) Đúng mỗi test được 1 điểm.
INPUT
OUTPUT
ST
Điểm
T
File
File
Dữ liệu
1 WINDOWS1.INP WINDOWS1.OU 3
1

T
4 2 1
2 WINDOWS2.INP WINDOWS2.OU 3
1
T
5 4 1
3 WINDOWS3.INP WINDOWS3.OU 2
1
T
4 1
4 WINDOWS4.INP WINDOWS4.OU 6
1
T
26 25 23 13 6 1
5 WINDOWS5.INP WINDOWS5.OU 3
1
T
49 8 1
6 WINDOWS6.INP WINDOWS6.OU 11
1
T
70 68 67 65 63 52 47 45 19 18 1
7 WINDOWS7.INP WINDOWS7.OU 2
1
T
70 1