Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết)

Nội dung text: Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết)

1. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn ĐÁP ÁN Câu 1 (4 điểm) Đong gạo: n = int(input()) mi = int(le9) x=0 while x*5 <=n: if (n-5*x)%3==0: y = (n-5*x)//3 mi = min(mi, (x+y)) x+=l print(-l if mi =le9 else mi) Câu 2 (4 điểm) Trâu và cỏ: test = int(input()) for_in range (test): dem = 0 a. b = map(int. Input ().split()) for td in range (a+1): tg = (9*a - 3*b + 6*td)//8 tn = a - td - tg if (tn>=0) and (tg>=0) \ and (td*5 + tn*3//3 == b) and (tg%3 ==0): dem = dem + 1 print(dem) for td in range (a+1): tg = (9*a - 3*b + 6*td)//8 tn = a – td – tg if (tn>=0) and (tg>=0)\ and (tg*5 + tn*3 + tg//3 ==b) and (tg%3=0): print(td.tn.tg) Câu 3 (4 điểm): Kí tự duy nhất đầu tiên q = int(input()) while q: q-=l s= input() pos= -1 cnt=[0]*26 for c in s: DeThi.edu.vn
2. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn cnt[ord(c)-ord(‘a’)] +=1 for i in range(len(s)): if cnt[ord(s[i])-ofd(‘a’) ==l: pos = i+1 break print(pos) Câu 5 (4 điểm) Chơi game n = int(input()) a = list (map(int. input(). Split()) b = list(map(int. input(). Split()) flag = [0] *101 for i in range(l. len(a)): flag[a[i]] =1 for i in range(l. len(b)): flag[b[i]] =1 ok = true for i in range(l. n+1): if not flag[i]: ok = false break print(‘YES’ if ok else ‘NO’) DeThi.edu.vn
3. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 3 SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH TỈNH QUẢNG NAM THPT - ĐỢT 2 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 đề) Tổng quan đề thi Bài Tên bài File chương trình File dữ liệu File kết quả 1 MEMORY MEMORY.* MEMORY.INP MEMORY.OUT 2 TEST TEST.* TEST.INP TEST.OUT Mã đề: 001 3 PROJECT PROJECT.* PROJECT.INP PROJECT.OUT Dấu * được thay thế bởi CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++ hoặc PYTHON. Bài 1. MEMORY (6 điểm) Năm 2025, Trường THPT HV kỉ niệm 15 năm thành lập trường kết hợp tổ chức cắm trại vào dịp ngày thành lập Đoàn thanh niên 26 tháng 3. Đây là lễ hội vô cùng quan trọng và lớn đối với trường, nên đã có rất nhiều khách mời là lãnh đạo các ban ngành, giáo viên – nhân viên đã và đang làm việc tại trường, cựu học sinh và học sinh đang học. Để tăng thêm phần ấn tượng cũng như tỏ lòng cảm ơn đối với khách mời, nhà trường có tổ chức trao quà lưu niệm cho một số cá nhân, tập thể đã có đóng góp lớn cho quá trình phát triển của nhà trường. Danh sách là tên các cá nhân, tập thể được lưu trong chuỗi kí tự liên tiếp. Số lượng phần quà sẽ thay đổi liên tục do số tiền tài trợ cho chương trình có sự thay đổi theo từng ngày. Để không bị động về kinh phí trao quà, nhà trường đã giao cho Ban chấp hành Đoàn trường lập danh sách số lượng lớn nhất các cá nhân, hoặc tập thể có thể được nhận quà trong đoạn danh sách liên tiếp lấy từ danh sách ban đầu nhà trường đưa ra. Số lượng các cá nhân, tập thể được nhận quà tương ứng là số lượng chuỗi khác rỗng khác nhau có thể có sau khi bỏ một đoạn ký tự ở đầu hoặc cuối chuỗi (có thể không bỏ đoạn ký tự nào). Yêu cầu: Bạn hãy viết chương trình giúp Ban chấp hành Đoàn trường đưa ra số lượng các cá nhân, hoặc tập thể có thể được nhận quà từ đoạn danh sách lấy ra. Dữ liệu: Vào từ file văn bản MEMORY.INP gồm: - Dòng đầu tiên chứa 2 số nguyên , lần lượt là độ dài danh sách ban đầu (1 ≤ M ≤ 2 x 105) và số lượng đoạn danh sách con (1 ≤ T ≤ 2 x 105). - Dòng tiếp theo chứa một chuỗi 푆có độ dài bao gồm các chữ cái Latin thường thể hiện tên của các cá nhân hoặc tập thể. DeThi.edu.vn
4. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn - T dòng tiếp theo, dòng thứ i (1 ≤ i ≤ T) gồm 2 số nguyên li và ri thể hiện một danh sách con được trích từ danh sách ban đầu từ vị trí 푙푖 đến vị trí 푖 (1 ≤ li ≤ ri ≤ M). Lưu ý: Các số trên cùng một hàng cách nhau bởi một dấu cách. Kết quả: Ghi ra file văn bản MEMORY.OUT gồm T dòng, dòng thứ i là một số nguyên thể hiện số lượng các cá nhân, tập thể có thể được nhận quà tương ứng với truy vấn thứ i. Ví dụ: MEMORY.INP MEMORY.OUT Giải thích 15 4 9 - Trong truy vấn đầu tiên, ta có chuỗi ttcn. ttcnphattrienmt 15 - Có 9 chuỗi khác rỗng khác nhau được tạo từ 1 4 6 chuỗi ttcn gồm: t, c, n, tt, tc, cn, ttc, tcn, ttcn. 2 6 20 13 15 6 11 Ràng buộc: - 20% test có ràng buộc M ≤ 60 , T ≤ 60. - 30% test có ràng buộc M ≤ 3 x 102 , T ≤ 3 x 102. - 30% test có ràng buộc M ≤ 3 x 103 , T ≤ 3 x 103. - 20% test không có có ràng buộc gì thêm. Bài 2. TEST (7 điểm) Để nâng cao thành tích huy chương trong cuộc thi thể thao toàn quốc vào quý 4 sắp tới, trung tâm huấn luyện XYZ thường xuyên tổ chức nhiều lần thi khảo sát theo quý để nắm rõ thực trạng của các vận động viên nhằm đưa ra phương pháp tập luyện phù hợp. Sau N lần khảo sát, huấn luyện viên đã có được thành tích của mỗi vận động viên theo 3 quý tương ứng với 3 dãy số nguyên. Qua đó huấn luyện viên đã chọn ra các thành tích chung của 3 quý và giá trị tích lớn nhất của các thành tích. Tuy nhiên vì mỗi quý, trung tâm tổ chức khảo sát rất nhiều lần, nên nếu làm thủ công trên giấy sẽ mất nhiều thời gian. Yêu cầu: Bạn hãy viết chương trình giúp trung tâm huấn luyện đưa ra giá trị lớn nhất của tích các thành tích chung theo thứ tự khảo sát. Dữ liệu: Vào từ file văn bản TEST.INP gồm: - Dòng đầu tiên gồm số nguyên N (1 ≤ N ≤ 100); - Dòng tiếp theo gồm N số nguyên ai (1 ≤ ai ≤ 100), là thành tích khảo sát ở quý 1; - Dòng tiếp theo gồm N số nguyên bi (1 ≤ bi ≤ 100), là thành tích khảo sát ở quý 2; - Dòng tiếp theo gồm N số nguyên ci (1 ≤ ci ≤ 100), là thành tích khảo sát ở quý 3. Lưu ý: Các số trên cùng một hàng cách nhau bởi một dấu cách. Kết quả: Ghi ra file văn bản TEST.OUT gồm một số nguyên là giá trị lớn nhất của tích các thành tích chung trong 3 quý theo yêu cầu. Ví dụ: DeThi.edu.vn
5. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn TEST.INP TEST.OUT 5 27 1 3 5 7 9 1 3 9 4 7 1 3 4 9 8 2 0 1 4 2 2 5 7 5 9 1 9 2 2 1 1 2 2 1 9 1 2 2 1 9 Ràng buộc: - 20% test tương ứng với N ≤ 5. - 50 % test có tích các thành tích chung không quá 1018. - 30% test còn lại không có ràng buộc gì thêm. Bài 3. PROJECT (7 điểm) Anpha là đất nước có nhiều thành phố xinh đẹp, người dân trên đất nước này nổi tiếng chăm chỉ, thân thiện. Kinh tế của nước này phát triển mạnh, thu nhập bình quân đầu người của nước này rất cao. Thu nhập chính ở quốc gia này chủ yếu là sản xuất công nghiệp, thương mại, dịch vụ và du lịch. Trận đại dịch COVID vừa qua đã ảnh hưởng rất lớn đến nền kinh tế đất nước, thu nhập của người dân sụt giảm đáng kể, tình trạng thất nghiệp gia tăng. Để lấy lại đà tăng trưởng kinh tế sau đại dịch tổng thống nước này muốn chấn hưng lại nền kinh tế đất nước bằng cách xây dựng thêm một số trung tâm kinh tế trọng điểm. Cả nước Anpha hiện nay có tổng cộng N thành phố lớn nhỏ được đánh số tuần tự từ 1 đến N. Giữa N thành phố này là một mạng lưới gồm M đường đi hai chiều, mỗi tuyến đường nối 2 trong N thành phố sao cho không có 2 thành phố nào được nối bởi quá 1 tuyến đường. Trong N thành phố này thì thành phố 1 và thành phố N là 2 trung tâm kinh tế lớn nhất cả nước và hệ thống đường đảm bảo luôn có ít nhất một cách đi từ thành phố 1 đến thành phố N. Tại hai thành phố trung tâm này, tình hình kinh tế có nhiều khả quan và khởi sắc trở lại, còn các thành phố khác thì gặp rất nhiều khó khăn. Vì vậy tổng thống nước Anpha đang có dự án là chọn ra thêm một thành phố nữa để đầu tư thành một trung tâm kinh tế thứ ba để mở rộng và phát triển. Trong quá trình thực hiện dự án, thành phố này sẽ tạm ngưng mọi hoạt động thường nhật, cũng như mọi luồng lưu thông ra vào để tiến hành nâng cấp cơ sở hạ DeThi.edu.vn
6. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn tầng. Nhưng trong thời gian sửa chữa ấy, phải bảo đảm đường đi ngắn nhất từ thành phố 1 đến thành phố N không bị thay đổi, nếu không nền kinh tế quốc gia sẽ bị trì trệ. Yêu cầu: Là một học sinh giỏi Tin học, em hãy giúp tổng thống nước Anpha đếm số lượng các thành phố có thể chọn làm trung tâm kinh tế thứ ba sao cho các thành phố được chọn này thỏa mãn các điều kiện ở trên. Dữ liệu: Vào từ file văn bản PROJECT.INP gồm: - Dòng đầu tiên ghi 2 số nguyên dương N và M là số thành phố và số tuyến đường. - Dòng thứ i trong số M dòng tiếp theo ghi 3 số nguyên dương x i, yi và di (1 ≤ di ≤ 1000) với ý nghĩa tuyến đường thứ i có độ dài di và nối giữa 2 thành phố xi, yi. Lưu ý: Các số trên cùng một hàng cách nhau bởi một dấu cách. Kết quả: Ghi ra file văn bản PROJECT.OUT như sau: - Dòng đầu tiên ghi số tự nhiên S là số lượng các thành phố có thể chọn làm trung tâm kinh tế thứ ba. - S dòng tiếp theo, mỗi dòng ghi 1 số nguyên dương là số thứ tự của thành phố được chọn. Các thành phố này được in ra theo thứ tự tăng dần. Ví dụ: PROJECT.INP PROJECT.OUT 6 6 2 1 2 1 4 2 3 5 5 3 6 2 1 4 10 4 5 15 5 6 10 Ràng buộc - 40% số test có ràng buộc 2 ≤ N ≤ 300, 1 ≤ M ≤ 1000. - 60% số test có ràng buộc 300 < N ≤ 30000, 1 ≤ M ≤ 100000. ----------HẾT---------- DeThi.edu.vn
7. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn ĐÁP ÁN Bài 1. (6.0 điểm) MEMORY: gồm có 50 test, mỗi test 0,12 điểm, thời gian 1 giây, bộ nhớ 1024 MB - 20% test có ràng buộc ≤ 60, ≤ 60. - 30% test có ràng buộc ≤ 3 × 102, ≤ 3 × 102. - 30% test có ràng buộc ≤ 3 × 103, ≤ 3 × 103. - 20% test không có có ràng buộc gì thêm. Bài 2. (7.0 điểm) TEST: gồm có 20 test, mỗi test 0.35 điểm, thời gian 1 giây, bộ nhớ 1024 MB - 20% test tương ứng với N ≤ 5. - 50 % test có tích các thành tích chung không quá 1018. - 30% test còn lại không có ràng buộc gì thêm. Bài 3. (7.0 điểm) PROJECT: gồm có 40 test, mỗi test 0,175 điểm, thời gian 1 giây, bộ nhớ 1024 MB - 40% số test có ràng buộc 2 ≤ N ≤ 300, 1 ≤ M ≤ 1000. - 60% số test có ràng buộc 300 < N ≤ 30000, 1 ≤ M ≤ 100000. DeThi.edu.vn
8. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 4 SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI OLYMPIC TRUYỀN THỐNG 30 THÀNH PHỐ HỒ CHÍ MINH THÁNG 4 LẦN THỨ XXIX TRƯỜNG THPT CHUYÊN MÔN: TIN HỌC – Khối: 11 LÊ HỒNG PHONG Thời gian: 180 phút (không kể thời gian giao đề) Tổng quan về đề thi Bài Tên bài File chưong trình File dữ liệu File kết quả 1 Đường đi trên ma trận MATRIX3.* MATRIX3.INP MATRIX3.OUT 2 Giải mã xâu KSTRING.* KSTRING.INP KSTRING.OUT 3 Thuê phòng họp XGRAPH.* XGRAPH.INP XGRAPH.OUT Dấu * 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 hay C++ Bài 1. Đường đi trên ma trận (6 điểm) An đang chơi một trò chơi, màn hình trò chơi là hình chữ nhật được chia làm n*m ô vuông đơn vị (n dòng và m cột). Mỗi ô vuông được đặt một phần thường, phần thưởng ở ô vuông nằm trên dòng thứ i từ trên xuống và cột thứ j từ trái sang có giá trị là ữij. Một nhân vật đang đứng ở ô trái trên (vị trí dòng 1, cột 1), cần phải di chuyển tới ô phải dưới của màn hình (vị trí dòng n, cột m). Mỗi bước, An có thể điều khiển nhân vật đi xuống dưới một đơn vị hoặc sang phải một đơn vị, nhưng không được phép đi xuống ba lần liên tiếp. Lưu ý, việc đi sang phải nhiều làn liên tiếp là không bị giới hạn. Yêu cầu: Hãy giúp An tìm cách điều khiển nhân vật sao cho tổng giá trị phần thường ở những ô mà nhân vật đi qua (bao gồm cả ô xuất phát và ô kết thúc) là lớn nhất có thể. Đưa ra tổng giá trị đó. Dữ liệu: Vào từ file văn bản MATRIX3.INP: - Dòng đầu tiên chứa hai số nguyên dương n và m. - n dòng tiếp theo, mỗi dòng chứa m số nguyên dương. Trên dòng thứ i, số thứ j là aij. Dữ liệu bảo đảm luôn tồn tại một cách di chuyển hợp lệ từ ô trái trên tới ô phải dưới. Kết quả: Ghi ra file văn bản MATRIX3.OƯT: Ghi một số nguyên dương duy nhất là tồng giá trị phần thưởng lớn nhất tìm được. Ví dụ: MATRIX3.INP MATRIX3.OUT GIẢI THÍCH 43 16 An có thể điều khiển nhân vật: 1 1 1 Đi xuống, đi xuống, sang phải, 5 1 1 đi xuống, sang phài. 5 1 2 3 3 1 DeThi.edu.vn
9. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn Ràng buộc: 5 - Trong tất cả các test: 1≤ n, m ≤ 2025; 1≤ aij ≤ 10 . - Có 25% số test với n,m ≤ 10; - Có 30% số test với n ≤ 3; - Có 45% số test với ràng buộc gốc. Bài 2. Giải mã xâu (7 điểm) Bình rất đam mê khảo cổ học. Anh vừa phát hiện một từ điển cổ, sau khi nghiên cứu Bình đã tìm ra một vài quy tắc của nó như sau: - Từ điển chi sử dụng k loại ký tự, có thể được Bình biểu diễn bằng k chữ cái đầu tiên frong bảng chữ cái Latin in thường. - Mỗi từ trong từ điển đều có độ dài bằng đúng k và chứa các chữ cái khác nhau. Nói cách khác, mỗi từ đều là một hoán vị của k chữ cái. - Mỗi chữ cái chi có thể đứng ở một số vị trí nhất định trên từ. Bình biểu diễn quy tắc này bằng một ma trận c kích thước kxk. Giá trị của Cij bằng 1 hoặc 0 tưorng ứng là ký tự thứ ỉ trong bảng chữ cái được phép xuất hiện ở vị trí j trên từ hoặc không. Từ nào thoả mãn cả ba quy tắc trên thì đều có trong từ điển. Bình sẽ sử dụng từ điển này để giải mã một thông điệp mà anh vừa tìm được. Thông điệp đã lâu đời nên có thê có một số vị trí bị mờ. Bình biêu diễn thông điệp bằng một xâu 5 chi chứa các ký tự Latin in thường và dấu * (dấu * đại diện cho các vị trí bị mờ). Để giải mã thông điệp, anh đã thử thay mỗi dấu * bằng một ký tự (các dấu * không nhất thiết được thay bằng các ký tự giống nhau), sau đó xoá đi một số ký tự trên 5 vậ giữ nguyên thứ tự các ký tự còn lại (có thể không xoá ký tự nào). Nếu xâu thu được là một từ trong từ điển thì Bình đã thu được một kết quả giải mã. Yêu cầu: Hãy tính xem Bình có thể thu được bao nhiêu kết quả giải mã khác nhau. Tức là đếm xem trong từ điển có bao nhiêu từ là xâu con (không cần liên tiếp) của s, với dấu * đại diện cho ký tự tuỳ ý. Dữ liệu: Vào từ file văn bản KSTRING.INP: - Dòng đầu tiên chứa số nguyên dương k. - k dòng tiếp theo, mỗi dòng chứa k số nguyên, ở trên dòng thứ i, số thứ j là Cụ. - Dòng tiếp theo chứa xâu s. Kết quả: Ghi ra file văn bàn KSTRING.OUT: Ghi một số nguyên duy nhất là số kết quả giải mã khác nhau mà Bình có thể thu được. Ví dụ: KSTRING.INP KSTRING.OUT GIẢI THÍCH 3 3 Chữ cái b không thể xuất hiện ở vị trí 1 trên từ 1 1 1 0 1 1 (trong ma trận, C21 = 0). 1 1 1 ad*a* Từ điển có 4 từ: abc, acb, cab, cba. Trong đó DeThi.edu.vn
10. Tuyển tập 11 Đề thi HSG môn Tin học Lớp 11 (Có đáp án chi tiết) - DeThi.edu.vn có 3 từ có thể là kết quà giải mã: abc, acb, cab. 4 4 Chữ cái a không thể xuất hiện ờ vị trí 3 trên 110 1 1111 00 11 từ. (C13 = 0) 1110 Chữ cái c không thể xuất hiện ở vị trí 1,2 trên cdefab*f* từ. (C31 = 0, C32 = 0) Chữ cái d không thể xuất hiện ờ vị trí 4 frên từ. (C44 = 0) Từ điển có 8 từ: abdc, adbc, adcb, badc, bdca, dabc, dacb, dbca. Trong đó, có 4 từ có thể là kết quà giải mã: abdc, dabc, dacb, dbca. Ràng buộc: - Trong tất cả các test: 1≤ k ≤ 15; Độ dài xâu s không quá 100. - Có 30% số test với k ≤ 10. - Có 30% số test với xâu 5 chì gồm các ký tự dấu sao *. - Có 40% số test với ràng buộc gốc. Bài 3. Thuê phòng họp (7 điểm) Thành phố nơi Cường làm việc có n địa điểm, được đánh số từ 1 đến n. Một số địa điểm trong thành phố có hội trường cho thuê. Hội trường ở địa điểm thứ i có diện tích là Si và giá thuê là Ci (quy ước rằng nếu ở địa điểm i không có hội trường thì Si = Ci = 0). Có m con đường hai chiều, mỗi con đường nối giữa hai địa điểm và có độ dài cho trước. Hệ thống đường bảo đảm việc đi lại giữa mọi địa điểm. Công ty của Cường ở địa điểm 1. Theo kế hoạch, có Q cuộc họp cần được tổ chức trong các ngày tới. Do thời gian tổ chức và quy mô khác nhau nên mỗi cuộc họp đều có yêu cầu riêng về việc tổ chức. Yêu cầu tổ chức của cuộc họp thứ j được mô tả bởi ba số nguyên (Lj,Hj,rj) với ý nghĩa: Cần thuê một phòng có diện tích thuộc phạm vi [Lj,Hj] và có khoảng cách tới công ty không quá rj. Yêu cầu: Với mỗi cuộc họp, hãy giúp Cường tìm hội trường có giá thuê rẻ nhất mà vẫn thỏa mãn yêu cầu tổ chức. Biết rằng các cuộc họp này có thời gian tổ chức khác nhau nên có thể nhiểu cuộc họp cùng thuê một hội trường. Dữ liệu: Vào từ file văn bàn XGRAPH.INP: - Dòng đầu tiên chứa ba số nguyên n, m, Q. - Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên Si, Ci. - Mỗi dòng trong số m dòng tiếp theo chứa ba số nguyên U.V.W cho biết có một con đường độ dài vv nối giữa hai địa điểm u và V. - Dòng thứ j trong số Q dòng tiếp theo chứa ba số nguyên Lj, Hj, rj mô tả yêu cầu tổ chức của cuộc họp thứ j. DeThi.edu.vn