• API
• FAQ
• Tools
• Archive
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.

Top