Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm

 Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
 ĐỀ SỐ 3
 BỘ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA 
 THPT - NĂM HỌC 2023-2024
 ĐỀ CHÍNH THỨC Môn: TIN HỌC
 Thời gian: 180 phút (Không kể thời gian giao đề)
 TỔNG QUAN ĐỀ THI
 Tiêu đề File chương trình File dữ liệu File kết quả
Câu 1 Ba đường truyền điện THREE.* THREE.INP THREE.OUT
Câu 2 Cải thiện đánh giá IMPEVAL.* IMPEVAL.INP IMPEVAL.OUT
Câu 3 Thu mua nông sản FBUY.* FBUY.INP FBUY.OUT
Dấu * được thay thế bởi PAS hoặc CPP tương ứng với ngôn ngữ lập trình Pascal hoặc 
C++.
Hãy lập trình giải các câu sau:
Câu 1. Ba đường truyền điện (7,0 điểm)
Quốc gia Alpha có một trang trại điện gió được quy hoạch bởi một bảng vuông N hàng và N 
cột. Các hằng được đánh số từ 1 tới N từ trên xuống dưới, các cột được đánh số từ 1 tới N từ 
trái sang phải. Trang trại có M trạm sản xuất điện gió được đánh số từ 1 tới M. Trạm thứ 
i(1 ≤ i ≤ M) được đặt tại ô thuộc hàng Ri, cột Ci và có công suất sản xuất là Wi oát. Chủ trang 
trại mới ký hợp đồng cung cấp điện cho đối tác. Trang trại sẽ phải lắp ba đường truyền điện, 
mỗi đường truyền đi qua một hàng hoặc một cột trong bảng. Các đường truyền có thể cắt 
nhau nhưng không được trùng nhau. Tổng công suất cung cấp cho đối tác là tổng công suất 
của các trạm điện nằm trên ít nhất một trong ba đường truyền. Trang trại cần tìm ra cách lắp 
đặt ba đường truyền để tổng công suất cung cấp là lớn nhất có thể.
Ngoài ra, công ty có Q phương án điều chỉnh. Phương án điều chỉnh thứ j(1 ≤ j ≤ Q) là tăng 
công suất của trạm Tj thêm một lượng Dj oát và giữ nguyên công suất Wi oát như hiện trạng 
ban đầu của mọi trạm i khác Tj. Lưu ý, các phương án là độc lập, nghĩa là các phương án đều 
chỉ áp dụng lên hiện trạng ban đầu của trang trại.
Yêu cầu: Hãy đưa ra tổng công suất lớn nhất có thể khi lắp ba đường truyền với hiện trạng 
ban đầu của trang trại và trong Q phương án điều chỉnh.
Dữ liệu
Vào từ file văn bản THREE. INP:
- Dòng đầu ghi một số nguyên dương T là số lượng trường hợp test.
- Mỗi nhóm dòng trong số T nhóm dòng tiếp theo mô tả một trường hợp test có cấu trúc như 
sau:
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
- Dòng thứ nhất chứa ba số nguyên N, M và Q lần lượt là kích thước bảng, số lượng trạm 
điện và số lượng phương án điều chỉnh (3 ≤ N ≤ 109; 3 ≤ M ≤ 105; 1 ≤ Q ≤ 105).
- Dòng thứ i trong số M dòng tiếp theo chứa ba số nguyên Ri, Ci và Wi lần lượt là vị trí hàng, 
vị trí cột và công suất của trạm điện thứ i. Dữ liệu bảo đảm không có hai trạm nào đặt tại 
 9
cùng một ô (1 ≤ Ri, Ci ≤ N; 1 ≤ Wi ≤ 10 ).
- Dòng thứ j trong số Q dòng tiếp theo chứa hai số nguyên Tj và Dj thể hiện phương án điều 
 18
chỉnh tăng công suất thêm Dj oát cho trạm điện thứ Tj(1 ≤ Tj ≤ M ; 1 ≤ Dj ≤ 10 ).
- Gọi ∑M và ∑Q tương ứng là tổng của tát cả các giá trị M và Q trong tất cả T trường hợp 
 5
