10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án)

 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1. Đường đi trên ma trận (6 điểm)
- Có 25% số test với n,m ≤ 10: Duyệt toàn bộ đường đi có thể có.
- Có 30% số test với n ≤ 3: Xem như không có ràng buộc về số lần đi xuống. Sử dụng thuật 
toán quy hoạch động để tìm đường đi có tổng lớn nhất, bằng cách gọi f[i][j] là tổng phần 
thưởng lớn nhất nếu xuất phát tại ô (i, j).
- Có 45% số test với ràng buộc gốc: Tương tự như subtask trên, nhưng bổ sung thêm thông 
tin về số lần đi xuống liên tiếp: Gọi f[i][j][k] là tổng phần thưởng lớn nhất nếu xuất phát tại ô 
(i, j) và được phép đi xuống k lần liên tiếp.
Bài 2. Giải mã xâu (7 điểm)
- Có 30% số test với k ≤ 10: Duyệt qua tất cả các hoán vị và kiểm tra xem nó có phải là một 
từ trong từ điển hay không. Nếu nó là từ trong từ điển, kiểm tra nó có phải là xâu con của 5 
hay không.
- Có 30% số test với xâu s chỉ gồm các ký tự dấu sao *: Tất cả các xâu trong từ điển đều là 
xâu con của s, do đó chỉ cần đếm số xâu trong từ điển. Có thể làm điều này bằng thuật toán 
quy hoạch động sử dụng bitmask: Gọi f[i][mask] là số lượng hoán vị độ dài i, gồm các ký tự 
trong tập mask.
- Có 40% số test với ràng buộc gốc: Sử dụng thuật toán quy hoạch động tương tự như 
subtask trước, bổ sung thêm thông tin về vị trí đã khớp của hoán vị hiện tại trên xâu s để 
kiểm tra xâu con: Gọi f[i][mask][j] là số hoán vị độ dài i, gồm các ký tự trong tập mask, là 
xâu con của 5[1..j].
Bài 3. Thuê phòng họp (7 điểm)
Có 16% số test với n ≤ 100: Chuẩn bị trước ma trận khoảng cách giữa tất cả các địa điểm 
bằng thuật toán Floyd. Với mỗi truy vấn, xét từng đỉnh để kiểm tra và tìm phương án tối ưu.
Có 24% số test với Q ≤ 100. Trả lời từng truy vấn như subtask trước, nhưng tìm đường đi 
ngắn nhất bằng thuật toán Dijkstra.
 14
Có 28% số test với rj = 10 với mọi j = 1,2,...,Q: Bỏ qua được ràng buộc về khoảng cách. 
Bài toán đưa về: Tìm địa điểm có giá thuê rẻ nhất thoả mãn diện tích thuộc phạm vi [L,H]. 
Có thể giảm phạm vi giá trị của diện tích, sau đó dùng cây phân đoạn (IT) để quản lý và truy 
vấn. Chiều phạm vi của cây là diện tích, chiều giá trị của cây là giá thuê.
Có 32% số test với ràng buộc gốc: Dùng cây phân đoạn tương tự như subtask trước, nhưng 
thứ tự nạp các đỉnh vào cây không phải từ 1 đến n. Thay vào đó, sắp xếp lại các truy vấn 
tăng dần theo rj, sau đó vừa trả lời truy vấn vừa bổ sung thêm các địa điểm mới vào cây theo 
chiều tăng dần của khoảng cách đến đỉnh 1.
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 ĐỀ SỐ 5
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH ĐỢT 2
 TỈNH QUẢNG NAM Môn thi: TIN HỌC 11 (CHUYÊN)
 ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề)
 (Đề gồm có 03 trang)
 Tổng quan về đề thi
Bài Tên bài Tên file chương trình Dữ liệu vào Dữ liệu ra
 1 SPORT SPORT.* SPORT.INP SPORT.OUT
 2 GAME GAME.* GAME.INP GAME.OUT
 3 MEGA MEGA.* MEGA.INP MEGA.OUT
Dấu * được 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à 
Free Pascal hoặc C++. 
Câu 1. (6,0 điểm) SPORT
 Một Sư đoàn A có N chiến sĩ, các chiến sĩ có chỉ số thể lực tương ứng theo thứ tự a1, 
