Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án)

 Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
6 
6 4 2 2 2 2 
Ràng buộc: 
 5
- Có 50% test tương ứng 50% số điểm của bài với T =1, 2 ≤ N ≤ 100, 1 ≤ ai ≤ 10 ;
 9
- Có 30% test tương ứng 30% số điểm của bài với T =1, 100 ≤ N ≤ 1000, 1 ≤ ai ≤ 10 ;
 9
- Có 20% test tương ứng 20% số điểm của bài với T ≤ 100, 1000 ≤ N ≤ 5000, 1 ≤ ai ≤ 10 .
Bài 4. (5.0 điểm) Tình đồng chí
 Chị Liên là một giao liên hoạt động cách mạng trong kháng chiến chống Pháp. Chị nổi 
tiếng là người gan dạ và khôn khéo. Thực dân Pháp muốn có được chị để thực hiện mọi âm 
mưu tiêu diệt cán bộ cách mạng của ta. Trong một lần đi công tác, chị không may bị giặc 
Pháp bắt giam.
 Được biết, nơi chị bị giam là một nhà giam đặc biệt hình chữ nhật, có P x Q phòng 
giam. Nhà giam được đánh số phòng theo chiều từ trên xuống dưới bắt đầu 1 đến P, đánh số 
phòng từ 1 đến Q theo chiều từ trái qua phải. Giữa hai phòng giam sát nhau có cửa thông 
nhau, muốn mở cửa để đi từ phòng này sang phòng kia phải mất một khoảng thời gian nhất 
định nào đó. 
 Sáu là một chiến sĩ đặc công được giao nhiệm vụ giải cứu chị Liên. Sau hơn hai giờ 
đồng hồ dò tìm trong nhà giam, anh mới phát hiện giặc Pháp giam chị tại phòng giam cuối 
cùng [P,Q] - dòng P cột Q. 
 Còn về phía Pháp, chúng cho rằng đặc công của ta đang cấp bách tìm kiếm chị nên tìm 
cách tra tấn dã man nhằm moi hết thông tin từ chị rồi nhanh chóng thủ tiêu. Chúng nghĩ 
rằng, đặc công của ta sẽ kịp thời tìm ra được chị. Thời gian thủ tiêu chị Liên sắp đến 
Yêu cầu: Bạn nghĩ xem, anh Sáu mất thời gian ít nhất là bao lâu để cứu và đưa chị Liên ra 
khỏi nhà giam của Pháp? 
Dữ liệu vào: Đọc từ file văn bản COMRADE.INP gồm:
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu (T ≤ 10) trong đó mỗi bộ dữ liệu gồm:
+ Dòng thứ nhất là hai số nguyên P và Q cách nhau một khoảng trắng (1 ≤ P, Q ≤ 1000);
+ Trong P dòng tiếp theo, mỗi dòng gồm Q-1 số nguyên aij là khoảng thời gian để mở cửa từ 
phòng giam [i, j] sang phòng giam [i, j+1], hoặc khoảng thời gian để mở cửa từ phòng giam 
 5
[i, j+1] sang phòng giam [i, j] (1 ≤ aij ≤ 10 );
+ Trong P-1 dòng tiếp theo, mỗi dòng gồm Q số nguyên bij là khoảng thời gian để mở cửa từ 
phòng giam [i, j] sang phòng giam [i +1, j] hoặc khoảng thời gian để mở cửa từ phòng giam 
 5
[i+1, j] sang phòng giam [i, j] (1 ≤ bij ≤ 10 ).
Kết quả: Ghi ra file văn bản COMRADE.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ụ:
 COMRADE.INP COMRADE.OUT
1 86
4 6
7 1 4 4 5
8 6 2 8 4
7 2 6 3 3
9 1 9 1 2
53 22 69 40 98 94
48 29 69 52 68 53
72 17 94 61 15 98
Ràng buộc : 
- Có 50% test tương ứng với 50% số điểm bài với T = 1 và 1 ≤ P, Q ≤ 20;
- Có 30% test tương ứng với 30% số điểm bài với T = 1 và P, Q ≤ 1000;
- Có 20% test tương ứng với 20% số điểm bài với T ≤ 10 và P, Q ≤ 1000.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài 1 (5.0 điểm) gồm có 50 test, mỗi test 0,1 điểm, bộ nhớ 1024 MB
Có 40% test tương ứng 40% số điểm của bài với N ≤ 103, K ≤ 106 thời gian thực hiện 1s.
Có 30% test tương ứng 30% số điểm của bài với 103 ≤ N ≤ 106, K ≤ 106 thời gian thực hiện 
1s.
Có 20% test tương ứng 20% số điểm của bài với 103 ≤ N ≤ 107, K ≤ 2 x 109 thời gian thực 
hiện 1s.
Có 10% test tương ứng 10% số điểm của bài với 106 ≤ N ≤ 107, K ≤ 2 x 109 thời gian thực 
hiện 3s.
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ó 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) gồm có 40 test, mỗi test 0,125 điểm, bộ nhớ 1024 MB
 5
Có 50% test tương ứng 50% số điểm của bài với T = 1, 2 ≤ N ≤ 100, 1 ≤ ai ≤ 10 thời gian 
thực hiện 1s.
 9
Có 30% test tương ứng 30% số điểm của bài với T = 1, 100 ≤ N ≤ 1000, 1 ≤ ai ≤ 10 thời 
gian thực hiện 1s.
 9
Có 20% test tương ứng 20% số điểm của bài với T ≤ 100, 1000 ≤ N ≤ 5000, 1 ≤ ai ≤ 10 
thời gian thực hiện 2s.
Bài 4 (5.0 điểm) gồm có 40 test, mỗi test 0,125 điểm, bộ nhớ 1024 MB
Có 50% test tương ứng với 50% số điểm bài với T = 1 và 1 ≤ P, Q ≤ 20 thời gian thực hiện 
1s.
Có 30% test tương ứng với 30% số điểm bài với T = 1 và P, Q ≤ 1000 thời gian thực hiện 1s.
Có 10% test tương ứng với 10% số điểm bài với T ≤ 10 và P, Q ≤ 1000 thời gian thực hiện 
1s.
Có 10% test tương ứng với 10% số điểm bài với T ≤ 10 và P, Q ≤ 1000 thời gian thực hiện 
2s.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
 ĐỀ SỐ 7
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT
 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 về đề thi
 Tên file chương 
 Tên bài Dữ liệu vào Dữ liệu ra Thời gian
 trình
Bài 1: Tặng quà QUATANG.* QUATANG.INP QUATANG.OUT 1s
Bài 2: Dự tiệc GHENGOI.* GHENGOI.INP GHENGOI.OUT 1s
Bài 3: Phân tích số PHANTICH.* PHANTICH.INP PHANTICH.OUT 1s
Bài 4: Cắm trại CAMTRAI.* CAMTRAI.INP CAMTRAI.OUT 1s
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) Tặng quà
 An đạt giải cao trong kỳ thi Khoa học kĩ thuật cấp tỉnh vừa qua nên mẹ đã thưởng cho 
An một chuyến đi du lịch đến thành phố Nha Trang. Tại đây, An đã tham quan nhiều nơi và 
mua nhiều quà cho 3 người trong gia đình gồm ba, mẹ và em của An. Có N món quà được 
đánh số từ 1 đến N, trong đó món quà thứ i có giá trị sử dụng là ai. Gọi T1, T2, T3 lần lượt là 
tổng giá trị các món quà của mỗi người; Tmax và Tmin lần lượt là giá trị lớn nhất và nhỏ nhất 
của T1, T2, T3.
Yêu cầu: An muốn thể hiện sự công bằng của mình đối với ba, mẹ và em nên An nghĩ cách 
chia N món quà trên cho 3 người sao cho chênh lệch của Tmax và Tmin là nhỏ nhất. Các bạn 
chuyên Tin 11 hãy giúp An chia quà nhé!
Dữ liệu vào: Từ tệp văn bản QUATANG.INP gồm:
- Dòng thứ nhất là số nguyên N (1 < N < 15);
 3
- Dòng thứ hai gồm N số nguyên a1, a2, ,aN là giá trị của các món quà (1 < ai < 10 ).
Dữ liệu ra: Ghi ra tệp văn bản QUATANG.OUT gồm một số nguyên duy nhất cần tìm.
Ví dụ:
 QUATANG.INP QUATANG.OUT
6 2
5 7 8 4 3 15
Ràng buộc:
- Sub1: Có 50% test tương ứng 50% số điểm của bài với N < 5 và ai < 102;
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
- Sub2: Có 30% test tương ứng 30% số điểm của bài với N < 10 và ai < 102;
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N < 15 và ai < 103.
Bài 2: (5.0 điểm) Dự tiệc
 Công ty Bảo hiểm AB tổ chức buổi tiệc nhằm tri ân những khách hàng đã tham gia mua 
