# Monkey and river (optimal)

Jun 2nd, 2020
1,178
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def solution(a, d)
2.   return 0 if d > a.length
3.
4.   position = -1
5.   time = 0
6.   max_time = 0
7.   length = a.size
8.
9.   while true do
10.     start_position = position + 1
11.     end_position = position + d
12.     new_position = -2
13.
14.     while new_position != position
15.       return time if end_position >= length
16.
17.       new_position = position
18.       unreach_count = 0
19.
20.       end_position.downto(start_position) do |index|
21.         max_time = [max_time, a[index]].max
22.
23.         if a[index] == -1
24.           unreach_count += 1
25.
26.           return -1 if unreach_count >= d
27.         end
28.
29.         if a[index] <= time && a[index] != -1
30.           position = index
31.           break
32.         end
33.       end
34.
35.       start_position = position + 1
36.       end_position = [position + d, length - 1].min
37.     end
38.
39.     if position + d + 1 > length
40.       return [max_time, time].min
41.     end
42.
43.     time += 1
44.
45.     return [max_time, time].min if time > length
46.   end
47. end
RAW Paste Data