a2,, aN. Để chuẩn bị cho hội thao hàng năm giữa các Sư đoàn với nhau, Sư đoàn A tổ chức 
một hội thi để chọn ra các đội có kết quả cao nhất để tham gia hội thao. Sau một thời gian 
huấn luyện về thể lực, Sư đoàn cần chọn ra các đội gồm các chiến sĩ có chỉ số thể lực hoàn 
hảo để tham gia hội thao. 
 Chỉ số thể lực hoàn hảo là đội gồm 3 chiến sĩ có vị trí là i, j, k, độ chênh lệch thể lực 
giữa 2 chiến sĩ trong đội là D sao cho i < j < k và ai – D ≥ aj và aj – D ≥ ak.
Yêu cầu: Hãy đếm số đội có thể tham gia hội thao của sư đoàn A.
Dữ liệu vào: Đọc từ tệp SPORT.INP
- Dòng đầu tiên là số N, D.
- Dòng tiếp theo ghi N số nguyên a1, a2,, aN.
Kết quả ra: Ghi ra tệp SPORT.OUT 
- Ghi ra một số duy nhất là số đội nhiều nhất có thể chọn.
Ví dụ:
 SPORT.INP SPORT.OUT GIẢI THÍCH
5 2 4 Có 4 đội tham gia hội thao với độ chênh lệch 
2 8 6 4 2 thể lực là:
 {8,6,4};{8,6,2}; {8,4,2};{6,4,2}
Giới hạn:
 5 9
- Subtask 1: 40% test có 1 ≤ ≤ 400;1 ≤ ≤ 10 ;| 푖| ≤ 10 ;
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 3 5 5
- Subtask 2: 30% test có 10 ≤ N ≤ 10 ; D = 1 ; | 푖| ≤ 10
 3 5 5 9
- Subtask 3: 30% test có 10 ≤ N ≤ 10 ; 1 ≤ D ≤ 10 ; | 푖| ≤ 10
Bài 2. (7,0 điểm) GAME
 Trong giờ học Toán, thầy giáo của An có ra một trò chơi để tạo không khí vui tươi và 
đoàn kết các bạn trong lớp. Trò chơi có nội dung như sau: cho dãy gồm 푛 số nguyên không 
âm, nhiệm vụ của các bạn trong lớp là hãy chia dãy thành k + 1 đoạn khác rỗng, để thu được 
k+1 đoạn, người chơi cần lặp lại các bước sau đây lần:
Bước 1. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên người chơi chỉ có một 
đoạn, đó chính là dãy ban đầu).
Bước 2. Chọn một vị trí nào đó ở giữa đoạn đã chọn để chia nó ra làm hai đoạn mới khác 
rỗng.
Mỗi lần thực hiện xong hai bước này người chơi nhận được một điểm số bằng tích của hai 
tổng các số trong hai đoạn mới chia ra. 
Yêu cầu: Với cách chơi như trên, bạn hãy lập trình giúp An tìm ra cách để đạt được tổng 
điểm lớn nhất. 
Dữ liệu vào: Đọc từ tệp GAME.INP gồm:
- Dòng đầu tiên chứa hai số nguyên dương 푛 và ( + 1 ≤ 푛 ≤ 3000);
 4
- Dòng thứ hai chứa n số nguyên không âm a 1, a2, ..., an (0 ≤ ai ≤ 10 , 1 ≤ i ≤ n) là các phần 
tử của dãy số.
Kết quả ra: Ghi vào tệp GAME.OUT
Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được. 
Ví dụ:
 GAME.INP GAME.OUT
7 3 108
1 3 4 0 2 3 4
Giải thích ví dụ:
Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:
- Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử 
dụng điểm chia sau phần tử thứ sáu và nhận được: (1 + 3 + 4 + 0 + 2 + 3) × 4 = 52 điểm.
- Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: 
(1 + 3) × (4 + 0 + 2 + 3) = 36 điểm.
- Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được:
(4 + 0) × (2 + 3) = 20 điểm.
Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) 
và nhận được: 52 + 36 + 20 = 108 điểm.
Giới hạn:
- Subtask 1: Có 60% số test có n ≤ 300;
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
- Subtask 2: Có 40% số test có n ≤ 3000.
Bài 3. (7,0 điểm) MEGA
 Đất nước Mega được mệnh danh là vùng đất có rất nhiều đảo đẹp và yên bình. Hàng 
năm có rất nhiều tàu thuyền khắp nơi trên thế giới ghé thăm đất nước Mega để tham quan, du 
lịch và kinh doanh. Để phát triển kinh tế, giao thương và thu hút đầu tư nước Mega đã kêu 
gọi sự đầu tư của nhiều công ty lớn trên thế giới đến xây dựng các cảng biển. Đến thời điểm 
hiện tại đã xây dựng được 푛 cảng biển, các cảng này được kết nối với nhau với hệ thống giao 
thông đường thủy gồm m đường 2 chiều, đảm bảo sự giao thương giữa 2 cảng bất kỳ (trực 
tiếp hoặc gián tiếp thông qua cảng trung gian). Giữa 2 cảng bất kỳ có không quá một đường 
đi trực tiếp.
 Việc đầu tư, vận hành, bảo trì các cảng này được giao cho 2 công ty lớn là Greek (G) 
và Yamato (Y) độc quyền đảm nhận. Các tàu thuyền hoạt động trên các cảng này đều thuộc 
quyền sở hữu của 2 công ty trên thực hiện. Các tàu thuyền khi vận chuyển hàng và người từ 
cảng này sang cảng khác thì chủ thuyền phải trả chi phí là 1 đơn vị tiền tệ, ngoài ra tàu 
thuyền khi đi qua cảng mà không phải do công ty mình quản lý thì chủ thuyền phải trả thêm 
3 đơn vị tiền tệ. Tất nhiên, khi vận chuyển hàng hóa và người, chủ thuyền bao giờ cũng chọn 
con đường ứng với tổng chi phí nhỏ nhất.
Yêu cầu: Cho biết n, m và mạng giao thông trong Mega, hãy giúp công ty G và Y tính tổng 
chi phí vận chuyển hàng giữa tất cả các cảng biển thuộc tập đoàn của họ. 
Dữ liệu vào: Đọc từ tệp MEGA.INP có cấu trúc:
- Dòng đầu tiên chứa hai số nguyên n, m.
- Dòng thứ hai chứa xâu gồm n ký tự, mỗi ký tự là G hoặc Y, ký tự thứ 푖 cho biết cảng 푖 
thuộc tập đoàn G hay Y. 
- Tiếp theo là m dòng, mỗi dòng chứa hai số nguyên i, j xác định đường nối cảng i với cảng 
j. 
Kết quả ra: Ghi ra tệp MEGA.OUT có cấu trúc:
- Gồm một dòng chứa hai số tương ứng là tổng chi phí vận chuyển hàng giữa tất cả các cảng 
thuộc tập đoàn G và Y.
Ví dụ:
 MEGA.INP MEGA.OUT
5 5 5 11
YGYGY 
1 2 
2 3 
3 4 
4 5 
5 1
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
Giới hạn:
- Subtask 1: Có 60% số test có n ≤ 100; m ≤ 5000
- Subtask 2: Có 40% số test có n ≤ 1000; m ≤ 5000
 ----------HẾT----------
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1. (6.0 điểm) SPORT: gồm có 40 test; mỗi test 0,15 điểm, thời gian 1 giây, bộ nhớ 1024 
MB
TEST SPORT.INP SPORT.OUT
1 5 2 0
 3 4 3 5 2
2 5 1 10
 5 4 3 2 1
. . .
40 . .
Bài 2. (7.0 điểm) GAME: gồm có 35 test, mỗi test 0.2 điểm, thời gian 1 giây, bộ nhớ 1024 MB
TEST GAME.INP GAME.OUT
1 7 3 108
 1 3 4 0 2 3 4
2 276 42 915433746673
 8357 6465 1050 1153 7109 9287 2309 2266 537 
 517 9283 193 3539 1960 3382 6499 252 2333 
 500 1353 711 6691 6227 5453 4889 1190 1570 
 213 9271 8651 7687 5539 4672 295 1794 6636 
 6036 5734 6440 5868 7479 9806 8343 3930 8389 
 3173 3461 8682 9888 4214 6816 462 7120 9618 
 5779 3711 8267 4434 3493 3735 5107 2533 3574 
 6469 783 4003 5443 1658 8929 6373 2355 7534 
 2455 3331 7550 2003 4687 7106 1119 6182 8317 
 1999 4738 164 9595 7604 840 2823 7156 2863 
 5251 5652 4054 1333 7940 3343 6857 4675 188 
 6678 3420 8354 6285 3950 3940 4840 1561 6422 
 9294 7176 395 820 6660 3648 9639 1799 8829 
 6339 5224 2154 593 6373 1829 396 6062 4568 
 954 7720 2155 3243 2002 3235 1709 3666 6021 
 3530 4164 2903 2424 9642 6918 8141 1890 4038 
 8247 9625 8467 7180 6919 8132 9658 7883 807 
 7991 1583 4040 2581 6402 1203 556 5527 8341 
 9624 8860 7150 2124 6392 8793 1597 1998 90 
 7369 4107 9352 3415 1660 4548 1909 6119 6018 
 287 9613 2838 1851 2293 2627 7871 4557 2859 
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 7842 7099 6689 7481 5328 6657 8778 8566 1075 
 7996 2249 1290 9944 9748 6448 4057 3792 9322 
 171 1297 6988 4008 3923 5708 4535 9003 2908 
 830 3180 1270 6784 8019 1012 7867 9487 9374 
 9272 1146 2001 5523 8886 4449 4668 9499 8821 
 2168 3986 8820 2825 1537 7362 9641 3835 3135 
 9159 7171 8119 3226 6052 8799 4966 4890 743 
 5747 4746 3842 2425 262 9222 5027 5488 34 
 4631 1407 8524 8615 2002 7965 7483 521 9940 
 7347 5563 6312 3619 8737 6309
 . .