bảo hiểm. Giám đốc Công ty muốn tất cả các khách hàng đến dự tiệc được thoải mái và vui 
vẻ nên đã yêu cầu nhân viên lễ tân chuẩn bị trước những bàn tiệc với số lượng người trong 
mỗi bàn có thể khác nhau để tiện bố trí cho mỗi nhóm khách hàng muốn ngồi chung một 
bàn. Nhân viên lễ tân đã bố trí M bàn tiệc, bàn thứ i có đủ ghế ngồi cho ai người. Trước khi 
bắt đầu vào buổi tiệc, có N nhóm khách hàng đến dự, nhóm thứ j có bj người. Để khách hàng 
đến dự tiệc được ngồi cùng nhóm trong một bàn, nhân viên lễ tân linh động bằng cách kê 
thêm ghế cho những bàn thiếu ghế và nếu có những bàn nào thừa ghế thì sẽ lấy bớt đi cho 
vừa đủ.
Yêu cầu: Bạn hãy giúp nhân viên lễ tân tìm phương án bố trí khách ngồi sao cho tổng số các 
ghế kê thêm và các ghế lấy bớt là ít nhất.
Dữ liệu vào: Từ tệp văn bản GHENGOI.INP gồm 03 dòng:
- Dòng thứ nhất gồm hai số nguyên dương M, N (0 < N < M < 104);
 9
- Dòng thứ hai ghi M số nguyên ai (0 < ai < 10 , i = 1, M);
 9
- Dòng cuối cùng ghi N số bj (0 < bj < 10 , j = 1, ..., N).
Dữ liệu ra: Ghi ra tệp văn bản GHENGOI.OUT gồm duy nhất một số nguyên là số lượng ít 
nhất các ghế đã chuyển ra, chuyển vào của tất cả các bàn.
Ví dụ:
 GHENGOI.INP GHENGOI.OUT
5 4 4
5 6 9 10 7
6 8 3 8
Ràng buộc:
- Sub1: Có 40% test tương ứng 40% số điểm của bài với 0 < N <M < 10 và ai, bj < 10;
 2 4
- Sub2: Có 40% test tương ứng 40% số điểm của bài với 0 < N <M < 10 và ai, bj < 10 ;
 4 9
- Sub3: Có 20% test tương ứng 20% số điểm của bài với 0 < N <M < 10 và ai, bj < 10
Bài 3: (5.0 điểm) Phân tích số
Cho số nguyên dương N. Với mọi giá trị N ta xây dựng hàm f(N) cho số lượng lớn nhất các 
số nguyên tố có tổng bằng N, mỗi số sử dụng một lần (trừ một số nguyên tố nào đó có thể sử 
dụng hai lần nếu cần). Qui ước: f(1) = 1.
Ví dụ: 
x = 5→ f(x) = 2 (5 = 3+2)
x = 7 → f(x) = 3 (7 = 3+2+2)
Yêu cầu: Hãy tìm f(N)?
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
Dữ liệu vào: Từ tệp văn bản PHANTICH.INP gồm nhiều dòng, mỗi dòng ghi một số nguyên 
dương N (N < 103).
Dữ liệu ra: Ghi ra tệp văn bản PHANTICH.OUT gồm nhiều dòng, mỗi dòng tương ứng với 
một dòng của tệp dữ liệu vào thể hiện f(N) tìm được.
Ví dụ:
 PHANTICH.INP PHANTICH.OUT
2 1
44 7
11 3
14 4
34 5
16 4
Ràng buộc:
- Sub1: Có 30% test tương ứng 30% số điểm của bài với N < 10;
- Sub2: Có 50% test tương ứng 50% số điểm của bài với N < 102;
- Sub3: Có 20% test tương ứng 20% số điểm của bài với N < 103;
Bài 4: (5.0 điểm) Cắm trại
 Nhân kỉ niệm 40 năm ngày thành lập trường, trường THPT Văn Long tổ chức cắm trại 
cho tất cả học sinh trong trường. Ban tổ chức hội trại dựng rất nhiều lều trong sân trường. 
Mỗi lớp được bố trí một lều và lớp trưởng được phân công làm lều trưởng. Còn một số lều 
không có học sinh được Ban tổ chức dùng để cất những vật dụng cần thiết cho đợt cắm trại. 
Mỗi lều có thể đến lều Trung ương bằng cách đi trực tiếp hoặc đi qua một số lều khác. Có 
tổng cộng P đường đi.
 Có đúng 26 lều được đặt tên là từ ‘a' đến ‘z’, lều Trung ương là ‘z’ và theo qui định lều 
này chỉ dành để tập trung lều trưởng khi có hiệu lệnh của Ban tổ chức. Trên bảng theo dõi ở 
lều Trung ương, lều nào có học sinh sẽ được gán tên là chữ in hoa (ví dụ: lều có tên là ‘b’ 
hiện đang có học sinh thì trên bảng theo dõi sẽ được gán tên là ‘B ’).
 Khi có hiệu lệnh từ Ban tổ chức, các lều trưởng sẽ khẩn trương tập trung về lều Trung 
ương bằng các đường đi. Theo qui định của Ban tổ chức, lều trưởng nào tập trung chậm nhất 
thì sẽ bị phạt nên các lều trưởng luôn tìm ra con đường ngắn nhất để về lều Trung ương.
Yêu cầu: Bạn hãy cho biết độ dài đoạn đường ngắn nhất từ các lều trưởng về tới lều Trung 
ương là bao nhiêu khi Ban tổ chức phát hiệu lệnh?
Dữ liệu vào: Từ tệp văn bản CAMTRAI.INP gồm:
- Dòng thứ nhất là số nguyên dương P (1 < P < 325);
- P dòng tiếp theo, mỗi dòng ghi tên của hai lều và một số nguyên dương X (X là khoảng 
cách giữa hai lều). Ba nội dung này nằm trên một dòng được viết cách nhau một khoảng 
trắng. 
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
Dữ liệu ra: Ghi ra tệp văn bản CAMTRAI.OUT gồm một số duy nhất là độ dài đoạn đường 
ngắn nhất từ các lều trưởng về tới lều Trung ương.
Ví dụ:
 CAMTRAI.INP CAMTRAI.OUT
5 5
A h 5
B e 3
C h 8
h z 7
e z 2
Ràng buộc:
- Sub1: Có 30% test tương ứng 30% số điểm của bài với P < 10 và X < 10;
- Sub2: Có 50% test tương ứng 50% số điểm của bài với P < 102 và X < 102;
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với P < 325 và X < 104
 ----------HẾT----------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài 1. (5.0 điểm) gồm có 10 test, mỗi test 0.50 điểm, bộ nhớ 1024 MB
- Sub1: Có 50% test tương ứng 50% số điểm của bài với N < 5 và ai < 10 2 (thời gian tối đa 
cho mỗi test là 1 giây);
- Sub2: Có 30% test tương ứng 30% số điểm của bài với N < 10 và ai < 10 2 (thời gian tối đa 
cho mỗi test là 1 giây);
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N < 15 và ai < 103 (thời gian 
tối đa cho mỗi test là 0.09 giây).
 TEST QUATANG.INP QUATANG.OUT
 1 6
 2
 5 7 8 4 3 15
 5
 2 18
 9 76 85 54 49
 10
Bài 2. (5.0 điểm) gồm có 10 test, mỗi test 0.50 điểm, bộ nhớ 1024 MB
- Sub1: Có 40% test tương ứng 40% số điểm của bài với 0 < N < M < 10 và a i, bj < 10 (thời 
gian tối đa cho mỗi test là 1 giây);
 2 4 
- Sub2: Có 40% test tương ứng 40% số điểm của bài với 0 < N < M < 10 và ai, bj < 10 (thời 
gian tối đa cho mỗi test là 1 giây);
 4 9
- Sub3: Có 20% test tương ứng 20% số điểm của bài với 0 < N < M < 10 và ai, bj <10 (thời 
gian tối đa cho mỗi test là 0.09 giây).
 TEST GHENGOI.INP GHENGOI.OUT
 4 3 2
 1 5 6 8 15
 6 8 3
 4 3 19
 2 50 60 80 150
 60 80 31
 10
Bài 3. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, bộ nhớ 1024 MB
- Sub1: Có 30% test tương ứng 30% số điểm của bài với N < 10 (thời gian tối đa cho mỗi 
test là 1 giây);
- Sub2: Có 50% test tương ứng 50% số điểm của bài với N < 10 2 (thời gian tối đa cho mỗi 
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
test là 1 giây);
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N < 103 (thời gian tối đa cho 
mỗi test là 0.09 giây).
 TEST PHANTICH.INP PHANTICH.OUT
 1 1 1
 5 2
 4 2
 9 3
 2
 10 3
 2 1
 20
Bài 4. (5.0 điểm) gồm có 20 test, mỗi test 0.25 điểm, bộ nhớ 1024 MB
- Sub1: Có 30% test tương ứng 30% số điểm của bài với P < 10 và X < 10 (thời gian tối đa 
cho mỗi test là 1 giây)
- Sub2: Có 50% test tương ứng 50% số điểm của bài với P < 10 2 và X < 102 (thời gian tối đa 
cho mỗi test là 1 giây);
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với P < 325 và X < 10 4 (thời 
gian tối đa cho mỗi test là 0.09 giây).
 TEST CAMTRAI.INP CAMTRAI.OUT
 9 8
 G z 10
 F c 5
 H x 6
 s v 7
 1
 s y 2
 c z 3
 b t 1
 p u 5
 j w 6
 6 10
 g z 2
 B u 1
 2
 d g 4
 e v 7
 A d 4
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 (Kèm đáp án) - De-Thi.com
 K p 5
20
 De-Thi.com