test. Dữ liệu bảo đảm 1 ≤ ∑M , ∑Q ≤ 2 x 10 .
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bản THREE.OUT:
- Gồm T nhóm dòng, mỗi nhóm dòng là kết quả của trường hợp test tương ứng có cấu trúc 
sau:
- Dòng thứ nhất ghi ra một số nguyên dương là tổng công suất lớn nhất tìm được với hiện 
trạng trang trại ban đầu.
- Dòng thứ j trong số Q dòng tiếp theo ghi ra tổng công suất lớn nhất tìm được với phương 
án điều chỉnh thứ j.
Ví dụ
 THREE. INP THREE.OUT Giải thích
2 17 Xét trường hợp test thứ nhất:
5 7 2 19 - Với hiện trạng ban đầu, một cách tối ưu là lắp ba 
1 1 1 24 đường truyền ở cột 1, cột 2 và cột 5. Tổng công suất 
3 1 2 6 cung cấp là 17.
2 2 3 7 - Với phương án điều chỉnh thứ nhất, một cách tối ưu 
4 2 4 là lắp ba đường truyền đo hàng 2, cột 2 và cột 5. Tổng 
2 4 2 công suất cung cấp là 19.
1 5 5 - Với phương án điều chỉnh thứ hai, một cách tối ưu là 
3 5 2 lắp ba đường truyền ở hàng 1, hàng 3 và cột 2. Tổng 
5 3 công suất cung cấp là 24.
 Cột
2 7 Hàng 1 2 3 4 5
3 3 1 1 1 5
1 1 1 2 3 2 → 5
1 2 2 3 2 2
1 3 3 4 4
3 1 5
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
 Cột
 Hàng 1 2 3 4 5
 1 1 5
 2 3 2
 3 2 → 9 2
 4 4
 5
