Nguồn: Olympic 30/4 năm 2016 Lớp 10
Chùa
Hương là một quần thể di tích thuộc địa phận xã Hương Sơn, huyện Mỹ Đức, thành
phố Hà Nội. Chùa Hương gồm nhiều chùa
chiền (đáng chú ý nhất là chùa Thiên Trù) cùng với động Hương Tích rất nổi tiếng
(được mệnh danh là Nam thiên đệ nhất động)
Chùa
Thiên Trù
|
Động
Hương Tích
|
||||||||
M=4
|
N=5
|
||||||||
Lưng
chừng núi Lão
|
Vào
mùa lễ hội (tháng Giếng đến tháng Ba âm lịch hàng năm), chú tiểu Bờm phải làm
việc khá vất vả. Hằng ngày, Bờm phải từ chùa Thiên Trù xuống lưng chừng núi Lão
rồi từ đố leo tiếp lên gần đỉnh nói đến động Hương Tích. Sau đó, từ động Hương
Tích, Bờm quay lại chùa Thiên Trù theo con đường ban đầu. Con đường bao gồm 2
đoạn dãy bậc thang lát đá với số bạc lần lượt là M
và N (xem hình minh họa). Hành trình
của Bờm như sau:
+ Từ
chùa Thiên Trù đi xuống lưng chừng núi Lão cũng như từ đây đi lên động Hương
Tích, vì đi người không nên Bờm có thể bước qua 1, 2 hoặc 3 bậc tùy thích.
+
Khi đi từ động Hương Tích xuống lưng chừng núi Lão, di phải gánh đồ nên Bờm chỉ
có thể bước qua 1 hoặc 2 bậc đồng thời sử dụng đúng 1 làn bước qua 3 bậc tại vị
trí tùy thích. Tuy nhiên, khi leo tiếp lên chùa Thiên Trù, Bờm chỉ có thể bước
qua 1 hoặc 2 bậc mà thôi.
Yêu cầu: Hãy
tính xem có thể có bao nhiêu cách để Bờm thực hiện một chuyến đi–về trong một
ngày như vậy.
Dữ liệu vào: Từ
tệp văn bản CHUTIEU.INP gồm nhiều dòng, mỗi dòng là một cặp giá trị của M và N (3≤M, N≤500).
Các
số ghi trên cùng một dòng ghi cách nhau ít nhất là một ký tự trắng.
Kết quả: Ghi
ra tệp văn bản CHUTIEU.OUT gồm nhiều dòng, mỗi dòng là kết quả tìm được ứng với
cặp giá trị của M, N thuộc dòng tương ứng tệp dữ liệu vào.
Ví dụ:
CHUTIEU.INP
|
CHUTIEU.OUT
|
3 4
4 5
10 15
22 19
|
168
2275
321404553680
15760806775373345664
|
Ràng
buộc: 50% số test ứng với 50% số điểm của bài có M≤20, N≤20.
