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

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

1. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn mỗi thao tác) và heap thay cho std::set với 푆 (cùng là (log ) nhưng hằng số tốt hơn). Độ phức tạp thời gian: ( log ). DeThi.edu.vn
2. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 2 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT TỈNH QUẢNG NAM NĂM HỌC 2024 – 2025 ĐỢT 2 MÔN THI: TIN HỌC 10 (CHUYÊN) Thời gian: 180 phút (không kể thời gian giao đề) TỔNG QUAN ĐỀ THI Câu Tên bài Tên tệp chương trình Dữ liệu vào Dữ liệu ra 1 Vận chuyển SHIPPER.* SHIPPER.INP SHIPPER.OUT 2 Hội trại TRAI.* TRAI.INP TRAI.OUT Mã đề: 001 3 Đếm số DEMSO.* DEMSO.INP DEMSO.OUT 4 Tham quan MYSON.* MYSON.INP MYSON.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/C++ hoặc Python Hãy lập trình giải các bài toán sau: Câu 1. (5,0 điểm) Vận chuyển Ngày nay, thương mại điện tử đã và đang phát triển, giúp người sản xuất và tiêu dùng mua bán thuận tiện. Người mua chỉ cần đặt hàng online và người bán có thể giao cho đơn vị vận chuyển để đưa hàng đến tận tay người mua. AB Express là công ty hoạt động trong lĩnh vực vận chuyển hàng. Tại trụ sở trong thành phố A, công ty AB Express đang có N chiếc xe tải đậu liên tiếp nhau trong bãi, xe thứ i có thể chở được ai tấn hàng. Giám đốc trụ sở vừa nhận được thông tin có một nhóm hàng sắp chuyển đến, trong đó có S tấn hàng cần chuyển tới thành phố B. Để đảm bảo chuyển hàng nhanh chóng giữa xe đưa hàng đến và các xe đưa hàng đi tới thành phố B, giám đốc cần lựa chọn trong bãi xe một số chiếc xe tải liên tiếp nhau có tổng tải trọng lớn hơn hoặc bằng S và số lượng xe là ít nhất để tiếp tục vận chuyển hàng đến thành phố B. Yêu cầu: Tìm số lượng xe tải liên tiếp ít nhất có tổng trọng tải lớn hơn hoặc bằng S. Dữ liệu: Vào từ file văn bản SHIPPER.INP gồm: - Dòng đầu tiên chứa hai số nguyên N và S là số lượng xe tải đang có ở bãi xe và trọng lượng số hàng cần vận chuyển tới thành phố B (1 ≤ ≤ 105, 1 ≤ 푆 ≤ 108); 5 - Dòng thứ hai chứa dãy N số nguyên a1, a2,..., aN thể hiện trọng tải của xe thứ ,i (0 ≤ ai ≤ 10 với mọi i = 1,...,N). Kết quả: Ghi ra file văn bản SHIPPER.OUT một số nguyên duy nhất là kết quả thỏa mãn yêu cầu bài toán. Nếu không có kết quả thỏa mãn thì ghi số 0. DeThi.edu.vn
3. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn Ví dụ: SHIPPER.INP SHIPPER.OUT 10 15 2 5 1 3 5 10 7 4 9 2 8 Giới hạn: - Subtask 1: Có 60% số test ứng với 60% số điểm (1 ≤ ≤ 103, 1 ≤ 푆 ≤ 105); - Subtask 2: 40% số test còn lại ứng với 40% số điểm không ràng buộc gì thêm. Câu 2. (5,0 điểm) Hội trại Năm 2025, trường đại học A tổ chức hội trại cho sinh viên các khoa. Chương trình hội trại gồm nhiều hoạt động như hội thi văn nghệ, trò chơi lớn, trò chơi nhỏ và các hoạt động giao lưu. Ở một chặng của hành trình trò chơi lớn, ban tổ chức đã thử thách các đội chơi bằng cách cho mỗi đội một dãy chữ cái, các đội chơi phải giữ nguyên hoặc xóa một số chữ cái để dãy còn lại trở thành một xâu đối xứng. Một xâu được gọi là xâu đối xứng nếu đọc từ trái qua phải cũng giống như đọc từ phải qua trái. Hai cách xóa được gọi là khác nhau nếu tồn tại một vị trí mà trong cách này thì xóa còn trong cách kia thì không xóa (xâu rỗng cũng được tính là một cách). Yêu cầu: Bạn là người lập trình giỏi, hãy giúp ban tổ chức chuẩn bị đầy đủ đáp án là số cách xóa xâu nhiều nhất tương ứng với các xâu cho trước. Dữ liệu: Vào từ file TRAI.INP gồm: - Dòng đầu chứa số nguyên dương N (N ≤ 109); - Tiếp theo là một số dòng, mỗi dòng chứa một xâu kí tự chỉ gồm các kí tự từ ‘a’ đến ‘z’ mô tả một bộ dữ liệu cho mỗi đội. Kết quả: Ghi ra file TRAI.OUT gồm một số dòng, mỗi dòng là đáp án của bộ dữ liệu tương ứng với file dữ liệu vào chia dư cho N. Ví dụ: TRAI.INP TRAI.OUT 100 4 abc 9 baba Giới hạn: - Subtask 1: 50% số test ứng với 50% số điểm có độ dài xâu < 15 và số dòng < 300; - Subtask 2: 50% số test ứng với 50% số điểm có độ dài xâu < 200 và số dòng < 2500. Câu 3. (5,0 điểm) Đếm số Năm học 2023-2024, bạn An đạt danh hiệu học sinh xuất sắc. Bố bạn An rất tự hào về con mình, vì vậy ông quyết định tặng cho An một bộ máy tính mới. Bố bạn An còn khuyến khích thêm bằng cách đưa ra một câu đố, nếu An có thể giải được, bộ máy tính mà An nhận được sẽ có cấu hình mạnh gấp hai lần so với bộ máy tính bình thường. Bố bạn An định nghĩa DeThi.edu.vn
4. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn số độc đáo là số mà trong đó không có hai chữ số liền kề nào giống nhau. Bố cho An hai số nguyên a, b và yêu cầu An phải đếm chính xác số lượng số độc đáo trong phạm vi từ a đến b. An rất muốn có bộ máy tính với cấu hình siêu mạnh nhưng không biết làm sao để giải câu đố thật nhanh. Bạn giúp An nhé. Dữ liệu: Vào từ file DEMSO.INP một dòng duy nhất có hai số nguyên a và b (0 ≤ a ≤ b ≤ 1018). Kết quả: Ghi ra file DEMSO.OUT là một số nguyên duy nhất là số lượng số độc đáo trong [a,b]. DEMSO.INP DEMSO.OUT 10 20 10 Giới hạn: - Subtask 1: Có 60% số test ứng với 60% số điểm (1 ≤ ≤ ≤ 106); - Subtask 2: Có 40% số test ứng với 40% số điểm (1 ≤ ≤ ≤ 1018). Câu 4. (5,0 điểm) Tham quan Nhân dịp lễ 8/3, gia đình Minh đi tham quan tại Thánh địa Mỹ Sơn. Nơi đây từng là kinh đô của vương quốc Chăm Pa cổ với rất nhiều khu quần thể đền tháp. Vương quốc Chăm Pa xây dựng kinh đô của mình trên một diện tích rất rộng lớn, gồm nhiều đồi núi và sông hồ. Từ một khu đền tháp bất kỳ luôn có đường đi đến tất cả các khu đền tháp khác. Có xe trung chuyển để đưa các đoàn khách du lịch di chuyển giữa hai khu đền tháp kề nhau. Mỗi lần di chuyển giữa hai khu đoàn khách sẽ tốn một vé di chuyển. Trong chuyến tham quan này, gia đình Minh mua D tấm vé xe trung chuyển và một tấm bản đồ mô tả bố cục của Thánh địa gồm N khu đền tháp và con đường di chuyển giữa các khu đền tháp. Sau một ngày du lịch đầy thú vị, Minh nhìn lại bản đồ và suy nghĩ, nếu có thể bắt đầu từ bất kỳ khu đền tháp nào, với D tấm vé xe trung chuyển trong tay, Minh có thể di chuyển bao nhiêu hành trình tham quan khu đền tháp. Yêu cầu: Hãy đếm số lượng cặp khu đền tháp ( , 푣) sao cho khoảng cách từ khu đến khu 푣 đúng bằng D chuyến xe. Coi như cặp khu đền tháp ( , 푣) và (푣, ) là một. Dữ liệu: Vào từ file văn bản MYSON.INP: - Dòng đầu tiên chứa hai số nguyên và là số lượng khu đền tháp và số lượng vé xe trung chuyển (1 ≤ ≤ 106, 1 ≤ ≤ 1000). - ― 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên và thể hiện cho hai khu đền tháp kề nhau có đường đi (1 ≤ , ≤ , ≠ ). Mỗi cặp số nguyên ( , ) chỉ xuất hiện một lần. Kết quả: Ghi ra file văn bản MYSON.OUT một số nguyên duy nhất là số lượng cặp khu đền tháp có độ dài đường đi đúng bằng chuyến xe. Nếu không có kết quả thỏa mãn ghi ra số 0. Giới hạn: - Subtask 1: Có 60% số test ứng với 60% số điểm (1 ≤ ≤ 103); - Subtask 2: 40% số test còn lại ứng với 40% số điểm không ràng buộc gì thêm. DeThi.edu.vn
5. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn Ví dụ: MYSON.INP MYSON.OUT 9 2 9 1 2 1 3 1 4 2 5 3 6 3 7 6 8 7 9 Giải thích: Có cặp khu đền tháp thỏa mãn là: (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (3, 4), (3, 8), (3, 9), (6, 7). ---------- HẾT ---------- DeThi.edu.vn
6. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn ĐÁP ÁN Câu Nội dung Điểm Subtask 1: - Có 60% số test ứng với 60% số điểm (1 ≤ ≤ 103, 1 ≤ 푆 ≤ 105) 3 1 Subtask 2: 2 - 40% số test còn lại ứng với 40% số điểm không ràng buộc gì thêm. Subtask 1: 50% số test ứng với 50% số điểm có độ dài xâu ≤ 15 và số dòng 2.5 ≤ 300. 2 Subtask 2: 50% số test ứng với 50% số điểm có độ dài xâu ≤ 200 và số dòng 2.5 ≤ 2500. Subtask 1: Có 60% số test ứng với 60% số điểm (1 ≤ ≤ ≤ 106). 3 3 Subtask 2: Có 40% số test ứng với 40% số điểm (1 ≤ ≤ ≤ 1018). 2 Subtask 1: Có 60% số test ứng với 60% số điểm (1 ≤ ≤ 103.) 3 4 Subtask 2: 40% số test còn lại ứng với 40% số điểm không ràng buộc gì thêm 2 DeThi.edu.vn
7. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn ĐỀ SỐ 3 SỞ GD & ĐT HÀ NỘI KỲ THI CHỌN HSG CẤP TRƯỜNG TRƯỜNG THPT PHÙNG KHẮC NĂM HỌC 2024-2025 KHOAN - THẠCH THẤT MÔN THI: TIN HỌC- LỚP 10 Thời gian: 150 phút (không kể thời gian giao đề) TỔNG QUAN BÀI THI Tên file STT Tên bài Dữ liệu vào Kết quả ra Điểm chương trình 1 DÃY SỐ DAYSO.* Nhập từ bàn phím In ra màn hình 3.5 2 TOP 3 TOP3.* Nhập từ bàn phím In ra màn hình 3.5 3 XAUCCDN XAUCCDN.* Nhập từ bàn phím In ra màn hình 4.5 4 UOCSNT UOCSNT.* Nhập từ bàn phím In ra màn hình 4.5 5 DAYCON DAYCON.* Nhập từ bàn phím In ra màn hình 4 Chú ý: Dấu * được thay thế bởi CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là C/C++ hoặc Python. Thí sinh tạo thư mục có tên là Số báo danh của TS tại thư mục gốc ổ đĩa C. Thí sinh đặt tên theo đúng như quy định trong đề thi. BÀI 1: DÃY SỐ. Viết chương trình nhập một dãy số nguyên. a. Tính tổng các số chẵn và tổng các số lẻ và in kết quả ra màn hình. b. Sắp xếp các phần tử của dãy theo thứ tự không giảm và đưa kết quả ra màn hình. BÀI 2. TOP 3 Sở GD thành phố cần chọn 3 em học sinh có thành tích thể thao cao nhất để tuyên dương và trao thưởng nhân dịp tổng kết năm học vừa qua dựa vào thành tích các trường tổng hợp gửi lên. Em hãy viết chương trình để chọn được 3 bạn có thành tích cao nhất biết rằng: - Thành tích mỗi học sinh được qui đổi thành 1 số nguyên dương. - Các học sinh đều có thành tích khác nhau. Yêu cầu: Nhập dữ liệu từ bàn phím và in kết quả lên màn hình. Hàng 1: Chỉ số và thành tích của học sinh có thành tích cao nhất. Hàng 2: Chỉ số và thành tích của học sinh có thành tích cao thứ 2. Hàng 3: Chỉ số và thành tích của học sinh có thành tích cao thứ 3. DeThi.edu.vn
8. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn Ví dụ: INPUT OUTPUT Giải thích 6 5 11 3 5 1 2 11 8 6 8 2 5 BÀI 3: XÂU CON CHUNG DÀI NHẤT. Xâu A gọi là xâu con của xâu B nếu trong xâu B có một dãy ký tự liên tiếp đúng bằng xâu A. Cho hai xâu s1 và s2 hãy viết chương trình để tìm xâu ketqua là xâu con chung dài nhất của s1 và s2 Yêu cầu: Nhập dữ liệu từ bàn phím và in kết quả lên màn hình. Ví dụ: INPUT OUTPUT Giải thích abcde123 abc abfceabcxyz BÀI 4: ƯỚC SỐ NGUYÊN TỐ. Mỗi số đều có ít nhất 1 ước số là số nguyên tố. VD: số 6 có 2 ước nguyên tố là 2 và 3. Số 25 có ước nguyên tố là 5. Em hãy viết chương trình tìm số nguyên có nhiều ước số là số nguyên tố nhất trong một dãy số nguyên. Yêu cầu: Viết 1 hàm kiểm tra số nguyên tố và 1 hàm tính tổng số ước nguyên tố của một số nguyên. Ví dụ: INPUT OUTPUT 38 88 50 15 25 105 105 BÀI 5: DÃY CON. Cho một danh sách các số nguyên. Viết một chương trình để tìm dãy con liên tiếp có tổng lớn nhất trong danh sách đó. Nhập dữ liệu từ bàn phím và in kết quả lên màn hình. Ví dụ: INPUT OUTPUT Giải thích 1, -2, 3, 4, -1, 2, 1, -5, 4 3, 4, -1, 2, 1 ------------- HẾT ------------- DeThi.edu.vn
9. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn ĐÁP ÁN BÀI 1: DÃY SỐ. Viết chương trình nhập một dãy số nguyên. a. Tính tổng các số chẵn và tổng các số lẻ và in kết quả ra màn hình. (2 điểm) b. Sắp xếp các phần tử của dãy theo thứ tự không giảm và đưa kết quả ra màn hình.(1,5 điểm) Code tham khảo # Nhập dãy số nguyên từ người dùng arr = list(map(int, input("Nhập dãy số nguyên (cách nhau bằng dấu cách): ").split())) # a. Tính tổng các số chẵn và tổng các số lẻ sum_even = sum(num for num in arr if num % 2 == 0) sum_odd = sum(num for num in arr if num % 2 != 0) print(f"Tổng các số chẵn: {sum_even}") print(f"Tổng các số lẻ: {sum_odd}") # b. Sắp xếp dãy số theo thứ tự không giảm và in ra kết quả arr_sorted = sorted(arr) print(f"Dãy số sau khi sắp xếp theo thứ tự không giảm: {arr_sorted}") BÀI 2. TOP 3 - Xử lý input và output thành công (1 đ) - Xử lý tốt, ra kết quả đúng 2,5 điểm. Số test chấm bài, mỗi test đúng được bao nhiêu điểm? Code tham khảo f1=open(r"d:hsg\bai1_int.txt", 'r') n=int(f1.readline()) mylist = f1.readline().split(' ') t1,t2,t3=0 id1,id2,id3=-1 for i in range(n): k=int(mylist[i]) if k>t1: t3=t2 id3=id2 t2=t1 id2=id1 t1=k id1=i elif k>t2: t3=t2 id3=id2 t2=k id2=i elif k>t3: DeThi.edu.vn
10. Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn t3=k id3=i f2 = open(r"d:hsg\bai1_out.txt", 'w') f2.write(str(id1+1) +" "+ str(t1)+"\n") f2.write(str(id2+1) +" "+ str(t2)+"\n" ) f2.write(str(id3+1) +" "+ str(t3)) f1.close f2.close BÀI 3: XÂU CON CHUNG DÀI NHẤT. - Xử lý input và output thành công (1 đ) - Xây dựng hàm xauconchungdainhat đúng 2,5 điểm - Các xử lý còn lại 1 điểm Lưu ý: Thí sinh có chương trình bố cục khác xử lý đúng vẫn cho điểm tương tự. Code tham khảo def xauconchungdainhat(s1, s2): m, n = len(s1), len(s2) # Bảng dp lưu trữ độ dài của chuỗi con chung dp = [[0] * (n + 1) for _ in range(m + 1)] max_len = 0 # Độ dài chuỗi con chung dài nhất end_pos = 0 # Vị trí kết thúc của chuỗi con chung dài nhất trong s1 # Duyệt qua từng ký tự của s1 và s2 for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: # Nếu hai ký tự giống nhau dp[i][j] = dp[i - 1][j - 1] + 1 if dp[i][j] > max_len: # Cập nhật nếu tìm được chuỗi con chung dài hơn max_len = dp[i][j] end_pos = i # Lưu vị trí kết thúc của chuỗi con chung dài nhất else: dp[i][j] = 0 # Nếu không giống nhau thì độ dài chuỗi con chung là 0 # Trả về chuỗi con chung dài nhất return s1[end_pos - max_len:end_pos] # Các xử lý khác. BÀI 4: ƯỚC SỐ NGUYÊN TỐ.\ - Xử lý input và output thành công (1 đ) - Viết hàm kiểm tra SNT đúng 1,25 điểm. - Viết hàm tính các ước nguyên tố 1,25 điểm. - Xử lý tốt chương trình chính tốt 1 điểm Code tham khảo DeThi.edu.vn