Đề thi HSG vòng trường,2009 chuyên Lào Cai

TRƯỜNG THPT CHUYÊN LÀO CAI
ĐỀ KHẢO SÁT CHẤT LƯỢNG ĐỘI TUYỂN LỚP 11,12

TỔ : TOÁN - TIN
NĂM HỌC 2009- 2010



Môn: Tin Học
Số báo danh:


Thời gian: 150 phút (Không kể thời gian giao đề)
Chữ ký của giám thị số 1


Ngày thi: 29/10/2009







Lập trình giải các bài toán sau:

Bài 1(6điểm): Least Common Multiple

File chương trình: lcm.pas
Giới hạn thời gian: 1 giây
Giới hạn bộ nhớ: 64 KB

Bội số chung nhỏ nhất của một tập các số nguyên dương là số nguyên dương nhỏ nhất mà nó chia hết cho tất cả các số trong tập đó. Ví dụ, bội số chung nhỏ nhất của 5, 7 và 15 là 105.
Hãy viết một chương trình tìm bội số chung nhỏ nhất của một tập gồm n số nguyên dương cho trước.

Dữ liệu: Vào từ bàn phím số nguyên dương n
và n số nguyên dương a1, a2, ..., an, tất cả các số có giá trị nằm trong khoảng của số nguyên 32-bit.

Kết quả: Đưa ra màn hình bội số chung nhỏ nhất của n số a1, a2, ..., an. Giả thiết rằng kết quả nằm trong khoảng số nguyên 32-bit.

Ví dụ:
Dữ liệu vào từ bàn phím
Kết quả trên màn hình

n = 3
a[1] = 5
a[2] = 7
a[3] = 15
105

n = 6
a[1] = 4
a[2] = 10296
a[3] = 936
a[4] = 1287
a[5] = 792
a[7] = 1
10296




Bài 2(7 điểm): To and Fro
File vào:
taf.in


File ra:
taf.out
Giới hạn thời gian: 1 giây

File chương trình:
taf.pas
Giới hạn bộ nhớ: 64 KB


Mo và Larry đã nghĩ ra cách mã hoá các thông báo. Đầu tiên họ chọn ra số cột n và sau đó viết thông báo (chỉ viết các chữ cái la tinh, bỏ qua tất cả các ký tự không là chữ cái la tinh) theo cột, trên mỗi cột các chữ cái được viết từ trên xuống dưới. Họ có thể thêm các chữ cái bất kỳ vào cuối thông báo sao cho sau khi viết nó tạo thành một mảng hình chữ nhật của các chữ cái. Ví dụ, nếu thông báo là “There’s no place like home on a snowy night” và có 5 cột, Mo có thể viết:

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Chú ý rằng Mo chỉ thêm các chữ cái và viết tất cả các chữ cái thành chữ in thường. Trong ví dụ này, Mo sử dụng một ký tự ‘và thêm vào cuối thông báo để tạo thành hình chữ nhật, nhưng anh ta cũng có thể sử dụng bất kỳ chữ cái khác.
Sau đó Mo gửi thông báo tới Larry bằng cách viết các chữ cái theo mỗi hàng: hàng thứ nhất từ trái sang phải, hàng thứ hai từ phải sang trái, hàng thứ ba từ trái sang phải, .... Do đó thông báo được mã hoá là:

toioynnkpheleaigshareconhtomesnlewx

Công việc của bạn là giúp Larry khôi phục lại thông báo gốc (kể cả các ký tự thêm vào) từ một thông báo đã mã hoá.
Dữ liệu: File vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu bao gồm 2 dòng. Dòng đầu tiên chứa số nguyên n là số cột được sử dụng (
). Dòng tiếp theo chứa một xâu chỉ gồm các chữ cái la tinh in thường, không chứa dấu cách và có nhiều nhất là 200 chữ cái. Kết thúc file vào bằng một dòng chứa đúng một số 0.

Kết quả: Với mỗi bộ dữ liệu vào, ghi ra file ra trên một dòng thông báo gốc tương ứng (không chứa dấu cách).
Ví dụ:

taf.in
taf.out

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0
theresnoplacelikehomeonasnowynightx
thisistheeasyoneab


Bài 3(7 điểm): Trộn 2 dãy số

Cho trước 2 dãy số a1, a2, ..., an (n ( 100.000) và b1, b2, ..., bm (m ( 100.000) đã được sắp xếp theo thứ tự tăng dần, tức là a1 ( a2 ( ... ( an và b1 ( b2 ( ... ( bm. Nhiệm vụ của bạn là trộn 2 dãy trên sao cho dãy số sau khi trộn vẫn giữ thứ tự tăng dần.

Dữ liệu: