De chon HSG tin 12 nam 2011-2012

Sở Giáo Dục & Đào Tạo NGhệ an
TRường THPT DTNT Quỳ HợP
Kỳ thi chọn đội tuyển dự thi
học sinh giỏi tỉnh lớp 12 THPT năm học 2011 - 2012



Môn thi: tin học
Hình thức thi: Thực hành
Thời gian: 180 phút (không kể thời gian giao đề)

Bài 1: (7 điểm): Rút gọn xâu
Cho một xâu s chỉ gồm các chữ cái in thường và độ dài tối đa 250 kí tự. Em hãy viết chương trình tạo ra xâu sg từ xâu s bằng cách xóa các kí tự liên tiếp giống nhau trong xâu s và chỉ để lại một kí tự đại diện trong đoạn đó.
Dữ liệu vào: Từ file văn bản xaugon.inp chứa xâu s chỉ gồm các chữ cái in thường.
Kết quả ra: Ghi ra file văn bản xaaugon.out là xâu sg tìm được.
VD:
Xaugon.inp
Xaugon.out

hhooocccssiinnnhhh
hocsinh

Bài 2: ( 7 điểm): Gía trị lặp
Cho trước dãy số n số nguyên a1, a2, …an không giảm và 2 chỉ số i,j (1
i
j
n).
Hãy tìm số lần lặp lại nhiều nhất của các số trong dãy ai, …, aj .
Dữ liệu: Vào từ file văn bản DAYSO.INP gồm:
Dòng đầu tiên chứa số nguyên n
Dòng thứ 2 chứa dãy số a1, a2, …an
Dòng thứ 3 chứa 2 số i và j
(Các số trên một dòng cách nhau ít nhất 1 dấu cách trống)
Kết quả: Ghi ra file văn bản DAYSO.OUT có:
Dòng đầu tiên chứa số lần lặp lại nhiều nhất của các số trong dãy a1, a2, …an .
Dòng thứ 2 chứa số lần lặp lại nhiều nhất của các số trong dãy ai, …, aj .
Ví dụ:
DAYSO.INP
DAYSO.OUT

10
-1 -1 1 1 1 1 3 10 10 10
5 10
4
3

Hạn chế 1
n
100, -10000
ai
10000 với i
{1,…,n}
Bài 3: (6 điểm) Bang nhac
Tại một quầy băng đĩa người ta ghi các bài hát theo băng. khi khách hàng chọn bài hát thứ i trong băng thì phải quay băng để bỏ qua i-1 bài hát trước đó. Thời gian quay băng bỏ qua mọi bài hát trước đó và thời gian phát bài hát đó là như nhau. Trung bình mỗi lượt khách đến các bài hát trong băng được họ lựa chọn là như nhau. Giả sử băng của chủ quán có dung lượng ghi vừa đủ N bài hát, với mỗi bài hát họ biết dung lượng mỗi bài hát phát ra. Hỏi chủ quán phải ghi các bài hát vào băng như thế nào để cho tổng thời gian quay băng trong mọi lượt khách đến là nhanh nhất?
Dữ liệu vào: Từ file văn bản bannghac.inp như sau:
- Dòng đầu tiên là số N(1<=N<=100) thể hiện số lượng bài hát.
- Dòng thứ 2 là N số nguyên N, mỗi số là thời gian phát mỗi bài hát.
Kết quả ra: Ghi vào file văn bản bangnhac.out như sau:
- Dòng đầu tiên ghi tổng số thời gian phát băng đó nếu mỗi bài hát được phát một lần.
- N dòng tiếp theo, mỗi dòng ghi 2 số nguyên là thứ tự bài hát và thời gian tìm và phát bài hát đó.
VD:
bangnhac.inp
bangnhac.out

5
44