Giáo trình WFALL( thác nước) – ioicamp.net

Giáo trình WFALL( thác nước) – ioicamp.net.Mã gửi bài: WFALL
Đề bài:
Sau những tháng ngày phải chạy trốn thì vua sư tử Simba đã lớn khôn và quyết định trở
về để trả thù cho người cha của mình. Để trở về nhà thì Simba cần phải đi qua một thác
nước (như mô tả ở hình vẽ) từ phía sát mép ngoài bên trái sang phía sát mép ngoài bên
phải.
Thác nước có độ rộng là W và độ cao là H, được chia
thành W cột được đánh số từ 1 đến W từ trái sang phải
và H dòng được đánh số từ 1 đến H từ dưới lên trên. Tại
mỗi cột của thác thì có một dãy liên tiếp các khúc gỗ nằm
ngang trôi từ trên xuống và Simba sẽ phải nhảy qua các
khúc gỗ này để đi qua thác.
Cột thứ i của thác được mô tả gồm các thông tin sau:
 Các khúc gỗ trôi xuống với vận tốc Vi ô/giây.
 Khoảng cách giữa 2 khúc gỗ liên tiếp đều bằng Ki ô
 Tại thời điểm 0, khúc gỗ thấp nhất nằm ở cạnh dưới của ô thuộc dòng Li.
Tại thời điểm 0 Simba đứng trên một hòn đá cố định ở sát mép ngoài bên trái của thác tại
cạnh dưới của ô tại dòng S và Simba cần nhảy qua thác để đến một hòn đá cố định khác
sát mép ngoài bên phải của thác tại cạnh dưới của ô tại dòng T. Ta sẽ đánh số 2 cột đặc
biệt này là cột 0 (là cột bên trái) và cột W+1 (là cột bên phải).
Giả sử tại thời điểm X, Simba đứng trên một khúc gỗ (hay hòn đá) thì Simba có thể đứng
yên trên khúc gỗ (hoặc hòn đá) đó trong một số nguyên giây (trong khi các khúc gỗ vẫn
trôi với vận tốc của nó) hoặc nhảy từ vị trí nó đang đứng đến một vị trí khác. Thời gian để
Simba thực hiện một bước nhảy như vậy là 1s và toàn bộ các khúc gỗ cũng di chuyển
sang một trạng thái khác trong khi nó thực hiện bước nhảy. Có nghĩa là tại thời điểm X+1
thì phải có một khúc gỗ tại vị trí mà Simba sẽ nhảy đến. Simba không thể nhảy từ ô nó
đang đứng đến một ô cao hơn vị trí này quá P ô và cách vị trí này không quá Q ô về phía
bên phải hoặc bên trái. Simba cũng không thể nhảy đến một ô ở ngoài thác (trừ 2 ô bắt
đầu và kết thúc).
Bạn hãy tìm một cách nhảy hợp lý cho Simba để nó có thể nhảy đến đích với thời gian
nhanh nhất.