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.
Giáo trình WFALL( thác nước) - ioicamp.net
Giáo trình WFALL( thác nước) - ioicamp.net