Alhiris

Colocviu problem chests

Jan 25th, 2020
280
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.92 KB | None | 0 0
  1. import math
  2. import cmath
  3.  
  4.  
  5. def main():
  6.     v=[int(x) for x in input().split()]
  7.     n=len(v)
  8.     chests=1 #last chest, first is added by algorithm
  9.     i=0
  10.     while i<n:
  11.         mini=v[i]
  12.         for j in range(1,v[i]+1): #positions he can go to from position i
  13.             if(i+j<n):
  14.                 mini = max(mini,v[i+j]-(v[i]-j))
  15.             else:
  16.                 break
  17.             """
  18.            Let's say we pick the 3rd one(j=3) from position i
  19.            let's say v[i+j]=7, we have to substract v[i]-j so
  20.            we calculate the distance relative to our position now(i).
  21.            (the actual distance we can travel the most)
  22.            on some cases mini is negative, doesn't matter if that's the case
  23.            """
  24.         i+=mini #mini si now the farthest position we can get to, so optimal solution till end.
  25.         chests+=1
  26.     print (chests)
  27.  
  28.  
  29. if __name__=="__main__":
  30.     main()
Advertisement
Add Comment
Please, Sign In to add comment