Đề thi chọn HSG Quốc gia môn Tin học năm 2018 - Sở GD&ĐT Sóc Trăng (Vòng 2)

Hãy tham khảo Đề thi chọn HSG Quốc gia môn Tin học năm 2018 - Sở GD&ĐT Sóc Trăng (Vòng 2) để giúp các bạn biết thêm cấu trúc đề thi như thế nào, rèn luyện kỹ năng giải bài tập và có thêm tư liệu tham khảo chuẩn bị cho kì thi sắp tới đạt điểm tốt hơn.
Nội dung trích xuất từ tài liệu:
Đề thi chọn HSG Quốc gia môn Tin học năm 2018 - Sở GD&ĐT Sóc Trăng (Vòng 2)SỞ GIÁO DỤC VÀ ĐÀO TẠOSÓC TRĂNGTHI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI QUỐC GIANăm 2018¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ĐỀ CHÍNH THỨCMôn: TIN HỌC(Thời gian làm bài 180 phút, không kể phát đề)¯¯¯¯¯¯¯¯¯¯¯¯Ngày thi thứ hai: 16/9/2017Đề thi này có 02 trang, gồm 03 câuTỔNG QUAN NGÀY THI THỨ HAICâuFile chương trìnhTên câuFile dữ liệu vàoFile kết quả1Mật khẩu an toànC1MatKhau.*MatKhau.inpMatKhau.out2Phân tích số nguyên tốC2PhanTich.*PhanTich.inpPhanTich.out3Hệ thống dây điệnC3DayDien.*DayDien.inpDayDien.outDấ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++. Yêu cầu đặt tên file giống bảng trên.Hãy lập trình giải các câu hỏi sau:Câu 1: (6,0 điểm) Mật khẩu an toànMột xâu ký tự được gọi là mật khẩu an toàn nếu xâu có độ dài ít nhất bằng 8 và xâuchứa ít nhất một chữ cái in hoa (‘A’..’Z’), một chữ cái thường (‘a’..’z’), một chữ số(‘0’..’9’).Ví dụ: ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu an toàn, còn ‘a1B2C’, ‘a1b2c3’, ‘tinHoc’đều không phải là mật khẩu an toàn.Một lần, Thanh nhìn thấy một sâu S, chỉ gồm các loại kí tự: Chữ cái in hoa, chữ cáithường và chữ số. Thanh muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếmxem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện: 1 ≤ i < j ≤ length(S) và xâu con gồmcác ký tự liên tiếp từ i đến j của S là mật khẩu an toàn.Yêu cầu: Cho xâu S, tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện nêu trên.Dữ liệu: vào từ tập tin văn bản MatKhau.inp: gồm một dòng chứa xâu S có độ dàikhông quá 106.Kết quả: ghi ra tập tin văn bản MatKhau.out: một số nguyên là số lượng cặp chỉ số(i, j) tính được.Ví dụ:MatKhau.inpabc23456PQXMatKhau.outMatKhau.inp MatKhau.out8abc12301Câu 2: (7,0 điểm) Phân tích số nguyên tốNhập một số nguyên N (4 < N < 20000). Chọn nhiều nhất M số nguyên tố khác nhausao cho tổng của M số nguyên tố này nhỏ hơn hoặc bằng N. Hãy cho biết có bao nhiêu cáchchọn như trên?Ví dụ: Với N = 15, ta có nhiều nhất 3 số nguyên tố có tổng nhỏ hơn hoặc bằng 15 vàcó 4 cách chọn như vậy.2 + 3 +5 ≤ 152 + 3 + 7 ≤ 152 + 5 + 7 ≤ 153 + 5 + 7 ≤ 15Dữ liệu: vào từ tập tin văn bản PhanTich.inp: số nguyên N.Kết quả: ghi ra tập tin văn bản PhanTich.out: số cách chọn.Ví dụ:PhanTich.inp15PhanTich.out4Câu 3: (7,0 điểm) Hệ thống dây điệnMột công ty cần thay toàn bộ hệ thống dây điện cho N phòng làm việc. Cho biết sơđồ mạng lưới điện hiện có của N căn phòng này được biểu diễn bằng ma trận A[i, j] trongđó A[i, j] chính là độ dài của dây điện nối liền giữa hai phòng i, j (A[i, j] = A[j, i], A[i, j] = 0nếu không có dây nối giữa phòng i và phòng j). Hãy lập trình tính độ dài của dây dẫn cần sửdụng sao cho cả N phòng đều có điện và số lượng này là ít nhất.Dữ liệu: vào từ tập tin văn bản DayDien.inp: gồm N + 1 dòng- Dòng đầu ghi số N- Dòng i + 1 (1 ≤ i ≤ N) ghi N số A[i, 1] A[i, 2]…A[i, N]Các số ghi trên cùng một dòng cách nhau ít nhất một dấu cáchKết quả: ghi ra tập tin văn bản DayDien.out: độ dài dây điện ít nhất.Ví dụ:DayDien.inpDayDien.outDayDien.inp DayDien.out434=14034214=20340303224=230304301Tong do dai: 543002210khong thuchien duoc0000--- HẾT ---Họ tên thí sinh: ................................................Số báo danh: ..................................................Chữ ký của Giám thị 1: .................................. Chữ ký của Giám thị 2: ..................................2