SHARE
TWEET

Untitled

a guest Jun 26th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #!/usr/bin/env python3
  2.  
  3. import collections
  4. import sys
  5.  
  6. # Constants
  7.  
  8. INFINITY = float('inf')
  9.  
  10. # Turtle Tuple
  11.  
  12. Turtle = collections.namedtuple('Turtle', 'weight strength capacity')
  13.  
  14. # Compute Weights
  15.  
  16. def compute_weights(turtles):
  17.     # TODO: 1. Insert sentinel/padding into list of turtles
  18.     table = [[INFINITY for i in range(len(turtles)+1)] for j in range(len(turtles)+1)]
  19.     n = len(turtles)
  20.     # TODO: 2. Initialize weights table:
  21.     #
  22.     #   Weights(i, j) = Minimum weight of selecting j turtles from first i turtles
  23.     #
  24.     # By default, we set Weights(i, j) to INFINITY
  25.  
  26.     # If we can select no turtles (j == 0), then minimum weight is 0
  27.  
  28.     # TODO: 3. Construct table to minimize weight of selecting j turtles from
  29.     # the first i turtles:
  30.     #
  31.     #   If Turtle(i)'s capacity >= Weights(i - 1, j - 1) Then
  32.     #       Weights(i, j) = Min(Weights(i - 1, j),
  33.     #                           Weights(i - 1, j - 1) + Turtles[i].weight)
  34.     #   Otherwise
  35.     #       Weights(i, j) = Weights(i - 1, j)
  36.     for i in range(n):
  37.         for j in range(n):
  38.            if j == 0:
  39.               table[i][j] = 0
  40.               continue
  41.            if turtles[i].capacity >= table[i-1][j-1]:
  42.               table[i][j] = min(table[i-1][j], table[i-1][j-1] + turtles[i].weight)
  43.            else:
  44.               table[i][j] = table[i-1][j]
  45.     # TODO: 4. Return table of weight
  46.     return table
  47. # Count turtles
  48.  
  49. def determine_count(Turtles, Weights):
  50.     # TODO: Determine number of turtles in stack
  51.     count = 0
  52.     bottom_row = len(Turtles) - 1
  53.     for turtle in Weights[bottom_row]:
  54.         if turtle != INFINITY:
  55.            count += 1
  56.     return count
  57. # Main execution
  58.  
  59. if __name__ == '__main__':
  60.     Numbers = map(lambda line: list(map(int, line.split())), sys.stdin)
  61.     Turtles = map(lambda args: Turtle(args[0], args[1], args[1] - args[0]), Numbers)
  62.     Turtles = sorted(Turtles, key=lambda x: x.capacity)# TODO: Sort turtles by capacity
  63.     Weights = compute_weights(Turtles)
  64.     Count   = determine_count(Turtles, Weights)
  65.     print(Count)
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