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

 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ví dụ:
 BOMCHUM.INP BOMCHUM.OUT 
 4 3 7 18 13
 2 4 10 9
 4 18 12 28 14
 10 11 12 13
Giải thích: 
Gọi G(x) là tổng các ước của x.
Test ví dụ 1 có: 
G (2) = 1 + 2 = 3; G (4) = 1 + 2 + 4 = 7; G (10) = 1 + 2 + 5 + 10 = 18;
G (9) = 1 + 3 + 9 = 13
Test ví dụ 2 có:
G (10) = 18; G (11) = 1 + 11 = 12;
G (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28; G (13) = 1 + 13 = 14;
Ràng buộc:
 4 3
- Subtask 1: (40% số điểm): 푞 ≤ 10 ; i ≤ 10 (1 ≤ 푖 ≤ 푞)
 4 5 6
- Subtask 2: (40% số điểm): 10 < 푞 ≤ 10 ; i ≤ 10 (1 ≤ 푖 ≤ 푞)
- Subtask 3: (20% số điểm): 
 5 6 12
10 < 푞 ≤ 10 ; i ≤ 10 (1 ≤ 푖 ≤ 푞); i+1 = i + 1 (1 ≤ 푖 < 푞)
Bài 2. TỆP NHẬT KÝ
An lưu trên máy tính một tệp nhật ký, là một chuỗi gồm N sự kiện được ghi lại. Mỗi sự kiện 
được thể hiện bởi một số nguyên mà chỉ có An mới biết được ý nghĩa của nó. Bảo mật độ K 
của tệp nhật ký là số cặp số nguyên trong chuỗi sự kiện có tổng bằng K.
Thật không may máy tính của An bị vi rút xâm nhập và tệp nhật ký đã bị nhiễm vi rút. Chuỗi 
sự kiện đã bị thay đổi bởi những chữ cái La tinh in thường và dấu cách được chèn vào giữa 
các sự kiện. Hệ điều hành của máy tính An nhận diện được vi rút và cảnh báo một mã lỗi là 
một số nguyên S (|S| ≤ 109). An hiểu được, muốn khôi phục lại tệp nhật ký ban đầu cần phải 
xác định độ bảo mật độ S của tệp nhật ký đó. 
Yêu cầu: Với tệp bị nhiễm vi rút nói trên, nhiệm vụ của bạn là giúp An xác định được độ 
bảo mật của tệp nhật ký để An có thể khôi phục lại dữ liệu của mình.
Dữ liệu: Vào từ tệp văn bản NHATKY.INP gồm:
- Dòng đầu là một số nguyên dương N (N ≤ 106).
- Dòng thứ hai là xâu kí tự thể hiện tệp nhật ký bị nhiễm vi rút, gồm các chữ cái La tinh in 
thường và dấu cách được chèn vào giữa các sự kiện.
- Dòng thứ ba gồm một số nguyên S là mã lỗi mà hệ điều hành thông báo.
Các số nguyên thể hiện cho các sự kiện có có giá trị tuyệt đối không quá 109.
- Kết quả: Ghi ra tệp văn bản NHATKY.OUT gồm một số nguyên là độ bảo mật độ S của tệp 
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
nhật ký.
Ví dụ:
 NHATKY.INP NHATKY.OUT GIẢI THÍCH
8 5 Các cặp có tổng bằng 7 là (5,2), (2,5), 
5ab2c5xy3 4a3c13d-6 (3,4), (4,3), (13, -6)
7 Vậy bảo mật độ 7 của tệp nhật ký là 5
Ràng buộc: 
- Subtask 1: Có 30% số test tương ứng với 30% số điểm có 100 < N ≤ 104, tệp nhật ký bị 
nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
- Subtask 2: Có 20% số test tương ứng với 20% số điểm có 104 < N ≤ 105, tệp nhật ký bị 
nhiễm chỉ gồm các dấu cách được chèn vào giữa các sự kiện.
- Subtask 3: Có 30% số test tương ứng với 30% số điểm có 2 ≤ N ≤ 100 và không có ràng 
buộc gì thêm.
- Subtask 4: Có 20% số test tương ứng với 20% số điểm có 105 < N ≤ 106 và không có ràng 
buộc gì thêm.
Bài 3. BỜM VÀ PHÚ ÔNG
Sau khi Bờm đáp ứng hết các điều kiện mà Phú Ông đưa ra, Bờm lại thắng cuộc một lần nữa. 
Vì phần thưởng lần này quá lớn nên Bờm vội chạy về và lục soát khắp nhà mới tìm được 
một cái ba lô có sức chứa trọng lượng không vượt quá S. Bờm vội vã mang đến nhà Phú Ông 
nhận thưởng. Phú Ông có N thỏi vàng có trọng lượng lần lượt là a1, a2, , aN để cho Bờm 
lựa chọn. Bờm rất cẩn thận lựa chọn các thỏi vàng cho vào ba lô sao cho tổng trọng lượng 
lớn nhất mà không vượt quá sức chứa của nó.
Yêu cầu: Bạn hãy tính toán giúp Bờm có thể chọn những thỏi vàng để tổng trọng lượng là 
lớn nhất và đếm có bao nhiêu cách lựa chọn như vậy? (Hai cách chọn là khác nhau nếu khác 
nhau ít nhất một thỏi vàng).
Dữ liệu: Vào từ tệp văn bản PO.INP có cấu trúc như sau:
- Dòng đầu gồm 2 số nguyên N và S (0 < N ≤ 1000; 0 < S ≤ 50000; N S ≤ 5 106);
- Dòng thứ hai chứa số nguyên dương Q là loại truy vấn nhận giá trị 1 hoặc 2;
 3
- Dòng cuối gồm N số nguyên ai (0 < i ≤ , ≤ 풊 ≤ 푵).
Kết quả: Đưa ra tệp văn bản PO.OUT có cấu trúc như sau:
- Với Q = 1 thì chỉ ghi ra tổng trọng lượng lớn nhất có thể.
- Với Q = 2 thì ghi ra 2 dòng:
+ Dòng 1 ghi tổng trọng lượng lớn nhất có thể.
+ Dòng 2 ghi số cách Bờm có thể lựa chọn để đạt tổng trọng lượng lớn nhất chia lấy dư cho 
109+7.
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ví dụ:
 PO.INP PO.OUT PO.INP PO.OUT
3 4 4 3 7 6
1 2 2
3 1 4 4 6 2
Ràng buộc: 
- Có 60% test ứng với 60% số điểm có S ≤ 1000.
(40% test ứng với 40% điểm có Q=1, 60% test ứng với 60% điểm có Q=2).
Bài 4. KIẾN
Một khu vườn được xem xét như là một lưới các ô vuông, có một tổ kiến ở ô có tọa độ (0,0) 
và có một số ô trên lưới có vật cản. Một chú kiến muốn đi tìm thức ăn, kiến sẽ đi theo quy 
tắc sau:
- Từ một ô kiến có thể đi sang được 4 ô chung cạnh.
- Kiến không đi vào ô có vật cản
- Kiến không đi xa tổ quá S bước
Yêu cầu: Cho tọa độ các ô có vật cản và số S, hỏi kiến có thể đến được tất cả bao nhiêu ô.
Dữ liệu: Vào từ tệp văn bản ANT.INP gồm:
- Dòng đầu là 2 số nguyên C (số ô có vật cản) và S (0 ≤ C ≤ 10000; 1 ≤ S ≤ 107).
- C dòng sau, mỗi dòng 2 số nguyên xi , yi là tọa độ của các ô chứa vật cản.
 (|xi |, |yi| < 1001).
Kết quả: Ghi ra tệp ANT.OUT gồm dòng duy nhất là số ô mà kiến có thể đến được.
Ví dụ:
 ANT.INP ANT.OUT HÌNH MÔ TẢ CHO VÍ DỤ
4 5 26
-1 1
0 -1
0 1
1 0 1
 0 Tổ
 -1
 - 1 0 1
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ràng buộc:
- Subtask1: Có 70% số test ứng với 70% số điểm có S ≤ 103.
- Subtask2: Có 30% số test ứng với 30% số điểm có 103 S ≤ 107.
 -----------HẾT-----------
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1 (5,0 điểm). gồm có 25 test, mỗi test 0,2 điểm, thời gian 1s, bộ nhớ 1024 MB
 4 3
- Có 40% test tương ứng 40% số điểm với q ≤ 10 ; ai ≤ 10 (1 ≤ i ≤ q)
 4 5 6
- Có 40% test tương ứng 40% số điểm với 10 < q ≤ 10 ; ai ≤ 10 (1 ≤ i ≤ q)
- Có 20% test tương ứng 20% số điểm với 
 5 6 12
10 < q ≤ 10 ; ai ≤ 10 (1 ≤ i ≤ q); ai+1 = ai + 1 (1 ≤ i < q)
Bài 2 (5,0 điểm). gồm có 40 test, mỗi test 0,125 điểm, thời gian 1s, bộ nhớ 1024 MB
- Có 30% số test tương ứng với 30% số điểm có 100 < N ≤ 104, tệp nhật ký bị nhiễm chỉ gồm 
các dấu cách được chèn vào giữa các sự kiện.
- Có 20% số test tương ứng với 20% số điểm có 104 < N ≤ 105, tệp nhật ký bị nhiễm chỉ gồm 
các dấu cách được chèn vào giữa các sự kiện.
- Có 30% số test tương ứng với 30% số điểm có 2 ≤ N ≤ 100 và không có ràng buộc gì thêm.
- Có 20% số test tương ứng với 20% số điểm có 10 5 < N ≤ 10 6 và không có ràng buộc gì 
thêm.
Bài 3 (5,0 điểm). gồm có 20 test, mỗi test 0,25 điểm, thời gian 1s, bộ nhớ 1024 MB
- Có 60% test tương ứng với 60% số điểm có S ≤ 1000.
- (40% test ứng với 40% điểm có Q = 1, 60% test ứng với 60% điểm có Q = 2).
Bài 4 (5,0 điểm). gồm có 20 test, mỗi test 0,25 điểm, thời gian 1s, bộ nhớ 1024 MB
- Có 70% số test ứng với 70% số điểm có S ≤ 103.
- Có 30% số test ứng với 30% số điểm có 103 S ≤ 107.
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
 ĐỀ SỐ 4
SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12
 ĐỒNG THÁP NĂM HỌC 2022-2023
 MÔN: TIN HỌC
 Thời gian: 180 phút, không kể thời gian phát đề
 Tổng quan đề thi
 Tên tệp chương 
 Tên bài Tên tệp dữ liệu vào Tên tệp dữ liệu ra
 trình
Bài 1. Phương trình bậc hai PTB2.* PTB2.INP PTB2.OUT
Bài 2. Đoàn xe qua cầu DOANXE.* DOANXE.INP DOANXE.OUT
Bài 3. Vận chuyển VANCHUYEN.* VANCHUYEN.INP VANCHUYEN.OUT
Ghi chú: Kí tự * là phần mở rộng của tệp chương trình tùy theo ngôn ngữ lập trình (ngôn 
ngữ C++ là.cpp, ngôn ngữ Python là.py). Thời gian thực hiện chương trình không quá 01 
giây.
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI
 Sau khi học phương pháp giải phương trình bậc hai, các bạn học sinh được thầy giáo cho 
các bài tập để luyện tập. Các học sinh rất hào hứng đua nhau giải các bài tập xem ai hoàn 
thành sớm nhất. Để tăng thêm phần hấp dẫn, thầy giáo đã yêu cầu các học sinh làm bài toán 
ngược lại: cho trước n số nguyên dương đôi một khác nhau u1,u2,,un, hãy tìm ba số khác 
nhau trong dãy số đã cho làm ba hệ số a,b,c để phương trình bậc hai ax2 +bx + c = 0 có 
nghiệm là -1. Khi bắt tay vào làm bài, các học sinh phát hiện ra rằng có rất nhiều cách chọn 
ra các bộ ba hệ số a,b,c thỏa điều kiện và các em muốn đếm xem có tất cả bao nhiêu cách 
chọn như thế.
Yêu cầu: Hãy cho biết có bao nhiêu cách chọn ba phần tử khác nhau trong dãy số đã cho 
làm ba hệ số a,b,c để phương trình bậc hai ax2 +bx + c = 0 có nghiệm là -1.
Dữ liệu vào: Cho từ tệp văn bản PTB2.INP có dạng:
- Dòng thứ nhất ghi số nguyên dương n(3 ≤ n ≤ 105);
 9
- Dòng thứ hai ghi n số nguyên dương u1,u2,,un 0 < ui ≤ 10 ,i = 1..n;ui ≠ uj ∀i ≠ j).
Các số trên cùng một dòng được ghi cách nhau môt dấu cách.
Kết quả: Ghi ra tệp văn bản PTB2.OUT gồm một dòng ghi một số nguyên là số cách tìm 
được.
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ví dụ:
 PTB2.INP PTB2.OUT
 6 2
 42137510
Giải thích: Có 2 cách chọn:
Cách 1: a = 2, b = 7,c = 5; phương trình 2x2 +7x + 5 = 0 có nghiệm x = ―1
Cách 2: a = 5, b = 7,c = 2; phương trình 5x2 +7x + 2 = 0 có nghiệm x = ―1
Giới hạn dữ liệu:
- Có 70% số test ứng với 70% số điểm có giá trị n ≤ 300;
- Có 20% số test ứng với 20% số điểm có giá trị n ≤ 3000;
 5
- Có 10% số test ứng với 10% số điểm có giá trị n ≤ 10 ,ui ≤ n.
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU
Trên tuyến đường một chiều, tình trạng giao thông trở nên đông đúc. Để đảm bảo an toàn, cơ 
quan chức năng phân nhóm cho các xe qua cầu. Các xe phải di chuyển tuần tự theo nhóm 
(nghĩa là nhóm i chỉ được di chuyển sau khi toàn bộ xe của nhóm thứ i -1 đã qua cầu và các 
xe không được phép vượt nhau), tổng trọng lượng của các xe trong nhóm không được vượt 
quá tải trọng của cầu. Thời gian qua cầu của mỗi nhóm phụ thuộc vào xe có vận tốc thấp 
nhất trong nhóm
Có n xe đến cầu, các xe được đánh số từ 1 đến n, 푒 thứ i có trọng lượng wi, chạy với vận tốc 
v푖. Biết cầu có tải trọng P, chiều dài L. Giả thiết rằng P > w푖∀i = 1.n.
Yêu cầu: Bỏ qua khoảng cách giữa các xe, hãy tìm phương án tách đoàn xe thành từng nhóm 
để toàn bộ xe qua cầu được đảm bảo an toàn với tổng thời gian nhỏ nhất.
Dữ liệu vào: Cho từ tệp văn bản DOANXE.INP có dạng:
- Dòng đầu ghi ba số nguyên n,P,L(1 ≤ n ≤ 1000,1 ≤ P ≤ 100,1 ≤ L ≤ 103);
- Dòng thứ i trong n dòng tiếp theo ghi hai số nguyên w푖,v푖(1 ≤ w푖 ≤ P,1 ≤ v푖 ≤ 100). Các 
số trên cùng một dòng được ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản DOANXE.OUT gồm một dòng ghi một số thực là thời gian nhỏ 
nhất tìm được (làm tròn 2 chữ số thập phân).
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ví dụ:
DOANXE.INP DOANXE.OUT Giải thích
10100100 24.33 - Nhóm 1: Xe I - Thời gian qua cầu: 4.00
4025 - Nhóm 2: Xe 2,3 - Thời gian qua cầu: 5.00
5020 - Nhóm 3: Xe 4, 5, 6 - Thời gian qua cầu: 10.00
5020 - Nhóm 4: Xe 7,8 - Thời gian qua cầu: 3.33
7010 - Nhóm 5: Xe 9,10 - Thời gian qua cầu: 2.00
1250 - Tổng thời gian: 
970 4.00 + 5.00 + 10.ô + 3.33 + 2.00 = 24.33
4930
3835
2750
1970
Giới hạn dữ liệu:
- Có 60% số test ứng với 60% số điểm có giá trị n ≤ 10;
- Có 30% số test ứng với 30% số điểm có giá trị n ≤ 100;
- Có 10% số test ứng với 10% số điểm có giá trị n ≤ 1000.
Bài 3. (6,0 điểm) VẬN CHUYỂN
 Ngày nay, việc mua sắm trực tuyến trở nên phổ biến. Chúng ta có thể chọn đặt mua 
những sản phẩm thông qua các kênh bán hàng trực tuyến. Sau đó các đơn vị vận chuyển sẽ 
nhận kiện hàng và giao đến tận nhà.
 Một đơn vị vận chuyển có n trung tâm trung chuyển được đánh số từ 1 đến n. Giữa hai 
trung tâm trung chuyển được nối với nhau tối đa một tuyến đường hai chiều. Có tất cả m 
tuyến đường, tuyến dường thứ i nối hai trung tậm ai và bi có khoảng cách là ci(i = 1..m).
Yêu cầu: Hãy xác định tổng khoảng cách ngắn nhất để vận chuyển một kiện hàng từ trung 
tâm trung chuyển s đến trung tâm trung chuyển t.
Dữ liệu vào: Cho từ tệp văn bản VANCHUYEN.INP có dạng:
- Dòng thứ nhất ghi bốn số nguyên n,m,s,t(1 ≤ s,t ≤ n ≤ 105,1 ≤ m ≤ 105,s ≠ t);
- Dòng thứ i trong m dòng tiếp theo ghi ba số nguyên dương a푖,b푖,c푖(1 ≤ a푖,b푖 ≤ n, 
 9
a푖 ≠ b푖,0 < c푖 ≤ 10 ).
Các số trên cùng một dòng dıroc ghi cách nhau một dấu cách.
Kết quả: Ghi ra tệp văn bản VANCHUYEN.OUT gồm một dòng ghi một số nguyên dương 
là tổng khoảng cách ngắn nhất để vận chuyển kiện hàng từ trung tâm trung chuyển s đến 
trung tâm trung chuyển t.
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
Ví dụ:
 VANCHUYEN.INP VANCHUYEN.OUT
 5715 10
 123
 148
 235
 244
 355
 438
 453
