Đề thi phần lập trình - Bảng B thời gian làm bài: 120 phút, không kể thời gian giao đề

HỘI THI TIN HỌC TRẺ 
TỈNH VĨNH PHÚC
LẦN THỨ X - NĂM 2015
ĐỀ THI PHẦN LẬP TRÌNH - BẢNG B
Thời gian làm bài: 120 phút, không kể thời gian giao đề
————————————
TỔNG QUAN
STT
Tên bài
File chương trình
File dữ liệu
File kết quả
Điểm
Thời gian
1
Bậc cầu thang
Steps.***
Steps.Inp
Steps.Out
40
1s/test
2
Trồng cây
Crops.***
Crops.Inp
Crops.Out
30
1s/test
Lưu ý:
Thí sinh thay “.***” bằng “.PAS” hoặc “.CPP” tuỳ thuộc theo ngôn ngữ lập trình mà thí sinh lựa chọn là Turbo Pascal (Free Pascal) hoặc C/C++;
Thí sinh đặt đúng tên file theo yêu cầu;
Đề thi có 02 trang.
Lập chương trình giải các bài toán sau:
Bài 1. Bậc cầu thang
Bờm rất thích chơi trò chơi điện tử Lucky Luke. Một lần chơi đến màn phải điều khiển Lucky leo lên một cầu thang gồm n bậc.
Các bậc thang được đánh số từ 1 đến n, từ dưới lên trên. Lucky có thể đi lên một bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 (bậc thang số 1 không bao giờ bị thủng).
Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ n). Bờm muốn nhờ bạn trả lời câu hỏi này.
Dữ liệu vào: (Steps.Inp)
Dòng 1: gồm 2 số nguyên n và k, là số bậc của cầu thang và số bậc thang bị hỏng 
 (0 ≤ k < n ≤ 100000).
Dòng 2: gồm k số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng 
 dần. 
Kết quả: (Steps.Out)
In ra phần dư của số cách Lucky leo hết cầu thang khi chia cho 15122011.
Ví dụ: 
Steps.Inp
Steps.Out
4 2
2 3
0
6 1
4 
2
Bài 2. Trồng cây
	Nhằm hưởng ứng ngày môi trường thế giới 5/6, thành phố VY muốn trồng thêm cây xanh. Bản đồ của thành phố VY được biểu diễn dưới dạng mặt phẳng tọa độ Oxy. Thành phố quyết định giao cho các hộ dân trồng cây, mỗi hộ dân sẽ trồng số lượng cây tương ứng là diện tích của một khu đất hình chữ nhật. Mỗi hình chữ nhật có một cạnh nằm trên trục Ox; có: Vị trí bắt đầu là , kết thúc là (<) và chiều cao . Các mảnh đất mà các hộ dân được nhận không nhất thiết phải rời nhau; nếu có phần đất chung, hộ nào đã trồng cây rồi thì các hộ sau không phải trồng cây tại vị trí đó nữa.
Yêu cầu: Hãy tính số cây mà thành phố VY phải chuẩn bị để giao cho các hộ dân.
Dữ liệu vào: (Crops.Inp)
Dòng 1: Ghi số nguyên , là số mảnh đất hình chữ nhật thành phố VY 
 định giao cho các hộ dân.
Dòng 2 đến n+1: dòng thứ i+1 mô tả hình chữ nhật i gồm 3 số nguyên , , thỏa 
 mãn: là các giá trị miêu tả mảnh đất hình chữ nhật thứ i.
Kết quả: (Crops.Out)
Ghi một số là số cây thành phố VY cần chuẩn bị.
Ví dụ:
Crops.Inp
Crops.Out
4
2 5 1
9 10 4
6 8 2
4 6 3
16
Mô tả ví dụ: (điểm đánh dấu “X” là vị trí trồng cây)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
=Hết=
(Cán bộ coi thi không giải thích gì thêm)
Họ và tên thí sinh:SBD:..