SHARE
TWEET

Untitled

a guest Nov 17th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from sys import stdin
  2. from typing import *
  3.  
  4. dist: Dict[Tuple[int, bool], int] = {}
  5.  
  6. def best_dist(arr, i, s, is_connected):
  7.     if i == len(arr) - 2:
  8.         return s + arr[i + 1] - arr[i]
  9.  
  10.     if (i, is_connected) in dist:
  11.         return dist[(i, is_connected)]
  12.  
  13.     if is_connected:
  14.         connected = best_dist(arr, i + 1, s + arr[i + 1] - arr[i], True)
  15.         not_connected = best_dist(arr, i + 1, s, False)
  16.  
  17.         best = min(connected, not_connected)
  18.  
  19.         dist[(i, is_connected)] = best
  20.         return best
  21.     else:
  22.         best = best_dist(arr, i + 1, s + arr[i + 1] - arr[i], True)
  23.  
  24.         return best
  25.  
  26. def main():
  27.     num_of_nails = int(stdin.readline())
  28.     nails = list(map(int, stdin.readline().split()))
  29.     nails.sort()
  30.  
  31.     print(best_dist(nails, 0, 0, False))
  32.     print(dist)
  33.  
  34.  
  35. if __name__ == "__main__":
  36.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top