Giới hạn dữ liệu:
- Có 80% số test ứng với 80% số điểm có giá trị n ≤ 103;
- Có 20% số test ứng với 20% số điểm có giá trị n ≤ 105.
 -----------HẾT-----------
 DeThiHay.net 21 Đề thi Học sinh giỏi các cấp môn Tin học Lớp 12 (Có đáp án) - DeThiHay.net
 ĐÁP ÁN
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI. Gồm 10 bộ test, mỗi bộ test 0,7 điểm.
 Test PTB2.OUT Điểm
 1 30 82 0,7
 2 70 236 0,7
 3 120 372 0,7
 4 175 462 0,7
 5 250 604 0,7
 6 285 252 0,7
 7 300 132 0,7
 8 2993 20 0,7
 9 3000 13158 0,7
 10 99997 4999600008 0,7
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU. Gồm 10 bộ test, mỗi bộ test 0,7 điểm.
 Test DOANXE.INP DOANXE.OUT Điểm
 1 11010 0.17 0,7
 2 32030 1.20 0,7
 3 53050 2.80 0,7
 4 85080 22.53 0,7
 5 96085 26.97 0,7
 6 105065 20.04 0,7
 7 508090 115.60 0,7
 8 808070 203.77 0,7
 9 100100100 428.19 0,7
 10 1000100100 4600.12 0,7
 DeThiHay.net