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.  
  49. data = sys.stdin.readlines()
  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)
  65.         #print answer
  66.         print answer % 1000000007
  67.         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
 
Top