Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết)

 Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐỀ SỐ 6
TRƯỜNG THPT TRIỆU SƠN 5 ĐỀ THI HỌC SINH GIỎI CẤP TRƯỜNG
 NĂM HỌC 
 Môn thi:TIN HỌC – KHỐI 11
 ĐỀ CHÍNH THỨC Thời gian: 180 phút(không kể thời gian giao đề)
 (Đề thi gồm có 3 trang)
Tổng quan bài thi:
Bài Tên bài File chương trình File dữ liệu File kết quả
1 Xoá kí tự trong số nguyên BAI1.PAS SONGUYEN.INP SONGUYEN.OUT
2 Xóa kí tự trong xâu BAI2.PAS KITU.INP KITU.OUT
3 T ìm xâu dài nhất BAI3.PAS XAU.INP XAU.OUT
4 Sự xuất hiện của các kí tự BAI4.PAS KIEMTRA.INP KIEMTRA.OUT
5 Tìm dãy con BAI5.PAS DAYCON.INP DAYCON.OUT
Hãy lập trình giải các bài toán sau:
Câu 1(5 điểm): Nhập vào số nguyên N và xóa đi k kí tự để N là nhỏ nhất
Dữ liệu vào : Từ tệp vă bản SONGUYEN.INP chứa số nguyên N và K
Dữ liệu ra: Ghi kết quả vào tệp SONGUYEN.OUT số nguyên N nhỏ nhất sau khi xóa k kí tự
 Ví dụ:
 SONGUYEN.INP SONGUYEN.OUT
 124512 1212
 2
Câu 2(5 điểm): Nhập vào một xâu, nếu tính 
từ trái sang phải thì kí tự ? là dấu hiệu xóa đi một kí tự đứng ngay trước nó nếu có. Sau đó in ra 
màn hình xâu đã chỉnh sửa
Dữ liệu vào:Từ tệp văn bản KITU.INP gồm một xâu
Dữ liệu ra: Ghi kết quả ra tệp văn bản KITU.OUT là xau sau khi xóa
Ví dụ: KITU.INP KITU.OUT
 Ho1?c sin12?a???nh Hoc sinh
Câu 3(4 điểm): Nhập vào một dãy gồm N xâu. Hãy đưa ra màn hình xâu nào có độ dài lớn nhất.
Dữ liệu vào: từ tệp văn bản XAU.INP gồm:
 - Dòng đầu là một số nguyên N
 - N dòng tiếp theo mỗi dòng chứa một xâu
Dữ liệu ra: Xâu có độ dài nhiều nhất ghi vào tệp văn bản XAU.OUT
 XAU.INP XAU.OUT
 3 Hbghjghjghj
 FHDFHD
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
Ví dụ: Hbghjghjghj
 Hgf
Câu 4(3 điểm): Cho một dãy số nguyên gồm N số và một số nguyên K. Hãy cho biết K có trong 
dãy số đó hay không? Nếu có nó xuất hiện bao nhiêu lần?
Dữ liệu vào: Từ tệp văn bản KIEMTRA.INP gồm:
 - Dòng thứ nhất là N
 - Dòng thứ hai là dãy N phần tử, mỗi phần tử cách nhau một dấu cách
 - Dòng thứ 3 là số nguyên K
Dữ liệu ra: Số lần xuất hiện của K có trong dãy số ghi vào tệp KIEMTRA.OUT
Ví dụ: 
 KIEMTRA.INP KIEMTRA.OUT
 4 1
 12 45 78 2 
 12
 4 0
 45 58 5 6 
 12
Câu 5(3 điểm): Cho một mảng gồm N phần tử. Hãy tìm dãy con gồm M phần tử (M<N) Sao cho dãy con 
này có tổng lớn nhất
Dữ liệu vào: Từ tệp văn bản DAYCON.INP gồm:
 - Dòng đầu là N
 - Dòng thứ hai là N phần tử
 - Dòng thứ 3 là M
Dữ liệu ra: Dãy con có tổng lớn nhất ghi vào tệp DAYCON.OUT
Ví dụ
 DAYCON.INP DAYCON.OUT
 5 78 45 26
 1 78 45 26 3
 3
 ...................Hết.....................
 (Cán bộ coi thi không giải thích gì thêm)
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐÁP ÁN
Câu Nội dung Điểm
 Kiểm tra chương trình với 5 test tương ứng với 5 số N. 5điểm
 - Mỗi test đúng ứng . 1điểm
 - Chương trình:
 Program bai1;
 Var t1,t2:text;
 N,i,j,k:int64;
 St: ansistring;