35 . .
Bài 3. (7.0 điểm) MEGA: gồm có 40 test; mỗi test 0,175 điểm, thời gian 1 giây, bộ nhớ 
1024 MB
TEST MEGA.INP MEGA.OUT
1 5 5 5 11
 YYGYG
 1 2
 5 1
 3 4
 3 2
 5 4
2 3 2 5 0
 YGG
 1 2
 3 1
 . .
40 . .
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 ĐỀ SỐ 6
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT ĐỢT 2
 TỈNH QUẢNG NAM Môn thi: TIN HỌC 11 (CHUYÊN)
 ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề)
 (Đề gồm có 04 trang)
 Tổng quan đề thi
 Tên file chương 
Bài Tên bài Dữ liệu vào Dữ liệu ra
 trình
 1 Đếm trại sinh COUNT.* COUNT.INP COUNT.OUT
 2 Ngôi sao may mắn STAR.* STAR.INP STAR.OUT
 3 Khỉ ăn chuối BANANA.* BANANA.INP BANANA.OUT
 4 Tình đồng chí COMRADE.* COMRADE.INP COMRADE.OUT
Dấu * được 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à 
Free Pascal hoặc C++. 
Hãy lập trình giải các bài toán sau:
Bài 1. (5.0 điểm) Đếm trại sinh
 Trong đợt sinh hoạt trại 26/3 tại trường THPT A, Ban quản trại tổ chức cho các trại 
sinh tham gia trò chơi nối vòng tay lớn. Có N trại sinh tham gia, đứng thành vòng tròn, mỗi 
trại sinh lần lượt mang số hiệu từ 1 đến N. Người quản trại tiến hành đếm từ trại sinh thứ 1, 
qua trại sinh thứ 2, đếm đến trại sinh thứ K, thì người này rời khỏi vòng tròn và trại sinh 
kế tiếp lại bắt đầu từ 1. Trò chơi kết thúc khi trên vòng tròn còn đúng 1 trại sinh, đây là trại 
sinh thắng cuộc. 
 Bạn An là trại sinh tham gia sinh hoạt trại, nên muốn mình sẽ là người chiến thắng 
(trại sinh còn lại sau cùng).
Yêu cầu: Hãy viết chương trình giúp bạn An chọn vị trí đứng trong vòng tròn để là người 
thắng cuộc trong trò chơi nối vòng tay lớn. 
Dữ liệu vào: Đọc từ file văn bản COUNT.INP gồm:
- Dòng đầu tiên ghi số nguyên dương N là số trại sinh tham gia (N ≤ 107);
- Dòng thứ hai ghi số nguyên dương K (K ≤ 2 x 109). 
Kết quả: Ghi ra file văn bản COUNT.OUT một số nguyên, là vị trí đứng trong vòng tròn 
của người thắng cuộc. 
Ví dụ:
 COUNT.INP COUNT.OUT
50 22
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
15
100000 12243
123456
Ràng buộc:
- Có 40% test tương ứng 40% số điểm của bài với N ≤ 103, K ≤ 106; 
- Có 30% test tương ứng 30% số điểm của bài với 103 ≤ N ≤ 106, K ≤ 106;
- Có 30% test tương ứng 30% số điểm của bài với 103 ≤ N ≤ 107, K ≤ 2 x 109.
Bài 2. (5.0 điểm) Ngôi sao may mắn
 Để tham gia trò chơi tìm ngôi sao may mắn, An luôn suy nghĩ cách chọn một ngôi sao 
