fork download
  1. # your code goes here
  2. from collections import deque
  3.  
  4. FILE = "test"
  5. try:
  6. inFile = open(FILE+".txt")
  7. except:
  8. pass
  9.  
  10.  
  11. def read():
  12. try:
  13. return inFile.readline().strip()
  14. except:
  15. return input().strip()
  16.  
  17. def bfs(f, s, g, u ,d):
  18. visited = {}
  19. path = {}
  20.  
  21.  
  22. q =deque(maxlen=None)
  23. q.append(s)
  24. visited[s] = True
  25. found = False
  26.  
  27. while q:
  28. track = q.popleft()
  29.  
  30. action_up = track + u
  31. action_down = track - d
  32.  
  33. if (not action_up in visited) and (1 <= action_up <= f) :
  34. visited[action_up] = True
  35. path[action_up] = track
  36. q.append(action_up)
  37.  
  38. if (not action_down in visited) and (1 <= action_down <= f):
  39. visited[action_down ] = True
  40. path[action_down ] = track
  41. q.append(action_down)
  42.  
  43. if action_down == g or action_up == g:
  44. found = True
  45. q.clear()
  46.  
  47. visited.clear()
  48.  
  49. count = 0
  50. u1 = g
  51.  
  52. if found == True:
  53. while 1:
  54.  
  55. u1 = path[u1]
  56. count = count +1
  57.  
  58. if u1==s:
  59. break
  60.  
  61. print(count)
  62. else:
  63. print('use the stairs')
  64.  
  65.  
  66. #1 <= s, g <= f <= 1000000 and 0 <= u, d <= 1000000
  67. f, s, g, u ,d = map(int,read().split())
  68.  
  69.  
  70. if s == g:
  71. print('0')
  72. elif s > g and d == 0: #This case Source > Des and down = 0 No way for coming down.
  73. print('use the stairs')
  74. elif s < g and u == 0 : #This case Source < Des and up = 0 No way for coming up.
  75. print('use the stairs')
  76. else:
  77. bfs(f, s, g, u ,d)
Success #stdin #stdout 0.46s 28384KB
stdin
1000000 1 1000000 1 1
stdout
999999