Đề 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ẠO<br /> SÓC TRĂNG<br /> <br /> THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI QUỐC GIA<br /> <br /> Năm 2018<br /> ¯¯¯¯¯¯¯¯<br /> <br /> ¯¯¯¯¯¯¯¯¯¯¯<br /> ĐỀ CHÍNH THỨC<br /> <br /> Môn: TIN HỌC<br /> (Thời gian làm bài 180 phút, không kể phát đề)<br /> ¯¯¯¯¯¯¯¯¯¯¯¯<br /> Ngày thi thứ hai: 16/9/2017<br /> Đề thi này có 02 trang, gồm 03 câu<br /> TỔNG QUAN NGÀY THI THỨ HAI<br /> Câu<br /> <br /> File chương trình<br /> <br /> Tên câu<br /> <br /> File dữ liệu vào<br /> <br /> File kết quả<br /> <br /> 1<br /> <br /> Mật khẩu an toàn<br /> <br /> C1MatKhau.*<br /> <br /> MatKhau.inp<br /> <br /> MatKhau.out<br /> <br /> 2<br /> <br /> Phân tích số nguyên tố<br /> <br /> C2PhanTich.*<br /> <br /> PhanTich.inp<br /> <br /> PhanTich.out<br /> <br /> 3<br /> <br /> Hệ thống dây điện<br /> <br /> C3DayDien.*<br /> <br /> DayDien.inp<br /> <br /> DayDien.out<br /> <br /> 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<br /> ứng là Pascal hoặc C++. Yêu cầu đặt tên file giống bảng trên.<br /> Hãy lập trình giải các câu hỏi sau:<br /> Câu 1: (6,0 điểm) Mật khẩu an toàn<br /> Mộ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âu<br /> chứ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ố<br /> (‘0’..’9’).<br /> Ví dụ: ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu an toàn, còn ‘a1B2C’, ‘a1b2c3’, ‘tinHoc’<br /> đều không phải là mật khẩu an toàn.<br /> 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ái<br /> thườ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 đếm<br /> xem 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ồm<br /> các ký tự liên tiếp từ i đến j của S là mật khẩu an toàn.<br /> 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.<br /> 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ài<br /> không quá 106.<br /> 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ố<br /> (i, j) tính được.<br /> Ví dụ:<br /> <br /> MatKhau.inp<br /> abc23456PQX<br /> <br /> MatKhau.out<br /> <br /> MatKhau.inp MatKhau.out<br /> <br /> 8<br /> <br /> abc123<br /> <br /> 0<br /> <br /> 1<br /> <br /> Câu 2: (7,0 điểm) Phân tích số nguyên tố<br /> Nhập một số nguyên N (4 < N < 20000). Chọn nhiều nhất M số nguyên tố khác nhau<br /> sao 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ách<br /> chọn như trên?<br /> 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à<br /> có 4 cách chọn như vậy.<br /> 2 + 3 +5 ≤ 15<br /> 2 + 3 + 7 ≤ 15<br /> 2 + 5 + 7 ≤ 15<br /> 3 + 5 + 7 ≤ 15<br /> Dữ liệu: vào từ tập tin văn bản PhanTich.inp: số nguyên N.<br /> Kết quả: ghi ra tập tin văn bản PhanTich.out: số cách chọn.<br /> Ví dụ:<br /> <br /> PhanTich.inp<br /> 15<br /> <br /> PhanTich.out<br /> 4<br /> <br /> Câu 3: (7,0 điểm) Hệ thống dây điện<br /> Mộ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ơ<br /> đồ 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<br /> đó 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] = 0<br /> nế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ử<br /> dụng sao cho cả N phòng đều có điện và số lượng này là ít nhất.<br /> Dữ liệu: vào từ tập tin văn bản DayDien.inp: gồm N + 1 dòng<br /> - Dòng đầu ghi số N<br /> - Dòng i + 1 (1 ≤ i ≤ N) ghi N số A[i, 1] A[i, 2]…A[i, N]<br /> Các số ghi trên cùng một dòng cách nhau ít nhất một dấu cách<br /> Kết quả: ghi ra tập tin văn bản DayDien.out: độ dài dây điện ít nhất.<br /> Ví dụ:<br /> <br /> DayDien.inp<br /> <br /> DayDien.out<br /> <br /> DayDien.inp DayDien.out<br /> <br /> 4<br /> <br /> 34=1<br /> <br /> 4<br /> <br /> 0342<br /> <br /> 14=2<br /> <br /> 0340<br /> <br /> 3032<br /> <br /> 24=2<br /> <br /> 3030<br /> <br /> 4301<br /> <br /> Tong do dai: 5<br /> <br /> 4300<br /> <br /> 2210<br /> <br /> khong thuc<br /> hien duoc<br /> <br /> 0000<br /> --- HẾT ---<br /> <br /> Họ tên thí sinh: ................................................Số báo danh: ..................................................<br /> Chữ ký của Giám thị 1: .................................. Chữ ký của Giám thị 2: ..................................<br /> 2<br /> <br />