1 Kt:b oolean;
 Begin
 Assign(t1,’SONGUYEN.INP’);
 Assign(t2,’SONGUYEN.OUT’);
 Reset(t1);
 Rewrite(t2);
 Readln(n);
 Str(n,st);
 Readln(k);
 For i:=1 to k do
 Begin
 Kt:=true;
 For j:=1 to length(st)-1 do if st[j] >st[j+1] then
 Begin
 Delete(st,j,1);
 Kt:=false;
 Break;
 End;
 If kt then delete(st,length(st), 1);
 End;
 While (st[1] = ‘0’) and (length(st)>1) do delete(st,1,1);
 Writeln(st);
 Close(t1); close(t2);
 End.
 Kiểm tra chương trình với 5 test ứng với 5 xâu 5điểm
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 - Mỗi test đúng ứng với 1điểm
 - Chương trình:
 Program bai1;
 Var t1,t2:text;
 a: string;
 i:integer;
2 Begin
 Assign(t1,’KITU.INP’);
 Assign(t2,’KITU.OUT’);
 Reset(t1);
 Rewrite(t2);
 Readln(A);
 For i:=1 to length(a) do if a[i]= ‘? ‘ then delete(a,i+1,1);
 Write(a);
 Readln;
 End.
 Kiểm tra chương trình với 4 test ứng với 4 dữ liệu vào 4điểm
 - Mỗi test đúng ứng với 1điểm
 - Chương trình:
 Program bai1;
 Var t1,t2:text;
 A:string;
3 Max: array[1..10000] of integer;
 N,i,j,lonnhat:integer;
 Begin
 Assign(t1,’XAU.INP’);
 Assign(t2,’XAU.OUT’);
 Reset(t1);
 Rewrite(t2);
 Readln(N);
 For i:=1 to N do
 Begin
 Readln(a);
 Max[i]:=length(a);
 End;
 Lonnhat:=max[1];
 For i:=2 to N do if max[i]>lonnhat then lonhat:=max;
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 For j:=1 to lonnhat write(a);
 Readln;
 End.
 Kiểm tra chương trình với 3 test ứng với 4 xâu 3điểm
 - Mỗi test đúng ứng với 1điểm
 - Chương trình:
4 Program bai1;
 Var t1,t2:text;
 a: array[1..10000] of int64;
 i,k,n:integer;
 Begin
 Assign(t1,’KIEMTRA.INP’);
 Assign(t2,’KIEMTRA. OUT’);
 Reset(t1);
 Rewrite(t2);
 Readln(n); 
 For i:=1 to n readln a[i];
 Readln(k);
 For i:=1 to n do if a [i] =k then inc(dem);
 Write(dem);
 Readln;
 End.
 Kiểm tra chương trình với 3 test ứng với 3 dữ liệu vào 3điểm
 - Mỗi test đúng ứng với 1điểm
 - Chương trình:
 Program bai1;
 Var t1,t2:text;
 a: array[1..10000] of integer;
 i,j n,m ,k,s,max:integer;
 Begin
 Assign(t1,’DAYCON.INP’);
 Assign(t2,’DAYCON.OUT’);
 Reset(t1);
 Rewrite(t2);
5 readln(n);
 For i:=1 to n do readln(a[i]);
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 Readln(m);
 Max:=0;
 K:=1
 For i:=1 to m do max:=max+a[i];
 For i:=2 to n-m+1 do
 Begin 
 S:=0;
 For j:=i to i+m-1 do s:= s+a[i];
 If s>max then 
 Begin 
 Max:=s;
 K:=i;
 End;
 End;
 For i:=k to k+m-1 do write(a[i]);
 Readln;
 End.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐỀ SỐ 7
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI CẤP TRƯỜNG 
 QUẢNG NAM Môn thi : TIN HỌC - LỚP 11
 Thời gian : 150 phút (không kể thời gian giao đề)
 ĐỀ CHÍNH THỨC Ngày thi : 
 (Đề thi có 04 trang)
 TỔNG QUAN ĐỀ THI TỔNG QUAN ĐỀ BÀI
 File chương Thời 
 Bài Tên bài File dữ liệu vào File kết quả
 trình gian
 Tổng bình phương 
 1 SQUARE.* SQUARE.INP SQUARE.OUT 1 s
 các chữ số
 Ước chung lớn 
 2 MAXGCD.* MAXGCD.INP MAXGCD.OUT 1 s
 nhất
 3 Sơn gạch SONGACH.* SONGACH.INP SONGACH.OUT 1 s
 4 Thỏ và cà rốt RABBIT.* RABBIT.INP RABBIT.OUT 1 s
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à Pascal 
hoặc C++.
Hãy lập trình giải các bài toán sau:
Bài 1. Tổng bình phương các chữ số (5 điểm) 
Cho một số tự nhiên N (N ≤ 1064).
Yêu cầu: Hãy viết chương trình tính tổng bình phương các chữ số của số tự nhiên đã cho.
Ví dụ: N=12. Tổng bình phương các chữ số của nó là 5 = 12 + 22.
Dữ liệu vào: Từ tệp văn bản SQUARE.INP gồm một số N.
Kết quả: Ghi ra tệp văn bản SQUARE.OUT gồm một số duy nhất tìm được.
Ví dụ:
 SQUARE.INP SQUARE.OUT
 12 5
