• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Oct 9th, 2012 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. def ways(di, offset, steps):
2.         global mem, dimensions
3.         if steps in mem[di] and offset in mem[di][steps]:
4.                 return mem[di][steps][offset]
5.         val = 0
6.         if steps == 0:
7.                 val = 1
8.         else:
9.                 if offset - 1 >= 1:
10.                         val += ways(di, offset - 1, steps - 1)
11.                 if offset + 1 <= dimensions[di]:
12.                         val += ways(di, offset + 1, steps - 1)
13.         mem[di][steps][offset] = val
14.         return val
15.
16.
17. def set_ways(left, right, steps):
18.         # must create t1, t2, t3 .. ti for steps
19.         global mem, starting_point
20.         #print left, right
21.         #sleep(2)
22.         if right - left == 1:
23.                 #print 'getting steps for', left, steps, starting_point[left]
24.                 #print 'got ', mem[left][steps][starting_point[left]], 'steps'
25.                 return mem[left][steps][starting_point[left]]
26.                 #return ways(left, starting_point[left], steps)
27.         val = 0
28.         split_point =  left + (right - left) / 2
29.         for i in range(steps + 1):
30.                 t1 = i
31.                 t2 = steps - i
32.                 mix_factor = fact[steps] / (fact[t1] * fact[t2])
33.                 #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)
34.                 val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)
35.         return val
36.
37. import sys
38. from time import sleep, time
39.
40. fact = {}
41. fact[0] = 1
42. start = time()
43. accum = 1
44. for k in range(1, 300+1):
45.         accum *= k
46.         fact[k] = accum
47. #print 'fact_time', time() - start
48.
50. num_tests = int(data.pop(0))
51. for ignore in range(0, num_tests):
52.         n_and_steps = data.pop(0)
53.         n, steps = map(lambda x: int(x), n_and_steps.split())
54.         starting_point = map(lambda x: int(x), data.pop(0).split())
55.         dimensions = map(lambda x: int(x), data.pop(0).split())
56.         mem = {}
57.         for di in range(n):
58.                 mem[di] = {}
59.                 for i in range(steps + 1):
60.                         mem[di][i] = {}
61.                         ways(di, starting_point[di], i)
62.         start = time()
63.         #print 'mem vector is done'
64.         answer = set_ways(0, n, steps)