Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- inp = open("nice.in", 'r')
- out = open("nice.out", 'w')
- def kek(x, y, l):
- x = bin(x)[2:]
- y = bin(y)[2:]
- while len(x) != l:
- x = '0' + x
- while len(y) != l:
- y = '0' + y
- for i in range(0, len(x) - 1):
- 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])):
- return False
- return True
- s = inp.readline()
- a = s.split()
- n = int(a[0]) # n - высота прямоугольника
- m = int(a[1]) # m - длина
- if n > m:
- n, m = m, n
- amount = 2 ** n
- dp = [[0] * amount for i in range(amount)] # dp - 0 = невозможно перейти от столбца i к j, а 1 = возможно
- for i in range(amount): #заполнение массива dp
- for j in range(amount):
- if kek(i, j, n):
- dp[i][j] = 1
- else:
- dp[i][j] = 0
- count = [[0] * amount for i in range(m)] #количество раскрасок, кончающихся m-тым столбиком
- for i in range(amount):
- count[0][i] = 1
- for k in range(1, m):
- for i in range(amount):
- for j in range(amount):
- if dp[i][j] == 1:
- count[k][i] += count[k - 1][j]
- answer = 0
- for i in range(amount):
- answer += count[m - 1][i]
- out.write(str(answer))
- inp.close()
- out.close()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement