Mô tả và yêu cầu

ỤC VÀ ĐÀO TẠO KỲ THI OLYMPIC TRUYEN THONG 30 THANG 4 -
Ó HO CHÍ MINH LAN THU XXIX - NAM 2025
yộ 0. rene Môn: TIN HỌC - Khối: 11 ;
= 5 Thời gian: 180 phút (không kể thời gian giao dé)
Ty Ngày thi: 05/4/2025
DE THI CHINH THUC Dé thi gom 04 trang, 03 bai

Luu ý: - Thí sinh không được sử dung tài liệu;
- Giám thị không giải thích gì thêm.
Tổng quan về đề thi

Bài | Tên bài File chương trình File dữ liệu File kết quả

1 Đường đi trên ma trận MATRIX3.* MATRIX3.INP MATRIX3.OUT
2 Giải mã xâu KSTRING.* KSTRING.INP KSTRING.OUT
3 Thué phong hop XGRAPH.* XGRAPH.INP XGRAPH.OUT

Dau * thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hay C++

Bài 1. Đường đi trên ma trận (6 điển)

An đang chơi ¡ một trò chơi, màn hình trò chơi là hình chữ nhật được chia làm nxm 6 vuông đơn vị (n dòng
và m cột). Mỗi 6 vuông được đặt một phần thường, phần thưởng ở ô vuông nằm trên dong thứ 7 từ trên
xuống và cột thứ j J từ trai sang có giá trị là aij. Một nhân vật đang đứng ở 6 trái trên (vị tri dòng 1, cột 1),
can phai di chuyén tới 6 phải dưới của màn hình (vị trí dòng n, cột m). Mỗi bước, An có thé điều khiển
nhân vật đi xuống dưới một đơn vị hoặc sang phải một đơn vị, nhưng không được phép đi xuống ba lần
liên tiếp. Lưu ý, việc đi sang phải nhiều lần liên tiếp là không bị giới hạn.

Yêu cầu: Hãy giúp An tìm cách điều khiển nhân vật sao cho. tổng giá trị phần thưởng ở những ô mà nhân
vật đi qua (bao gồm cả ô xuất phát và ô kết thúc) là lớn nhất có thể. Đưa ra tông giá trị đó.

Dữ liệu: Vào từ file văn bản MATRIX3.INP:

+ Dòng đầu tiên chứa hai số nguyên dương n và m.

+ n dòng tiếp theo, mỗi dòng chứa m số nguyên dương. Trên dòng thứ i, số thứ / là z¡ ie
Dữ liệu bảo đảm luôn tồn tại một cách di chuyền hợp lệ từ ô trái trên tới ô phải dưới.
Kết quả: Ghi ra file văn bản MATRIX3.OUT:

Ghi một số nguyên dương duy nhất là tổng giá trị phần thưởng lớn nhất tìm được.

Ví dụ

MATRIX3.INP MATRIX3.OUT GIẢI THÍCH
43 16 An có thể điều khiển nhân
111 vật: Đi xuống, đi xuống,
Sul sang phải, đi xuống, sang
812 phải.
334

Kỳ thi Olympic truyền thống 30/4 lần thứ XXIX năm 2025 1

Ràng buộc:
« Trong tất cả các test: 1< n,m <2025; 1< ai, „ <10°.
« Có 25% số test với n,m <10;
« Có 30% số test với ø <3;

« Có 45% số test với ràng buộc gốc.
Bài 2. Giải mã xâu (7 điển)

Bình rất đam mê khảo cổ học. Anh vừa phát hiện một từ điển cổ, sau khi nghiên cứu Bình đã tìm ra một
vài quy tắc của nó như sau:

« Từ điển chỉ sử dụng & loại ký tự, có thể được Bình biểu diễn bang k chữ cái đầu tiên trong bảng chữ
cái Latin in thường.

+ Mỗi từ trong từ điển đều có độ dai bằng đúng # và chứa các chữ cái khác nhau. Nói cách khác, mỗi
từ đều là một hoán vị của k chữ cái.

« Mỗi chữ cái chỉ có thể đứng ở một số vị trí nhất định trên từ. Bình biểu diễn quy tắc này bằng một
ma trận c kích thước kxk, Giá trị của cij bằng 1 hoặc 0 tương ứng là ký tự thứ ¿ trong bảng chữ cái
được phép xuat hiện ở vị trí 7 trên từ hoặc không.

Từ nào thoả mãn cả ba quy tắc trên thì đều có trong từ điền.

Bình sẽ sử dụng từ điển này để giải mã một thông điệp mà anh vừa tìm được. Thông điệp đã lâu đời nên
có thể có một số vị trí bị mờ. Bình biểu diễn thông điệp bang một xâu s chỉ chứa các ký tự Latin in
thường và dấu * (dấu * đại diện cho các vị trí bị mờ). Dé giải mã thông điệp, anh đã thử thay mỗi dấu *
bằng một ký tự (các dấu * không nhất thiết được thay bằng các ký tự giống nhau), sau đó xoá đi một số
ký tự trên s và giữ nguyên thứ tự các ký tự còn lại (có thê không xoá ký tự nào). Nếu xâu thu được là một
từ trong từ điển thì Bình đã thu được một kết quả giải mã.

Yêu cầu: Hãy tính xem Bình có thể thu được bao nhiêu kết quả giải mã khác nhau. Tức là đếm xem trong
từ điên có bao nhiêu từ là xâu con (không cần liên tiệp) của s, với dau * đại diện cho ký tự tuỳ ý.

Dữ liệu: Vào từ file văn bản KSTRING.INP:

+ Dòng đầu tiên chứa số nguyên đương k.
5 k dong tiép theo, mỗi dòng chứa k số nguyên. Ở trên dòng thứ i, số thứ '7 là cụ,
« Dòng tiếp theo chứa xâu s.

Kết quả: Ghi ra file văn bản KSTRING.OUT:

Ghi một số nguyên duy nhất là số kết quả giải mã khác nhau mà Bình có thể thu được.

Ví dụ:

KSTRING.INP KSTRING.OUT GIẢI THÍCH

3 Chữ cái b không thể xuất hiện ở vị trí 1 trên từ
(trong ma trận, cz: = 0).

Tir dién có 4 từ: abc, acb, cab, cba. Trong đó có
ad*a* 3 từ có thé là kết quả giải mã: abc, acb, cab.

4 4 Chữ cái a không thể xuất hiện ở vị trí 3 trên từ.

1101 (cis = 0)

ee Chữ cái c không thé xuất hiện ở vị tri 1, 2 trên

O Diet từ. (cai = 0, ca = 0)

1110 . 2 man:

cdefab*f* Chữ cái d không thê xuât hiện ở vị trí 4 trên từ.
(cas = 0)
Từ điển có 8 từ: abdc, adbc, adcb, badc, bdca,
dabe, dacb, đbca. Trong đó, có 4 từ có thé là kết
quả giải mã: abdc, dabc, dacb, dbca.

Ràng buộc:

+ Trong tất cả các test: 1< &<15; Độ dài xâu s không quá 100.
+ Có 30% số test với k <0.

+ Có 30% số test với xâu s chỉ gồm các ký tự dấu sao *.

« Có 40% số test với ràng buộc sốc.

Bài 3. Thuê phòng họp (7 điển)

Thành phố nơi Cường làm việc có n địa điểm, được đánh số từ 1 đến n. Một số địa điểm trong thành phố
có hội trường cho thuê. Hội trường ở địa điểm thứ i có diện tích là s¡ và giá thuê là c; (quy ước rằng nếu ở
địa điểm ¡ không có hội trường thì s;= e;= 0). Có m con đường hai chiều, mỗi con đường nối giữa hai địa
điểm và có độ dài cho trước. Hệ thống đường bảo đảm việc đi lại giữa mọi địa điểm.

Công ty của Cường ở địa điểm 1. Theo kế hoạch, có Q cuộc họp cần được tổ chức trong các ngày tới. Do
thời gian tổ chức và quy mô khác nhau nên mỗi cuộc họp đều có yêu cầu riêng về việc tổ chức. Yêu cầu

t6 chức của cuộc họp thứ j được mô tả bởi ba số nguyên (1/#7,r;) với ý nghĩa: Cần thuê một phòng có

diện tích thuộc phạm vi [L;,Hj] và có khoảng cách tới công ty không quá z;.

Yêu cầu: Với mỗi cuộc họp, hãy giúp Cường tìm hội trường có giá thuê rẻ nhất mà vẫn thoả mãn yêu cầu
tô chức. Biết rang các cuộc hop này có thời gian tô chức khác nhau nên có thể nhiều cuộc họp cùng thuê
một hội trường.

Dữ liệu: Vào từ file văn bản XGRAPH.INP:

+ Dòng đầu tiên chứa ba số nguyên n, m, Q.
+ Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên sj, ci.
* Mỗi dòng trong số m dòng tiếp theo chứa ba số nguyên u,v,w cho biết có một con đường độ dài w
nôi giữa hai địa điểm u và v.
* hy: thứ j trong số Q dòng tiếp theo chứa ba số nguyên 7„, Hj, z; mô tả yêu cầu tổ chức của cuộc
ọp thứ 7.

Kết quả: Ghi ra file văn bản XGRAPH.OUT:

Ghi Q dòng. Dòng thứ j là giá thuê hội trường rẻ nhất cho cuộc hop thứ j, nếu không có hội trường nào
thoả mãn yêu câu tô chức cuộc họp thứ j thì ghi -1.

Kỳ thi Olympic truyền thống 30/4 lần thứ XXIX năm 2025 3

£

S “Á

2

2

tad

Ví dụ:

XGRAPH.INP XGRAPH.OUT GIẢI THÍCH

Các hội trường có thể thuê cho 5 cuộc họp
lần lượt năm ở các địa điểm: 2, 5, 6, 1,
không tồn tại.

^>
`
CH No

Rang buộc:
+ Trong tất cả các test:
- l<n,m,O<10';
- 0<s/c¡<10);
- 1<1/<H,<10,
- l<n<101,
- 1<w<10;
* Có 16% số test với n <100;
« Có 24% số test với O <100;
« Có 28% số test với z;= 10! với mọi j = 1,2,...,0;

« Có 32% số test với ràng buộc gốc.

Kỳ thi löiym sie truyền thiêng 30/4 lần thứ XXIX năm 2025 4