Đề thi HSG Tỉnh Nghệ An Môn Tin học 11 năm 2013-2014

SỞ GD& ĐT NGHỆ AN

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 đề)
TỔNG QUAN BÀI THI
Bài
Tên file nguồn
File Input
File Output
Thời gian chạy
Điểm

Bài 1
THANHGO.PAS
THANHGO.INP
THANHGO.OUT
1 giây
5

Bài 2
MIN.PAS
MIN.INP
MIN.OUT
1 giây
6

Bài 3
SDD.PAS
SDD.INP
SDD.OUT
1 giây
5

Bài 4
SUBARR.PAS
SUBARR.INP
SUBARR.OUT
1 giây
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
2 3 4
1


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.
Ví dụ:
MIN.INP
MIN.OUT

4
307uv5x1y08mnp
0108


Bài 3. (5 điểm) SỐ ĐƠN ĐIỆU
Số a1, a2, …, an được gọi là số đơn điệu nếu ai < ai+1 > ai+2 hoặc ai > ai+1 < ai+2 (
i=
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