Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- import cmath
- def main():
- v=[int(x) for x in input().split()]
- n=len(v)
- chests=1 #last chest, first is added by algorithm
- i=0
- while i<n:
- mini=v[i]
- for j in range(1,v[i]+1): #positions he can go to from position i
- if(i+j<n):
- mini = max(mini,v[i+j]-(v[i]-j))
- else:
- break
- """
- Let's say we pick the 3rd one(j=3) from position i
- let's say v[i+j]=7, we have to substract v[i]-j so
- we calculate the distance relative to our position now(i).
- (the actual distance we can travel the most)
- on some cases mini is negative, doesn't matter if that's the case
- """
- i+=mini #mini si now the farthest position we can get to, so optimal solution till end.
- chests+=1
- print (chests)
- if __name__=="__main__":
- main()
Advertisement
Add Comment
Please, Sign In to add comment