1  from lib import *
 2  
 3  input = read_input(2015, 17)
 4  
 5  containers = list(map(int, input.splitlines()))
 6  
 7  dp = {}
 8  
 9  
10  def solve1(i, x):
11      if i == len(containers):
12          return int(x == 0)
13  
14      if (i, x) not in dp:
15          out = solve1(i + 1, x)
16  
17          if containers[i] <= x:
18              out += solve1(i + 1, x - containers[i])
19  
20          dp[(i, x)] = out
21  
22      return dp[(i, x)]
23  
24  
25  print(solve1(0, 150))
26  
27  
28  containers = list(map(int, input.splitlines()))
29  dp = {}
30  
31  
32  def solve2(i, x):
33      if i == len(containers):
34          return None if x else (0, 1)
35  
36      if (i, x) not in dp:
37          out = solve2(i + 1, x)
38  
39          if containers[i] <= x:
40              y = solve2(i + 1, x - containers[i])
41  
42              if y is not None:
43                  l, c = y
44  
45                  l += 1
46  
47                  if out is None or l < out[0]:
48                      out = l, c
49  
50                  elif out is not None and out[0] == l:
51                      out = l, out[1] + c
52  
53          dp[(i, x)] = out
54  
55      return dp[(i, x)]
56  
57  
58  print(solve2(0, 150)[1])