Advertisement
Guest User

k

a guest
Dec 18th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.59 KB | None | 0 0
  1. inp = open("nice.in", 'r')
  2. out = open("nice.out", 'w')
  3.  
  4. def kek(x, y, l):
  5.         x = bin(x)[2:]
  6.         y = bin(y)[2:]
  7.         while len(x) != l:
  8.                 x = '0' + x
  9.         while len(y) != l:
  10.                 y = '0' + y
  11.         for i in range(0, len(x) - 1):
  12.                 if ((x[i] == '1') and (x[i] == x[i + 1]) and (y[i] == '1') and (y[i] ==  y[i + 1])) or ((x[i] == '0') and (x[i] == x[i + 1]) and (y[i] == '0') and (y[i] == y[i + 1])):
  13.                         return False
  14.         return True
  15.  
  16. s = inp.readline()
  17. a = s.split()
  18. n = int(a[0])                                   # n - высота прямоугольника
  19. m = int(a[1])                                           # m - длина
  20. if n > m:
  21.         n, m = m, n
  22.  
  23. amount = 2 ** n
  24. dp = [[0] * amount for i in range(amount)]          # dp - 0 = невозможно перейти от столбца i к j, а 1 = возможно
  25. for i in range(amount):                                 #заполнение массива dp
  26.     for j in range(amount):
  27.         if kek(i, j, n):
  28.             dp[i][j] = 1
  29.         else:
  30.             dp[i][j] = 0
  31. count = [[0] * amount for i in range(m)]        #количество раскрасок, кончающихся m-тым столбиком
  32. for i in range(amount):
  33.     count[0][i] = 1
  34. for k in range(1, m):
  35.     for i in range(amount):
  36.         for j in range(amount):
  37.             if dp[i][j] == 1:
  38.                 count[k][i] += count[k - 1][j]
  39. answer = 0
  40. for i in range(amount):
  41.     answer += count[m - 1][i]
  42. out.write(str(answer))
  43.  
  44. inp.close()
  45. out.close()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement