Đề HSG đề xuất (2008-2009)

Sở GD&ĐT Nghệ An Kì thi chọn Học Sinh Giỏi tỉnh
Năm học 2008 - 2009

Môn thi: tin học lớp 12 thpt
(Đề thi gồm có 2 trang)
Thời gian: 180 phút (không kể thời gian giao đề)

Bài 1: CASSETTE
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 và thời gian phát bài hát đó được tính 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 đựợc số phút phát ra.
Yêu cầu: Tìm cách ghi các bài hát vào băng của chủ quán để cho tổng thời gian quay băng trong mỗi lần khách đến là ít nhất?
Dữ liệu: File văn bản CASSETTE.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ứ hai là N số nguyên N, mỗi số là thời gian phát mỗi bài hát.
Kết quả: Ghi vào File văn bản CASSETTE.OUT như sau:
- Dòng đầu tiên ghi tổng 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 , dòng ghi hai số nguyên là thứ tự bài hát và thời gian tìm và phát bài hát đó.
Ví dụ:
CASSETTE.INP
CASSETTE.OUT

5
3 2 6 10 1
44
5 1
2 3
1 6
3 12
4 22


Bài 2: CODE
Các số từ 1 đến 9 được mã hoá dưới dạng các từ chỉ chứa các kí tự a, b và c như sau:
Chữ số
1
2
3
4
5
6
7
8
9

Mã
a
b
cc
bbc
cbc
abc
bac
aac
cac

Cho một xâu (có độ dài không quá 100) chỉ chứa các kí tự a, b, c.
Yêu cầu: Cho biết số nguyên tương ứng của xâu nếu mã hoá được, nếu không được ghi ra số 0
Dữ liệu: vào từ File CODE.INP là một xâu(có độ dài không quá 100)
Kết quả: Xuất ra File CODE.OUT số nguyên tương ứng của xâu nếu mã hoá được, nếu không được ghi ra số 0
Ví dụ:
CODE.INP
CODE.OUT
CODE.INP
CODE.OUT

abacc
1213
accbc
0


Bài 3: ROTATION
Cho một số X (số chữ số của X <=14). Ta gọi số đó là một số xoay khi xoay số X một góc 180 thì ta vẫn được số X. Ví dụ: 11, 69, 96 là những số xoay.
Yêu cầu: Khi cho một số K, hãy tìm xem với những số có K chữ số thì có bao nhiêu số xoay và đó là những số nào?
Dữ liệu: vào từ File ROTATION.INP chỉ ghi duy nhất một số nguyên dương K(1<=K<=14).
Kết quả: Xuất ra File ROTATION.OUT mỗi dòng ghi một số thoả mãn.
Ví dụ:
ROTATION.INP
ROTATION.OUT

2
11
69
88
96


Bài 4: PERMUT
Cho một mảng A gồm N số là một hoán vị từ 1 đến N. Một dẫy con của dãy trên là một đoạn liên tục từ u đến v (u<=v).
Yêu cầu: Tìm tất cả các dãy con sao cho dãy con đó cũng là một hoán vị của các số liên tiếp bắt đầu từ 1.
Dữ liệu: vào từ File PERMUT.INP:
Dòng thứ nhất ghi số N (N<=30000).
Dòng thứ hai ghi N số A[1] đến A[N]
Kết quả:Xuất ra ghi vào File PERMUT.OUT