Đề thi chọn học sinh giỏi tỉnh lớp 11 năm học 2013 - 2014 môn Tin học

1

SỞ GD & ĐT NGHỆ AN ĐỀ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 11

NĂM HỌC 2013-2014

(Đề 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 File Input File Outout 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 Baì 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 Picochio 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ì ra 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 <=10.000; 1<=ai<=109. Dữ liệu: Vào từ file văn bản THANHGO.INP: Dòng đầu tiên 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 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 gtrì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: 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

Đề thi chính thức

ThuVienDeThi.com

2

Ví dụ:

MIN.INP MIN.OUT 4 307uv5xly08mnp

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 (Với mọi 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à các 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 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 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ử i và kết thúc ở phần từ 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 cứa 2 số nguyên dương N, K (1<=k<=N<=4.105). Dòng thứ 2 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ác nhau ít nhất một ký tự trống) Ví dụ:

SUBARR.INP SUBARR.OUT 4 2 1 2 1 2

3

------- Hết------ Chú ý: Giám thị không giải thích gì thêm.

ThuVienDeThi.com