nào đó từ hai dãy đặt ngôi sao theo kiểu quanh co (thoạt đầu các ngôi sao của hai dãy chưa 
được chọn). Mỗi lượt chơi là quá trình An phải chọn ít nhất một ngôi sao theo cách sau:
- Chọn một ngôi sao tùy ý chưa từng được chọn từ một trong hai dãy đặt ngôi sao.
- Giả sử ở bước thứ T, An đã chọn ngôi sao có chỉ số i từ một dãy nào đó và nếu vẫn tiếp tục 
lượt chơi thì ở bước T + 1, An phải chọn một ngôi sao nào đó (chưa từng được chọn) từ dãy 
kia với chỉ số j mà i < j.
- Lượt chơi được coi là kết thúc nếu An không thể chọn tiếp được ngôi sao nào nữa (theo 
cách trên) hoặc An chủ động dừng cuộc chơi nếu muốn.
Điểm số mà An dành được sau mỗi lượt chơi chính là tổng của tất cả mã số đính kèm trên 
ngôi sao được chọn trong lượt chơi đó.
Yêu cầu: Xác định điểm số tối đa mà An đạt được từ lượt chơi đầu tiên.
Dữ liệu vào: Đọc từ file văn bản STAR.INP gồm:
- Dòng đầu tiên chứa số nguyên dương N (N ≤ 106);
- Dòng thứ hai chứa N số nguyên, là mã số của các ngôi sao thuộc dãy thứ nhất;
- Dòng thứ ba chứa N số nguyên, là mã số của các ngôi sao thuộc dãy thứ hai. 
(Tất cả các số hạng của hai dãy đều có giá trị tuyệt đối nhỏ hơn 10 9, các số cách nhau một 
khoảng trắng)
Kết quả: Ghi ra file văn bản STAR.OUT một số nguyên, là điểm số cao nhất mà An đạt 
được từ lượt chơi đầu tiên.
Ví dụ:
 DeThiHay.net 10 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 11 (Có đáp án) - DeThiHay.net
 STAR.INP STAR.OUT
7 414
47 2 95 65 79 58 5
63 88 3 28 9 72 52
4 74
11 -23 45 52
22 -12 -15 5
Ràng buộc:
- Có 60% test tương ứng 60% số điểm của bài này với 1≤ N ≤ 20;
- Có 20% test tương ứng 20% số điểm của bài này với N ≤ 103;
- Có 20% test tương ứng 20% số điểm của bài này với N ≤ 106.
Bài 3. (5.0 điểm) Khỉ ăn chuối
 Mạnh là ông chủ của một rạp xiếc khá nổi tiếng. Nhận thấy xiếc khỉ đang thu hút được 
nhiều người đến xem, ông đã quyết định đầu tư mua một số lượng lớn khỉ về để kiếm lời. 
Những con khỉ trong rạp xiếc rất thích ăn chuối, để dạy chúng làm xiếc, Mạnh đã chuẩn bị 
rất nhiều chuối cho chúng ăn. Chuối được chứa trong N thùng, mỗi thùng chứa một số lượng 
các quả chuối. Các thùng được đánh số từ 1 đến N.
 Quy luật phát chuối cho một con khỉ là luôn phát hết chuối trong một thùng hoặc tất cả 
chuối chứa trong các thùng liên tiếp nhau.
 Việc chia các thùng chuối cho bọn khỉ được thực hiện theo thứ tự từ thùng 1 đến 
thùng N, vì các con khỉ rất tham ăn nên các con khỉ đến sau luôn muốn nhận được lượng 
chuối lớn hơn hoặc bằng lượng chuối con khỉ đến trước nhận được. Để không lãng phí, 
Mạnh muốn tất cả các thùng chuối đều được phát hết. 
Yêu cầu: Hãy giúp Mạnh tính xem số lượng con khỉ lớn nhất có thể nhận được chuối.
Dữ liệu vào: Đọc từ file văn bản BANANA.INP gồm:
- Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu (T ≤ 100) trong đó mỗi bộ dữ liệu 
gồm: 
+ Dòng đầu ghi số nguyên dương N là số lượng thùng chuối (2 ≤ N ≤ 5000);
+ Dòng tiếp theo chứa N số nguyên dương a i là số lượng chuối mỗi thùng, mỗi số cách nhau 
 9
một dấu cách (1 ≤ ai ≤ 10 ).
Kết quả: Ghi ra file văn bản BANANA.OUT gồm T dòng, mỗi dòng tương ứng với kết quả 
tính được của mỗi bộ dữ liệu vào.
 Ví dụ:
 BANANA.INP BANANA.OUT
 2 3 
 4 3
 1 2 1 2
 DeThiHay.net