Đề thi hsg tin trường Lam Sơn 2009

SỞ GD-ĐT THANH HOÁ
Trường PTTH Lam Sơn



ĐỀ THI CHỌN HSG CẤP TRƯỜNG
Năm học: 2008 - 2009


MÔN THI: TIN HỌC
Thời gian làm bài: 180 phút

Tổng quan bài thi:

Tên bài
File chương trình
File dữ liệu vào
File kết quả

Bài 1
Số Fibonacci
FIBO.PAS
FIBO.INP
FIBO.OUT

Bài 2
Lưới ô
GRID.PAS
GRID.INP
GRID.OUT

Bài 3
Tổ chức tham quan
TOUR.PAS
TOUR.INP
TOUR.OUT

(Đề thi gồm 2 trang)
(Cán bộ coi thi không giải thích gì thêm)
Hãy lập trình giải các bài toán sau:
Bài 1. Số Fibonacci Tên chương trình: FIBO.PAS
Các số Fibonacci F1, F2 … được định nghĩa như sau:
F1 = F2 = 1
FN+1 = FN + FN-1 , N>1, N nguyên dương.
  Người ta viết liên tục, sát nhau các số Fibonacci thành dãy dài bắt đầu từ F1 và thu được dãy U: 11235813…
Yêu cầu:  Cho số N ( 0Dữ liệu:  Vào từ file FIBO.INP gồm duy nhất số nguyên dương N.
Kết quả: Ghi ra file FIBO.OUT số duy nhất là chữ số thứ N của dãy.
Ví dụ:
FIBO.INP
FIBO.OUT

6
8


Bài 2. Lưới ô Tên chương trình: GRID.PAS
Cho một lưới ô vuông gồm m hàng, n cột (1Yêu cầu: Đếm số cách đi khác nhau để con kiến đi từ ô (1,1) đến ô (m,n) theo đường đi ngắn nhất.
Dữ liệu: Vào từ file GRID.INP gồm duy nhất hai số m,n cách nhau bởi khoảng trắng.
Kết quả: Ghi ra file GRID.OUT gồm duy nhất một số nguyên dương là số cách đi khác nhau từ ô (1,1) đến ô (m,n).
Ví dụ:
GRID.INP
GRID.OUT

3 2
3

Bài 3: Tổ chức tham quan Tên chương trình: TOUR.PAS
Trong đợt tổ chức cho đoàn viên đi tham quan danh lam thắng cảnh của địa phương, Tỉnh đoàn cho N đoàn (đánh từ số 1 đến N) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ i đi thăm địa điểm ở cách quảng trường chính di km (i=1,2,...., N). Tỉnh đoàn thuê M xe du lịch đánh số từ 1 đến M (M(N) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ j có mức tiêu thụ xăng là vj đơn vị thể tích/km. Ban đầu tất cả các đoàn và xe đều tập trung ở quảng trường chính.
Yêu cầu: Hãy chọn N xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.
Dữ liệu: File văn bản TOUR.INP:
Dòng đầu tiên chứa hai số nguyên dương N, M (N(M(10000);
Dòng thứ hai chứa các số nguyên dương d1, d2, ..., dN; (di <32000)
Dòng thứ ba chứa các số nguyên dương v1, v2, ..., vM; (vj <32000)
Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng.
Kết quả: Ghi ra file văn bản TOUR.OUT: dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
Dòng đầu tiên chứa tổng lượng xăng dầu cần
Dòng thứ i trong số N dòng tiếp theo ghi chỉ số xe phục vụ đoàn i (i=1, 2, ..., N).
Ví dụ:
TOUR.INP
TOUR.OUT

3 4
7 5 9
17 13 15 10
256
2
3
4



-------------------------- HẾT --------------------------