ĐỀ KIỂM TRA ĐỘI TUYỂN HSG LẦN 3 - Ôn Hải Phòng T11/2020
Rar the Cat cuối cùng đã thực hiện được ước mơ từ nhỏ là trở thành phi công và muốn đưa bạn mình, Dinosaur, trên một vài chuyến bay ngắm cảnh. Trong những chuyến bay của
mình Rar phải bay qua các ngọn núi trong ngọn núi (đánh số thứ tự từ đến ), trong đó ngọn núi thứ có chiều cao là mét.
Ví dụ, hình ảnh dưới đây thể hiện có ngọn núi, chiều cao là :
Rar sẽ thực hiện chuyến bay, với chuyến bay thứ có độ cao hành trình tối đa là mét. Mỗi chuyến bay bắt đầu từ núi thứ và kết thúc trên núi thứ (trong đó ) từ trái sang phải. Vì mỗi chuyễn bay của anh ta có độ cao bay tối đa, nên anh ta không thể bay ngang, cất cánh hoặc hạ cánh trên một ngọn núi có độ cao lớn hơn độ cao bay của máy bay mà anh ta điều khiển.
Đối với chuyến bay thứ , hãy giúp Rar xác định tổng số chuyến bay khác nhau mà anh ta có thể thực hiện, tức là tổng số cách Rar có thể chọn và sao cho không có dãy núi nào từ và có chiều cao lớn hơn .
Dữ liệu vào:
Dòng đầu tiên sẽ chứa hai số nguyên và ;
Dòng thứ hai sẽ chứa số nguyên ;
Dòng thứ ba sẽ chứa số nguyên .
Dữ liệu ra:
Ghi ra số nguyên trên dòng, với số trên dòng thứ cho biết tổng số chuyến bay khác nhau mà Rar có thể thực hiện với chuyến bay thứ của mình.
Ví dụ:
Dữ liệu vào:
6 3
1 3 2 4 1 2
2 3 4
Dữ liệu ra:
5
9
21
Giới hạn:
;
Subtask số điểm có ;
Subtask số điểm tiếp theo có ;
Subtask số điểm tiếp theo có và dãy tăng nghiêm ngặt;
Subtask số điểm tiếp theo có ;
Subtask số điểm cuối cùng không có ràng buộc gì thêm.
