HSG tin Đà Nẵng 2009-2010

Bài 1: xâu FIBINACCI
Xét dãy các xâi F1,F2,...,FN trong đó:
F1 = 'A'
F2 = 'B'
Fk+1 = Fk + Fk-1(K=>2)
ví dụ:
F1 = 'A'
F2 = 'B'
F3 = 'BA'
F4 = 'BAB'
F5 = 'BABBA'
F6 = 'BABBABAB'
...
Cho xâu S độ dài không quá 25, chỉ bao gồm các kí tự 'A' và 'B'
yêu cầu: hãy xác định số lần xuất hiện xâu S trong xâu FN,N<=35. Chú Ý: Hai lần xuất hiện của S trong FN không nhất thiết phải là các xâu rời nhau hoàn toàn.
Dữ liệu vào: Đọc từ file văn bản FIBISTR.INP có cấu trúc như sau:
Gồm nhiều dòng, mỗi dòng có N S. Giữa N và S có đúng 1 dấu cách. Dữ liệu vào là chuẩn, không cần kiểm tra.
Dữ liệu ra: Ghi ra file văn bản FIBISTR.OUT có cấu trúc như sau:
Gồm nhiều dòng, mỗi dòng dữ liệu ứng với một dòng kết quả ra
Ví Dụ:
FIBISTR.OUT FIBISTR.OUT
3 A 1
3 AB 0
8 BABBAB 4

Bài 2: SỐ PHẢN NGUYÊN TỐ
Một số tự nhiên n được gọi là số phản nguyên tố nếu nó có nhiều ước số nhất trong n số tự nhiên đầu tiên
Yêu cầu: Cho số K (K<=10000) ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.
Dữ liệu vào : Đọc từ file văn bản SOPNT.INP có cấu trúc như sau:
Dòng đầu tiên là số M(1<M<=100): số các số cần tìm số phản nguyên tố lớn nhất của nó.
M dòng tiếp theo là các số K1,K2,..KM
Dữ liệu ra: Ghi ra file văn bản SOPNT.OUT có cấu trúc như sau:
Gồm M dòng, Dòng thứ i (1<=i<=M) là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.
ví dụ
SOPNT.INP SOPNT.OUT
1 840
1000 


Bài 3: que diêm
Ngồi nhà quá rỗi, Sơn có ý tưởng dùng các que diêm tạo thành các số thập phân. Một cách đại diện cho 10 chữ số thập phân như sau:
1 2 3 4 5 6 7 8 9 0 ( sr các bạn, cái này mình ko biết viết sao hết. Nó giống như cái chỉ số trong đồng hồ điện tử ý. ví dụ: số 1 thì có 2 gạch nhỏ.)
Cho N que diêm, Sơn có thể tạo ra một loạt các chữ số.Sơn kinh ngạc phát hiện ra số nhỏ nhất và lớn nhất trong số đó có thể tạo được bằng cách sử dụng tất cả các que diêm của Sơn.
Yêu cầu: Xác định số nhỏ nhất và lớn nhất mà Sơn có thể tạo ra.
Dữ liệu vào: Đọc từ file văn bản MATCH.INP có cấu trúc như sau:
Dòng đầu tiên là số test K(1<K<=100)
K dòng tiếp theo, mỗi test gồm một dòng chứa số nguyên n (2<=n<=100) là số que diêm
Dữ liệu ra: Ghi ra file văn bản MATCH.OUT có cấu trúc như sau:
Gồm K dòng, mỗi dòng là số nhỏ nhất và số lớn nhất, là các số nguyên dương có chữ số đầu tiên khác 0. Ví dụ:
MATCH.INP MATCH.OUT
2 7 7
3 8 711
7