Kỳ thi chọn học sinh giỏi tỉnh lớp 11 năm học 2013 - 2014 môn thi: Tin học - THPT Bảng A
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (160.15 KB, 2 trang )
<span class='text_page_counter'>(1)</span>SỞ GD& ĐT NGHỆ AN Đề thi chính thức. KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11 NĂM HỌC 2013 - 2014. (Đề thi gồm 2 trang) Môn thi: TIN HỌC- THPT BẢNG A Thời gian: 150 phút (không kể thời gian giao đề) Bài. Tên file nguồn. Bài 1 Bài 2 Bài 3 Bài 4. THANHGO.PAS MIN.PAS SDD.PAS SUBARR.PAS. TỔNG QUAN BÀI THI File Input File Output. Thời gian chạy THANHGO.INP THANHGO.OUT 1 giây MIN.INP MIN.OUT 1 giây SDD.INP SDD.OUT 1 giây SUBARR.INP SUBARR.OUT 1 giây. Điểm 5 6 5 4. Bài 1. (5 điểm) THANH GỖ Cha của Pinocchio muốn làm lại cho Pinocchio một cái mũi mới. Ông có N thanh gỗ, thanh gỗ i có độ dài ai. Là người yêu thích toán học ông ta đưa ra một giải thuật sau để lấy ra thanh gỗ có độ dài cần thiết: - Nếu còn lại 1 thanh gỗ thì ông ta sẽ lấy thanh gỗ này làm mũi cho Pinocchio. - Nếu còn nhiều hơn một thanh gỗ thì ông ta sẽ làm như sau : Bước 1: Chọn ra thanh gỗ i có độ dài ai nhỏ nhất, tiếp theo chọn thanh gỗ j có độ dài aj nhỏ nhất trong các thanh còn lại. Bước 2: Nếu ai = aj thì vứt bỏ bớt một thanh, quay về bước 1. Bước 3: Nếu ai < aj thì ta sẽ cắt khỏi thanh aj đi một đoạn bằng ai, quay lại bước 1. Yêu cầu: Hãy tính độ dài thanh gỗ mà ông ta nhận được để làm mũi cho Pinocchio. Giới hạn: 1 N 10000; 1 ai 109. Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu là số N, dòng sau là N số a1, a2,…, an. Kết quả: Ghi ra file văn bản THANHGO.OUT: Số X là độ dài thanh gỗ tìm được. (Các số trên cùng một dòng của file dữ liệu vào ghi cách nhau ít nhất một ký tự trống) Ví dụ: THANHGO.INP THANHGO.OUT 3 1 234 Bài 2. (6 điểm). SỐ NHỎ NHẤT. Cho một số nguyên dương K và một xâu ký tự S. Xâu S chỉ gồm các ký tự là các chữ cái la tinh thường ‘a’..‘z’ và các chữ số ‘0’..‘9’, trong đó có ít nhất K ký tự là chữ số. Bạn hãy viết một chương trình loại bỏ một số ký tự ra khỏi xâu S sao cho K ký tự còn lại theo đúng thứ tự đó tạo nên số nhỏ nhất. Trong K ký tự còn lại có thể cho phép các chữ số 0 đứng ®Çu. Dữ liệu: Vào từ file văn bản MIN.INP: Dòng thứ nhất là số nguyên dương K (K ≤ 10). Dòng thứ hai ghi xâu S có độ dài nhỏ hơn 250. KÕt qu¶: Ghi ra file v¨n b¶n MIN.OUT: Gåm mét dßng ghi ra K ký tù cßn l¹i t¹o nªn sè nhá nhÊt. 1 Lop10.com.
<span class='text_page_counter'>(2)</span> Ví dụ: MIN.INP. MIN.OUT. 4 307uv5x1y08mnp Bài 3. (5 điểm). 0108. SỐ ĐƠN ĐIỆU. Số a1a2…an được gọi là số đơn điệu nếu ai < ai+1 > ai+2 hoặc ai > ai+1 < ai+2 ( i= 1, n 2) Số có một chữ số; số có hai chữ số khác nhau cũng được gọi là số đơn điệu lần lượt có độ dài bằng 1; 2. Ví dụ: Các số 5, 58, 3748, 32435465768 là số đơn điệu vì: Số 5 có 1 chữ số Số 58 có 2 chữ số khác nhau. Số 3748 có: 3 < 7 > 4 < 8 Số 32435465768 ta thấy: 3 > 2 < 4 > 3 < 5> 4 < 6 > 5 < 7 > 6 < 8 Yêu cầu: Viết chương trình xác định số chữ số lớn nhất tạo thành số đơn điệu của một số cho trước. D÷ liÖu: Vµo tõ file v¨n b¶n SDD.INP: Gồm một số nguyên dương N có không quá 75 chữ số. KÕt qu¶: Ghi ra file v¨n b¶n SDD.OUT: Chứa số nguyên là số chữ số lớn nhất tạo thành đoạn số đơn điệu của số N. Ví dụ: SDD.INP SDD.OUT 3748 4 Bài 4. (4 điểm) SUBARRAY Cho một dãy gồm N số nguyên a1, a2,…, aN và số nguyên dương K. Dãy con ai, ai+1,…, aj (1 I j N) là dãy được tạo từ các phần tử liên tiếp của dãy A, bắt đầu từ phần tử thứ i và kết thúc ở phần tử thứ j. Yêu cầu: Tìm số lượng dãy con của A có ít nhất K phần tử bằng nhau. Dữ liệu: Vào từ file văn bản SUBARR.INP: Dòng đầu tiên chứa hai số nguyên N, K (1 K N 4.105). Dòng thứ hai chứa N số nguyên a1, a2,…, aN (ai 109); Kết quả: Ghi ra file văn bản SUBARR.OUT: Ghi ra số lượng dãy con tìm được. (Các số trên cùng một dòng của file dữ liệu vào ghi cách nhau ít nhất một ký tự trống) Ví dụ: SUBARR.INP SUBARR.OUT 42 3 1212 -------- Hết -------Chú ý: Giám thị không giải thích gì thêm.. Họ và tên thí sinh:.........................................................................Số báo danh:............................. 2 Lop10.com.
<span class='text_page_counter'>(3)</span>
