SHARE
TWEET

Untitled

a guest Oct 9th, 2012 211 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_set, mem, starting_point
  20.         #print left, right
  21.         #sleep(2)
  22.         if (left, right) in mem_set and steps in mem_set[(left, right)]:
  23.                 return mem_set[(left, right)][steps]
  24.         if right - left == 1:
  25.                 #print 'getting steps for', left, steps, starting_point[left]
  26.                 #print 'got ', mem[left][steps][starting_point[left]], 'steps'
  27.                 return mem[left][steps][starting_point[left]]
  28.                 #return ways(left, starting_point[left], steps)
  29.         val = 0
  30.         split_point =  left + (right - left) / 2
  31.         for i in xrange(steps + 1):
  32.                 t1 = i
  33.                 t2 = steps - i
  34.                 mix_factor = fact[steps] / (fact[t1] * fact[t2])
  35.                 #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)
  36.                 val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)
  37.         mem_set[(left, right)][steps] = val
  38.         return val
  39.        
  40. import sys
  41. from time import sleep, time
  42.  
  43. fact = {}
  44. fact[0] = 1
  45. start = time()
  46. accum = 1
  47. for k in xrange(1, 300+1):
  48.         accum *= k
  49.         fact[k] = accum
  50. #print 'fact_time', time() - start
  51.  
  52. data = sys.stdin.readlines()
  53. num_tests = int(data.pop(0))
  54. for ignore in xrange(0, num_tests):
  55.         n_and_steps = data.pop(0)
  56.         n, steps = map(lambda x: int(x), n_and_steps.split())
  57.         starting_point = map(lambda x: int(x), data.pop(0).split())
  58.         dimensions = map(lambda x: int(x), data.pop(0).split())
  59.         mem = {}
  60.         for di in xrange(n):
  61.                 mem[di] = {}
  62.                 for i in xrange(steps + 1):
  63.                         mem[di][i] = {}
  64.                         ways(di, starting_point[di], i)
  65.         start = time()
  66.         #print 'mem vector is done'
  67.         mem_set = {}
  68.         for i in xrange(n + 1):
  69.                 for j in xrange(n + 1):
  70.                         mem_set[(i, j)] = {}
  71.         answer = set_ways(0, n, steps)
  72.         #print answer
  73.         print answer % 1000000007
  74.         #print time() - start
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top