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

SỞ GIÁO DỤC VÀ ĐÀO TẠO THI CHỌN ĐỘI TUYỂN HỌC SINH GIỎI QUỐC GIA<br /> SÓC TRĂNG<br /> Năm 2018<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ứ nhất: 15/9/2017<br /> Đề thi này có 02 trang, gồm 03 câu<br /> TỔNG QUAN NGÀY THI THỨ NHẤT<br /> File chương trình<br /> <br /> File dữ liệu vào<br /> <br /> Ghép số nguyên dương<br /> <br /> C1GhepSo.*<br /> <br /> GhepSo.inp<br /> <br /> GhepSo.out<br /> <br /> 2<br /> <br /> Trò chơi kéo co<br /> <br /> C2KeoCo.*<br /> <br /> KeoCo.inp<br /> <br /> KeoCo.out<br /> <br /> 3<br /> <br /> Tách chuỗi đối xứng<br /> <br /> C3TachCDX.*<br /> <br /> TachCDX.inp<br /> <br /> TachCDX.out<br /> <br /> Câu<br /> <br /> Tên câu<br /> <br /> 1<br /> <br /> File kết quả<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) Ghép số nguyên dương<br /> Trong giờ ra chơi Bi đố Bo như sau: Có hai số nguyên dương A và B, cần tạo ra số C<br /> bằng cách ghép các chữ số của A và B sao cho thứ tự các chữ số của A và B không thay đổi<br /> trên số C. Bạn hãy giúp Bo xây dựng số C sau đó tìm giá trị nhỏ nhất và lớn nhất của số C.<br /> Dữ liệu: vào từ tập tin văn bản GhepSo.inp: gồm một dòng duy nhất có 2 số nguyên<br /> dương A và B, với 1 ≤ A, B ≤ 108, dữ liệu đảm bảo không có các chữ số 0 vô nghĩa của A và B.<br /> Kết quả: ghi ra tập tin văn bản GhepSo.out: gồm<br /> - Dòng thứ nhất ghi giá trị của số A và số B.<br /> - Dòng thứ hai ghi giá trị nhỏ nhất của số C.<br /> - Dòng thứ ba ghi giá trị lớn nhất của số C.<br /> Ví dụ:<br /> GhepSo.inp<br /> GhepSo.out<br /> 28 41<br /> <br /> So A = 28 va so B = 41<br /> Gia tri nho nhat cua so C: 2418<br /> Gia tri lon nhat cua so C: 4281<br /> <br /> Câu 2: (7,0 điểm) Trò chơi kéo co<br /> Trong buổi sinh hoạt ngoài trời, thầy chủ nhiệm chia học sinh thành hai đội để chơi<br /> kéo co. Bạn hãy giúp thầy tìm cách chia hai đội sao cho công bằng nhất theo cả hai điều<br /> kiện là tổng khối lượng các thành viên trong hai đội có sự chênh lệch là ít nhất và số thành<br /> viên của hai đội chênh lệch nhau không quá 1 người.<br /> Dữ liệu: vào từ tập tin văn bản KeoCo.inp: gồm<br /> - Dòng đầu là một số nguyên dương N (2 ≤ N ≤ 100) là số học sinh trong lớp.<br /> - N dòng tiếp theo cho biết khối lượng của từng học sinh, khối lượng có giá trị trong<br /> khoảng [20..150].<br /> 1<br /> <br /> Kết quả: ghi ra tập tin văn bản KeoCo.out: hai dòng được sắp xếp không giảm theo<br /> tổng khối lượng mỗi đội, mỗi dòng thể hiện tổng số thành viên và khối lượng của mỗi đội.<br /> Nếu có nhiều cách chia thì in ra 1 cách chia bất kì.<br /> Ví dụ:<br /> KeoCo.inp<br /> KeoCo.out<br /> 5<br /> 30<br /> 70<br /> 20<br /> 50<br /> 40<br /> <br /> 2 100<br /> 3 110<br /> <br /> Câu 3: (7,0 điểm) Tách chuỗi đối xứng<br /> Chuỗi đối xứng (palindrome) là chuỗi mà nếu ta đọc từ trái sang phải hay từ phải<br /> sang trái thì đều giống nhau. Ví dụ chuỗi 'xyzyx' là chuỗi đối xứng. Một ký tự duy nhất cũng<br /> được gọi là chuỗi đối xứng.<br /> Một chuỗi S bất kỳ luôn có thể tách được từ các chuỗi đối xứng. Ví dụ chuỗi<br /> ‘madambobseesanna’ có một số cách tách như sau:<br /> 1) ‘m’ + ‘a’ + ‘d’ + ‘a’ + ‘m’+ ‘b’ + ‘o’ + ‘b’ + ‘s’ + ‘e’ + ‘e’ + ‘s’ + ‘a’ + ‘n’ + ‘n’ + ‘a’<br /> 2) ‘madam’ + ‘bob’ + ‘sees’ + ‘anna’<br /> 3) ‘madam’ + ‘bob’ + ‘s’ + ‘ee’ + ‘s’ + ‘anna’<br /> 4) ‘m’ + ‘ada’ + ‘m’ + ‘b’ + ‘o’ + ‘b’ + ‘sees’ + ‘anna’<br /> Tổng quát S = P1 + P2 +...+ Pk, với P1, P2,... , Pk là các chuỗi đối xứng. Bạn hãy tìm<br /> cách biểu diễn S sao cho k là bé nhất. Trong ví dụ trên k = 4 (cách tách số 2).<br /> Dữ liệu: vào từ tập tin văn bản TachCDX.inp:<br /> - Dòng thứ nhất là số nguyên N (1 ≤ N ≤ 2000) biểu thị chiều dài chuỗi S.<br /> - Dòng thứ hai là chuỗi S gồm N ký tự là các chữ cái la tinh thường từ ‘a’ đến ‘z’.<br /> Kết quả: ghi ra tập tin văn bản TachCDX.out:<br /> - Dòng thứ nhất là số nguyên k.<br /> - Trong k dòng tiếp theo, tại dòng thứ i là chuỗi đối xứng Pi. Nếu có nhiều cách biểu<br /> diễn, chỉ cần in ra một cách bất kỳ.<br /> Ví dụ:<br /> TachCDX.inp<br /> TachCDX.out<br /> 16<br /> madambobseesanna<br /> <br /> 4<br /> madam<br /> bob<br /> sees<br /> anna<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 /> <br /> 2<br /> <br />