Ràng buộc:
(1) Có 20% số test ứng với 20% số điểm thỏa mãn: N, M, Q ≤ 40 và T = 1.
(2) 20% số test khác ứng với 20% số điểm thỏa mãn: N, M, Q ≤ 100 và T = 1.
(3) 20% số test khác ứng với 20% số điểm thỏa mãn: N, M, Q ≤ 500 và T = 1.
(4) 20% số test khác ứng với 20% số điểm thỏa mãn: M, Q ≤ 1000 và ∑M, ∑Q ≤ 2000.
(5) 10% số test khác ứng với 10% số điểm thỏa mãn: M ≤ 1000 và ∑M ≤ 2000.
(6) 10% số test còn lại ứng với 10% số điểm: Không có ràng buộc gì thêm.
Câu 2: Cải thiện đánh giá (7,0 điểm)
Quốc gia Beta có N thành phố được đánh số từ 1 đến N. Các thành phố được nối với nhau 
bởi M con đường hai chiều, được đánh số từ 1 đến M, giữa hai thành phố bất kỳ có tối đa 
một con đường nối trực tiếp chúng. Con đường hai chiều số i(1 ≤ i ≤ M) nối trực tiếp giữa 
hai thành phố phân biệt Ui và Vi có độ dài Wi. Một đường đi gồm K thành phố từ thành phố 
X tới thành phố Y là một chuỗi các thành phố P1, P2, . , PK, sao cho P1 = X, PK = Y và có 
con đường trực tiếp giữa hai thành phố Pi và Pi+1(∀i = 1,2, , K – 1).
Ở quốc gia Beta, mọi thành phố đều có đường đi tới thành phố khác. Chi phí di chuyển của 
một đường đi từ thành phố X tới thành phố Y là tổng độ dài của các con đường trên đường đi 
đó. Gọi D(X, Y) là chi phí di chuyển nhỏ nhất trong số các chi phí di chuyển của các đường 
đi từ thành phố tới thành phố Y. Quy ước D(X, X) = 0 với mọi thành phố X.
Thành phố số 1 có một nhà máy đúc khuôn và thành phố số 2 có một nhà máy sản xuất mạ 
tĩnh điện. Một doanh nghiệp muốn chọn một thành phố nào đó để mở một trung tâm chế tạo 
thép trang trí sử dụng nguyên liệu từ nhà máy đúc khuôn và nhà máy sản xuất mạ tĩnh điện. 
Thành phố Y được gọi là tốt hơn hoặc tương đương so với thành phố X khi và chỉ khi
D(Y, 1) ≤ D(X,1) và D(Y, 2) ≤ D(X, 2). Lưu ý, thành phố X được xem là tốt hơn hoặc tương 
đương so với chính nó. Doanh nghiệp tính hạng của thành phố X là số lượng thành phố 푌 tốt 
hơn hoặc tương đương so với thành phố X. Cụ thể, công thức tính hạng là:
R(X) = |{Y ∈ {1,2,, N}: D(Y,1) ≤ D(X,1) và D(Y,2) ≤ D(X,2)}|
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
Ngoài ra, doanh nghiệp cũng cam kết với chính quyền địa phương rằng trước khi đặt trung 
tâm chế tạo thép ở thành phố X nào đó, họ sẽ cải tạo một con đường nối với thành phố X. 
Doanh nghiệp đã khảo sát và đưa ra 푃 phương án. Với phương án thứ j(1 ≤ j ≤ P), con đường 
Tj nối giữa thành phố UTj và VTj sẽ được chọn để cải tạo giúp cho độ dài mới W'Tj bé hơn độ 
dài ban đầu WTj. Với mỗi phương án, sau khi cải tạo đường, doanh nghiệp cần tính hạng của 
thành phố UTj và thành phố VTj. Các phương án là độc lập, nghĩa là các phương án đều chỉ áp 
dụng lên hiện trạng ban đầu của M con đường.
Yêu cầu: Với phương án thứ j(1 ≤ j ≤ P) hãy giúp doanh nghiệp tìm ra hạng của thành phố 
UTj và thành phố VTj sau khi cải tạo con đường Tj.
Dữ liệu
Vào từ file văn bản IMPEVAL.INP:
- Dòng đầu chứa ba số nguyên N, M và P lần lượt là số lượng thành phố, số lượng con đường 
và số lượng phương án (2 ≤ N ≤ 105 ; 1 ≤ M, P ≤ 105).
- Dòng thứ i trong số M dòng tiếp theo chứa ba số nguyên Ui, Vi và Wi lần lượt là hai thành 
phố được nối bởi con đường số i và độ dài của con đường này (1 ≤ Ui, Vi ≤ N ; 1 ≤ Wi ≤ 
109).
- Dòng thứ j trong số P dòng tiếp theo chứa hai số nguyên Tj và W'Tj lần lượt là chỉ số con 
đường được lên phương án cải tạo và độ dài sau khi cải tạo (1 ≤ Tj ≤ M; 1 ≤ W'Tj < WTj).
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bản IMPEVAL.OUT:
- Gồm P dòng, trong đó dòng thứ j ghi ra hai số nguyên R (UTj) và R (VTj) tương ứng là hạng 
của thành phố UTj và thành phố VTj nếu phương án thứ j được triển khai.
Ràng buộc
(1) Có 20% số test ứng với 20% số điểm thỏa mãn: M, P ≤ 1000.
(2) 20% số test khác ứng với 20% số điểm thỏa mãn: Mỗi thành phố có nhiều nhất 2 con 
đường nối với thành phố khác.
(3) 20% số test khác ứng với 20% số điểm thỏa mãn: Mọi con đường đều nối với thành phố 
số 1 hoặc thành phố số 2.
(4) 20% số test khác ứng với 20% số điểm thỏa mãn: M = N – 1.
(5) 20% số test còn lại ứng với 20% số điểm: Không có ràng buộc gì thêm.
Ví dụ
IMPEVAL.INP IMPEVAL.OUT Giải thích
5 6 2 1 2 - Với con đường số 5 có độ dài mới bằng 2, thành 
1 5 8 1 1 phố số 3 có hạng 1 do chỉ có duy nhất thành phố 
5 2 10 số 3 tốt hơn hoặc tương đương với thành phố số 3, 
1 3 6 thành phố số 4 có hạng 2 do có hai thành phố tốt 
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
3 2 12 hơn hoặc tương đương với nó là thành phố số 4 và 
3 4 3 thành phố số 5.
4 2 11 X 1 2 3 4 5
5 2 D (X, 1) 0 18 6 8 8
6 9 D (X, 2) 18 0 12 11 10
 - Với con đường số 6 có độ dài mới bằng 9, thành 
 phố số 4 và thành phố số 2 đều có hạng 1.
Câu 3: Thu mua nông sản (6,0 điểm)
Quốc gia Delta có nền nông nghiệp hàng đầu thế giới. Năm nay, nhờ ứng dụng công nghệ 
thông tin sâu rộng trong sản xuất nông nghiệp, nông dân quốc gia Delta đã được mùa lớn. Để 
chúc mừng thành công lớn của bà con cũng như đẩy mạnh việc xuất khẩu, chính phủ quyết 
định bố trí các xe thu mua nông sản từ khắp mọi nơi trên cả nước.
Trong quốc gia có N ngôi làng được đánh số từ 1 đến N. Mạng lưới giao thông tại đây gồm 
N - 1 con đường hai chiều, mỗi con đường nối trực tiếp hai ngôi làng nào đó. Các con đường 
này bảo đảm sự liên thông toàn quốc. Nói cách khác, từ một ngôi làng bất kỳ có thể đi tới tất 
cả các ngôi làng còn lại thông qua một hoặc nhiều con đường. Người dân tại quốc gia Delta 
có khả năng sản xuất được K loại nông sản khác nhau, được đánh số từ 1 đến K. Năm nay, 
người dân tại ngôi làng thứ i(1 ≤ i ≤ N) sản xuất loại nông sản thứ Ai.
 N x (N 1) 
Chính phủ quốc gia Delta sẽ bố trí xe tải đi thu mua nông sản. Cụ thể, với mỗi cặp 
 2
số nguyên (u, v) sao cho 1 ≤ u ≤ v ≤ N, có một xe tải xuất phát từ ngôi làng thứ u, đi qua một 
hoặc nhiều con đường rồi dừng lại ở ngôi làng thứ v. Biết rằng, xe tải luôn chọn đi theo 
tuyến đường qua ít con đường nhất có thể, và khi tới bất kỳ một ngôi làng nào (bao gồm cả 
hai ngôi làng thứ u và thứ v), xe tải sẽ thu mua 1 tấn nông sản được sản xuất tại ngôi làng đó. 
Nhờ mùa màng bội thu, tất cả các ngôi làng đều có đủ nông sản cho mọi xe đi qua thu mua.
Việc vận chuyển nông sản luôn phát sinh chi phí. Tùy theo đặc tính, chi phí vận chuyển từng 
loại nông sản có thể khác nhau. Theo tính toán của chính phủ, nếu trong toàn bộ hành trình, 
một xe tải thu mua được khối lượng nông sản các loại thứ 1,2,, K tương ứng là W1, W2,.., 
 2 2 2
WK tấn, chi phí vận chuyển của xe này là C1 x 푊1 + C2 x 푊2 +  + CK x 푊퐾, trong đó C1, 
C2 ,, CK tương ứng là hệ số chi phí vận chuyển của 퐾 loại nông sản thứ 1,2,, K. Chính 
 N x (N 1) 
phủ sẽ tài trợ toàn bộ chi phí vận chuyển, nên cần biết tổng chi phí của tất cả xe tải 
 2
này.
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
Ngoài ra, với niềm tin rằng nền nông nghiệp còn phát triển mạnh trong nhiều năm về sau, 
chính phủ muốn dự trù chi phí vận chuyển nông sản cho những năm tiếp theo. Theo kế 
hoạch canh tác trong Q năm tiếp theo, vào năm thứ j(1 ≤ j ≤ Q) ngôi làng thứ Tj sẽ chuyển 
qua sản xuất loại nông sản thứ Bj, trong khi N -1 ngôi làng còn lại sẽ tiếp tục canh tác loại 
nông sản như năm thứ j - 1 (năm nay được coi là năm thứ 0). Với mỗi năm, chính phủ muốn 
biết tổng chi phí vận chuyển nông sản nếu tiếp tục bố trí các xe tải thu mua như phương án ở 
trên.
Yêu cầu: Hãy viết chương trình tính tổng chi phí vận chuyển nông sản của chính phủ trong 
năm nay và trong Q năm tiếp theo, dựa trên kế hoạch thay đổi canh tác.
Dữ liệu
Vào từ file văn bản FBUY. INP:
- Dòng đầu chứa ba số nguyên N, K và Q lần lượt là số ngôi làng của quốc gia Delta, số loại 
nông sản được sản xuất tại đây và số năm trong kế hoạch canh tác
(1 ≤ K ≤ 20 ; 1 ≤ N, Q ≤ 2 x 105).
- Dòng thứ hai chứa N số nguyên 1, 2,, thể hiện loại nông sản chuyên được sản xuất 
tại các ngôi làng trong năm nay (1 ≤ 푖 ≤ 퐾,∀푖 = 1,2,, ).
- Dòng thứ ba chứa K số nguyên 1, 2,, 퐾 là hệ số chi phí vận chuyển của các loại nông 
 9
sản (1 ≤ 푖 ≤ 10 ,∀푖 = 1,2,,퐾).
- Mỗi dòng trong số N - 1 dòng tiếp theo chứa hai số nguyên x và y cho biết có một con 
đường hai chiều nối ngôi làng thứ x và ngôi làng thứ y.
- Dòng thứ j trong số Q dòng cuối cùng chứa hai số nguyên 푗 và 푗 với ý nghĩa: Vào năm 
thứ 푗 trong 푄 năm tiếp theo, ngôi làng thứ 푗 sẽ chuyển sang sản xuất loại nông sản thứ 푗 
1 ≤ 푗 ≤ ;1 ≤ 푗 ≤ 퐾 .
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bản FBUY.OUT:
- Dòng đầu chứa một số nguyên là phần dư của tổng chi phí vận chuyển nông sản trong năm 
nay trong phép chia cho 998244353.
- Dòng thứ j trong số Q dòng còn lại chứa một số nguyên là phần dư của tổng chi phí vận 
chuyển nông sản trong năm thứ j trong phép chia cho 998244353.
Ràng buộc
(1) Có 7,5% số test ứng với 7,5% số điểm thỏa mãn: ≤ 30 và 푄 ≤ 800.
(2) 12,5% số test khác ứng với 12,5% số điểm thỏa mãn: ≤ 100 và 푄 ≤ 800.
(3) 10% số test khác ứng với 10% số điểm thỏa mãn: ≤ 2000 và 푄 ≤ 800.
(4) 15% số test khác ứng với 15% số điểm thỏa mãn: ≤ 5000 và 푄 ≤ 8000.
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
(5) 17,5% số test khác ứng với 17,5% số điểm thỏa mãn: Luôn tồn tại một con đường nối 
 푖 푖
ngôi làng thứ 푖 và ngôi làng thứ ,∀푖 = 2,3,, là số nguyên lớn nhất không vượt quá 
 2 2
푖 .
2
(6) 22,5% số test khác ứng với 22,5% số điểm thỏa mãn: Luôn tồn tại một con đường nối 
ngôi làng thứ 푖 và ngôi làng thứ 푖 ―1,∀푖 = 2,3,, .
(7) 15% số test còn lại ứng với 15% số điểm: Không có ràng buộc gì thêm.
Ví dụ
 FBUY.INP FBUY.OUT Minh hoạ mạng lưới giao thông
5 3 2 120
1 1 1 2 3 137
2 3 5 139
1 2
2 3
2 4
1 5
2 3
3 2
Giải thích
Trong năm nay, các ngôi làng thứ 1,2,3,4,5 lần lượt sản xuất các loại nông sản thứ 1,1,1,2,3. 
 5 x (5 1)
Có tất cả = 10 xe tải với các lộ trình vận chuyển và chi phí như sau:
 2
 Lượng nông sản thu mua theo 
Các ngôi làng đi qua Chi phí vận chuyển
 tấn (loại 1 , loại 2 , loại 3)
1 → 2 (2,0,0) 2 × 22 + 3 × 02 + 5 × 02 = 8
1 → 2 → 3 (3,0,0) 2 × 32 + 3 × 02 + 5 × 02 = 18
1 → 2 → 4 (2,1,0) 2 × 22 + 3 × 12 + 5 × 02 = 11
1 → 5 (1,0,1) 2 × 12 + 3 × 02 + 5 × 12 = 7
2 → 3 (2,0,0) 2 × 22 + 3 × 02 + 5 × 02 = 8
2 → 4 (1,1,0) 2 × 12 + 3 × 12 + 5 × 02 = 5
2 → 1 → 5 (2,0,1) 2 × 22 + 3 × 02 + 5 × 12 = 13
3 → 2 → 4 (2,1,0) 2 × 22 + 3 × 12 + 5 × 02 = 11
3 → 2 → 1 → 5 (3,0,1) 2 × 32 + 3 × 02 + 5 × 12 = 23
4 → 2 → 1 → 5 (2,1,1) 2 × 22 + 3 × 12 + 5 × 12 = 16
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
Tổng chi phí vận chuyển của các xe là: 8 + 18 + 11 + 7+ 8 + 5 + 13+ 11 + 23 + 16 = 120.
Theo kế hoạch canh tác các năm tiếp theo:
- Trong năm thứ 1, các ngôi làng thứ 1,2,3,4,5 sẽ lần lượt sản xuất các loại nông sản thứ 
1,3,1,2,3. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi 
phí vận chuyển của các xe là: 7 + 13 + 10 + 7 + 7 + 8 + 22 + 10 + 28 + 25 = 137.
- Trong năm thứ 2, các ngôi làng thứ 1,2,3,4,5 sẽ lần lượt sản xuất các loại nông sản thứ 
1,3,2,2,3. Số lượng xe và lộ trình di chuyển của các xe vẫn giống như ở trên, nhưng tổng chi 
phí vận chuyển của các xe là: 7 + 10 + 10 + 7 + 8 + 8 + 22 + 17 + 25 + 25 = 139.
 ----------HẾT----------
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
 ĐÁP ÁN
Câu 1: Ba đường truyền điện (7,0 điểm)
- Subtask 1: Có 20% số test ứng với 20% số điểm thỏa mãn: , ,푄 ≤ 40 và 풯 = 1.
Duyệt tất cả các trường hợp: 3 đường dọc, 3 đường ngang, 2 dọc 1 ngang và 1 ngang 2 dọc. 
Số lượng 3 đường có thể chọn là ( 3), việc tính toán cho mỗi đường là ( ). Với mỗi 
truy vấn, cập nhật giá trị điểm và tính lại.
Độ phức tạp tính toán của thuật toán là ( 4 × 푄).
- Subtask 2: 20% số test khác ứng với 20% số điểm thỏa mãn: , ,푄 ≤ 100 và 풯 = 1.
Sử dụng việc tính trước tổng các hàng và các cột làm cho việc tính tổng 3 đường tính cả việc 
cập nhật là (1). Với mỗi truy vấn, độ phức tạp tính là ( 3).
Độ phức tạp tính toán của thuật toán là ( 3 × 푄).
- Subtask 3: 20% số test khác ứng với 20% số điểm thỏa mãn: , ,푄 ≤ 500 và 풯 = 1.
Ta có nhận xét rằng việc chọn 3 đường ngang hoặc 3 đường dọc tốt nhất chỉ mất độ phức tạp 
thuật toán là ( ). Còn với việc có 1 đường ngang (dọc) và 2 đường dọc (ngang), ta duyệt 
theo hàng ngang và cập nhật giá trị của 2 đường dọc tốt nhất. Độ phức tạp thuật toán cho mỗi 
truy vấn là ( 2).
Độ phức tạp tính toán của thuật toán là ( 2 × 푄).
- Subtask 4: 20% số test khác ứng với 20% số điểm thỏa mãn: ,푄 ≤ 1000 và 
Σ ,Σ푄 ≤ 2000. Cải tiến từ subtask 3 , ta sử dụng cấu trúc dữ liệu để cập nhật và truy vấn 2 
đường dọc tốt nhất sau khi cập nhật đường ngang. Thêm vào đó, ta sử dụng việc rời rạc hóa 
bài toán để số lượng đường cần duyệt là ( ). Độ phức tạp thuật toán cho mỗi truy vấn là 
 ( log ).
Độ phức tạp tính toán của thuật toán là ( log × 푄).
- Subtask 5: 10% số test khác ứng với 10% số điểm thỏa mãn: ≤ 1000 và Σ ≤ 2000.
Nhận xét là kết quả bài toán chỉ thay đổi khi 1 trong 3 đường đi qua điểm mới cập nhật. Nên 
ta sẽ tính trước tất cả kết quả tối ưu cho 2 đường còn lại. Khi đó, phương án tối ưu nếu buộc 
sử dụng điểm mới cập nhật là công suất tính trước cộng thêm công suất tăng thêm. Để tính 
trước 2 đường còn lại, ta duyệt 1 đường và tìm ra đường tối ưu còn lại bằng cấu trúc dữ liệu.
Số lượng trường hợp cần tính trước là ( 2). Độ phức tạp tính toán cho việc tính toán trước 
là 2log .
Dộ phức tạp tính toán của thuật toán là 2log + 푄 .
- Subtask 6: 10% số test còn lại ứng với 10% số điểm: 
 9 5 5
 ≤ 10 ; ,푄 ≤ 10 ;Σ ,Σ푄 ≤ 2 × 10 . Tương tự Subtask 5 , ta duyệt 1 đường và tìm 2 
dường tốt nhất còn lại. Nhưng với mỗi đường dọc ta chỉ cần lưu lại 2 đường đi có tổng lớn 
nhất mà không quan tâm đến tính dọc ngang của nó. Ta chỉ cần lưư trữ ( ) phương án, sử 
 DeThiHay.net Đề thi và Đáp án Kỳ thi chọn Học sinh giỏi Quốc gia THPT môn Tin học qua các năm - 
 DeThiHay.net
dụng cấu trúc dữ liệu việc tìm phương án mât (log ).
Độ phức tạp tính toán của thuật toán là ( log + 푄).
Câu 2: Cải thiện đánh giá (7,0 điểm)
- Subtask 1: Có 20% số test ứng với 20% số điểm thỏa mãn: ,푃 ≤ 1000.
Với mỗi truy vấn, ta thực hiện thuật toán tìm đường đi ngắn nhất Dijkstra hai lần với đỉnh 1 
và đỉnh 2. Độ phức tạp tính toán là (( + )log ). Sau đó, ta đếm từng đỉnh thỏa mãn 
điều kiện (1, ) ≤ (1, ) và (2, ) ≤ (2, ). Ta được thứ hạng của , làm tương tự với y. 
Độ phức tạp của bước này là ( ).
Độ phức tạp chung của thuật toán là (푄 × × log ) do ≤ +1.
- Subtask 2: Có 20% số test khác ứng với 20% số điểm thỏa mãn: Mỗi thành phố có nhiều 
nhất 2 con đường nối với thành phố khác.
Do đồ thị là liên thông nên chỉ có 2 trường hợp: Đồ thị là một đường thẳng hoặc đồ thị là 
một chu trình duy nhất.
+ Trong trường hợp đồ thị là một đường thẳng:
+ Nếu nằm trên đường đi từ 1 tới 2 thì hạng của là 1.
+ Nếu không nằm trên đường đi từ 1 tới 2:
+ Nếu ( ,1) ≤ ( ,2): ta dùng phương pháp tìm kiếm nhị phân với kết quả là số đỉnh gần 
1 hơn so với .
+ Nếu ( ,1) > ( ,2): ta dùng phương pháp tìm kiếm nhị phân với kết quả là số đỉnh gần 
2 hơn so với .
+ Trong trường hợp đồ thị là một chu trình: Sẽ có 2 đường đi khác nhau từ 1 tới 2. Ta áp 
dụng phương pháp tìm kiếm nhị phân trên 2 đường này để tính số đỉnh tốt hơn hoặc tương 
đương 푈 và .
Độ phức tạp tính toán là (푄 × log ).
- Subtask 3: Có 20% số test khác ứng với 20% số điểm thỏa mãn: Mọi con đường có một 
trong hai đầu mút là thành phố số 1 hoặc thành phố số 2 .
Với đồ thị dạng này, cạnh được cập nhật chi phí mới sẽ không làm thay đổi chi phí của các 
đỉnh khác. Với mỗi truy vấn, ta cập nhật giá trị ′( ,1) và ′( ,2). Bài toán quy về cho 
điểm ( , ) trên mặt phẳng, mỗi truy vấn cần đếm xem có bao nhiêu điểm ( , ) thỏa mãn 
 ≤ ( ,1) và ≤ ( ,2). Bài toán này ta có thể xử lý offline bằng cách sweep line theo tọa 
độ và dùng một cấu trúc dữ liệu dạng cây để đếm xem có bao nhiêu điểm có ≤ ( ,2) 
trong dộ phức tạp (log ).
Độ phức tạp chung của thuật toán là (푄 × log ).
- Subtask 4: Có 20% số test khác ứng với 20% số điểm thỏa mãn: Quốc gia Beta có đúng N-
1 con đường.
 DeThiHay.net