ĐỀ THI OLYMPIC TIN HỌC KHÔNG CHUYÊN
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (69.22 KB, 2 trang )
– – Trần Thành
SỞ GD & ĐT BĂC GIANG
KỲ THI OLYMPIC TIN HỌC
KHÔNG CHUYÊN
LẦN THỨ TƯ – NĂM 2011
ĐỀ THI OLYMPIC TIN HỌC KHÔNG CHUYÊN
BẢNG C – KHỐI THPT – PHẦN THỰC HÀNH
THỜI GIAN LÀM BÀI 120 PHÚT. NGÀY THI 22-3-2011
ĐỀ CHÍNH THỨC
Thí sinh lâọ chương trình bằng ngôn ngữ lập trình Pascal (Turbo Pascal hoặc Free
Pascal) giải các bài toán dưới đây:
Yêu cầu chung:
Tạo thư mục SBD_... trong ổ D:\, lưu các bài làm vào thư mục này theo yêu cầu cụ
thể của từng bài.
Đặt tên chương trình, tên tệp dữ liệu vào, tên tệp kết quả theo đúng quy định.
Đọc dữ liệu vào từ tệp văn bản và ghi kết quả ra tệp văn bản.
BÀI 1: TỔNG CÁC SỐ HẠNG(25 Đ). TÊN TỆP CHƯƠNG
TRÌNH LÀ SUM.PAS
Cho số nguyên dương N(N≤109). Tính tổng các số hạng của N. Ví dụ cho M = 301274
thì tổng các số hạng của N bằng 3+0+1+2+7+4=17.
Dữ liệu vào: Đọc từ file văn bản SUM.INP chứa số nguyên N.
Kết quả ra: Ghi ra file văn bản SUM.OUT một giá trị là tổng các số hạng của số N.
Ví dụ:
SUM.INP
SUM.OUT
301274
17
BÀI 2: ĐẾM SỐ FIBONACI (25 Đ). TÊN TỆP CHƯƠNG
TRÌNH LÀ FIBO.PAS
DÃY số Fibanaci được định nghĩa đệ qui như sau: F0=1, F1=1, Fn= Fn-1 + Fn-2 với n ≥ 2.
Các số hạng đầu tiên của dãy Fibonaci là: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55; Số m được gọi là
số Fibonaci nếu m là một số hạng bất kì của dãy Fibonaci. Ví dụ số 13 được gọi là số
Fibonaci nhưng số 14 không là số Fibonaci.
Cho hai số nguyên dương a và b với (1 ≤ a ≤ b ≤ 109 ). Hãy đếm số lượng số Fibonaci
trong đoạn [a ; b].
Dữ liệu vào: đọc từ file văn bản FIBO.INP gồm 2 số nguyên a và b.
Kết quả ra: ghi ra file văn bản FIBO.OUT một giá trị duy nhất là số lượng số Fibonaci
thuộc đoạn [a ; b].
Ví dụ:
FIBO.INP
FIBO.OUT
5 17
3
BÀI 3: SỐ TỰ NHIÊN NHỎ NHẤT (20 Đ). TÊN TỆP
CHƯƠNG TRÌNH LÀ SOMIN.PAS
Cho dãy số nguyên a có N phần tử a1, a2,……., aN (với 1≤ N ≤ 30000 và 0≤ ai ≤ 109, i =
1,2,..N). hãy tìm số tự nhiên nhỏ nhất không xuất hiện trong dãy số a. ví dụ cho N = 5 và dãy
a là 5, 0, 3, 1, 4 thì số tự nhiên nhỏ nhất không xuất hiện trong dãy số a là 2.
Dữ liệu vào: đọc từ file văn bản SOMIN.INP có dạng:
+ dòng đầu tiên là số N.
+ dòng thứ hai gồm N số nguyên a1, a2,……., aN.
Kết quả ra: ghi ra file văn bản SOMIN.OUT số tự nhiên tìm được.
Ví dụ:
– – Trần Thành
1
– – Trần Thành
SOMIN.INP
5
50314
SOMIN.OUT
2
BÀI 4:NGÂN HÀNG TRẢ TIỀN(10 Đ)TÊN TỆP CHƯƠNG
TRÌNH LÀ MONEY.PAS
Một người đi nấy tiền ở một ngân hàng. Người đó cần lấy một khoảng M đồng. Ngân hàng có
N đồng tiền có mệnh giá lần lượt là A1, A2, …AN. hỏi ngân hàng có bao nhiêu cách trả tiền ? ví
dụ cho N = 5, M = 10, ngân hàng có 5 đồng tiền có mệnh giá là A1=1, A2=2, A3=3, A4=4,
A5=5 thì ngân hàng có 3 cách trả tiền là (A1 ,A2 ,A3 ,A4), (A1 ,A4 ,A5), (A2 ,A3, A5).
Dữ liệu vào: đọc từ file văn bản MONEY.INP có dạng:
+ dòng đầu tiên là hai số N và M (N≤100, M≤100000).
+ dòng tiếp theo chứa N số nguyên dương tương ứng là mệnh giá của N đồng tiền A1, A2,
…AN (0≤Ai≤32000, i=1,2,..,N).
Kết quả ra: ghi ra file văn bản MONEY gồm một giá trị duy nhất là số cách trả tiền của
ngân hàng(số cách trả tiền < Maxlongint).
Ví dụ:
MONEY.INP
MONEY.OUT
5 10
3
12345
– – Trần Thành
2