Ràng buộc:
• Có 60% test tương ứng 60% số điểm của bài với N ≤ 106;
• Có 20% test tương ứng 20% số điểm của bài với N ≤ 1018;
• Có 20% test khác tương ứng với 20% số điểm còn lại của bài với N ≤ 1064.
Bài 2. Ước chung lớn nhất (5 điểm)
Minh trong lúc rảnh rỗi đã nghĩ ra một nhiệm vụ cho bản thân để thư giãn một chút. Anh ta chọn hai số 
nguyên A và B rồi tính ước số chung lớn nhất của các số nguyên "A giai thừa" và "B giai thừa". Minh 
muốn tìm ra GCD (A!, B!). Ai cũng biết rằng giai thừa của số nguyên x là tích của tất cả các số nguyên 
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
dương nhỏ hơn hoặc bằng x. Như vậy x! = 1*2*3*...*(x - 1)*x. Ví dụ 4! = 1*2*3*4 = 24. Nhắc lại rằng 
GCD (x, y) là số nguyên dương q lớn nhất chia (không có dư) cho cả x và y.
Yêu cầu: Tìm ước chung lớn nhất của A! và B! .
Dữ liệu vào: Từ tệp văn bản MAXGCD.INP gồm: 
• Một dòng chứa hai số nguyên A và B (1 ≤ A, B < 105). Mỗi số cách nhau một khoảng trắng.
Kết quả : Ghi ra tệp văn bản MAXGCD.OUT gồm:
• Một số nguyên dương là ước số chung lớn nhất của các số nguyên A! và B !. Do ước chung lớn 
nhất của A! và B! có thể rất lớn nên ghi kết quả chia dư cho 109 + 7.
Ví dụ:
 MAXGCD.INP MAXGCD.OUT
 4 3 6
Ràng buộc:
• Có 50% test tương ứng 50% số điểm của bài với 1 ≤ A, B < 105, min (A, B) ≤ 12;
• Có 30% test tương ứng 30% số điểm của bài với A, B ≤ 100;
• Có 20% test khác tương ứng với 20% số điểm còn lại của bài với A, B < 105.
Bài 3. Sơn gạch (5 điểm) 
Có n viên gạch xếp thành hàng trên mặt đất. Minh có m thùng sơn khác màu nhau. Minh sẽ sơn n viên 
gạch với m màu đó. Minh muốn sơn sao cho có k viên gạch đặc biệt mà màu của viên gạch đó khác với 
màu của các viên gạch ở phía bên trái của nó (không tính viên gạch đầu tiên).
Yêu cầu: Đếm xem có bao nhiêu cách sơn gạch thỏa mãn yêu cầu của Minh? Hai cách sơn được gọi là 
khác nhau nếu có ít nhất 1 viên gạch được sơn khác màu với cách còn lại. Đáp án có thể là một số khá lớn 
nên bạn có thể ghi ra kết quả là số cách chia dư cho 998 244 353.
Dữ liệu vào: Từ tệp văn bản SONGACH.INP gồm
• Một dòng duy nhất chứa ba số nguyên n, m và k (1 ≤ n, m ≤ 2000, 0 ≤ k ≤ n-1) – số viên gạch, số 
màu và số viên gạch đặc biệt.
Kết quả: Ghi ra tệp văn bản SONGACH.OUT gồm một số duy nhất là số cách sơn thỏa mãn chia dư cho 
998 244 353.
Ví dụ:
 SONGACH.INP SONGACH.OUT
 3 3 0 3
 SONGACH.INP SONGACH.OUT
 3 2 1 4
Ràng buộc:
• Có 30% test tương ứng 30% số điểm của bài với 1 ≤ n, m ≤ 2000, k = 0;
• Có 30% test tương ứng 30% số điểm của bài với 1 ≤ n, m, k ≤ 10;
• Có 40% test khác tương ứng với 40% số điểm còn lại của bài với 1 ≤ n, m ≤ 2000, 0<k ≤ n-1).
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
Bài 4. Thỏ và cà rốt (5 điểm)
Một lưới NxN ô vuông gồm có N hàng và N cột. Các hàng được đánh số từ 1 đến N (từ trên xuống) và 
các cột đánh số từ 1 đến N( từ trái qua). Một con Thỏ xuất phát từ ô (1, 1) và muốn di chuyển đến ô có 
đặt củ cà rốt là ô (X, Y). Người ta đặt các chướng ngại vật để Thỏ không được đi qua ở các ô đánh số 1; 
các ô không đặt chướng ngại vật được đánh số 0 và Thỏ có thể đi qua các ô này. Từ ô đang đứng, Thỏ chỉ 
có thể di chuyển đến 3 ô kề cạnh: một ô bên dưới và hai ô ở hai bên. Thỏ không thể di chuyển ra ngoài 
đường biên của lưới.
Yêu cầu: Tìm đường đi ngắn nhất (đi qua ít ô nhất) của Thỏ.
Dữ liệu vào: Từ tệp văn bản RABBIT.INP gồm: 
• Dòng đầu ghi số 3 số nguyên dương: N, X, Y (N 1000; X N; Y N ).
• N dòng tiếp theo mỗi dòng ghi N số nguyên 0 hoặc 1, mỗi số cách nhau một khoảng trắng.
(Riêng số đầu tiên của dòng thứ nhất và số thứ Y của dòng X ghi số 0 của lưới).
Kết quả : Ghi ra tệp văn bản RABBIT.OUT gồm:
• Một số nguyên dương là số các ô mà Thỏ đi qua (kể cả ô xuất phát và ô đích). Trong trường hợp 
Thỏ không di chuyển được đến ô đặt củ cà rốt thì phải ghi số 0.
Ví dụ:
 RABBIT.INP RABBIT.OUT
 5 3 4 6
 0 0 0 0 0 
 0 1 1 1 0
 0 0 0 0 0
 0 0 0 0 0
 0 0 1 0 0
 RABBIT.INP RABBIT.OUT
 5 3 4 0
 0 0 1 0 0 
 1 1 1 1 0
 0 1 0 0 0
 0 0 0 0 0
 0 0 1 0 0
Ràng buộc:
• Có 10% test tương ứng 10% số điểm của bài với N ≤ 10 và trong lưới duy nhất có một chướng 
ngại vật ô (i, j) sao cho i ≤ X; j ≤ Y ;
• Có 40% test tương ứng 40% số điểm của bài với N ≤ 10;
• Có 40% test tương ứng 40% số điểm của bài với N ≤ 100;
• Có 10% test khác tương ứng với 10% số điểm còn lại của bài với N ≤ 103.
 ---------------Hết---------------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 11 cấp Trường (Có giải chi tiết) - De-Thi.com
 ĐÁP ÁN
Chấm bài bằng chương trình chấm Themis mới nhất (có kèm theo) cài đặt trên hệ điều hành Windows 10 
(64bit) trở lên, các tests đã cài đặt sẵn cấu hình chấm bài.
Bài 1: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
 TEST SUMN.INP SUMN.OUT
 1 1111 4
 ... ... ...
 20
Bài 2: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
 TEST MAXGCD.INP MAXGCD.OUT
 1 10 3996 3628800
 ... ... ...
 20
Bài 3: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
 TEST SONGACH.INP SONGACH.OUT
 1 3 3 2 12
 ... ... ...
 20
Bài 4: (5 điểm) Có 25 tests, mỗi TEST đúng được 0.2 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. 
 TEST SUBSTR.INP SUBSTR.OUT
 7 3 5
 0 0 0 0 0 0 0 
 1 1 1 1 1 1 0 
 0 0 0 0 0 0 0 
 1 11
 1 0 1 0 0 0 0 
 1 1 0 1 0 1 1 
 1 0 1 1 0 1 1 
 0 1 1 1 1 0 1
 ... ... ...
 25
 ------------------------------------HẾT----------------------------------
 De-Thi.com