class Solution(object):
def distributeCandies(self, candies):
"""
:type candies: List[int]
:rtype: int
"""
kind = set()
for c in candies:
n = len(candies)/2
if (n<=len(kind)):
return n
else:
return len(kind)


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def check(s, t):
if (s and not t) or (not s and t):
return False
if not s and not t:
return True
return s.val==t.val and check(s.right, t.right) and check(s.left, t.left)

def dfs(s, t):
if not s:
return
if s.val==t.val and check(s, t):
raise 'Found'
else:
dfs(s.right, t)
dfs(s.left, t)

try:
dfs(s, t)
except:
return True
return False


pi = sum(2dist(tree, nuts[j]): all j)-dist(tree, nuts[i])+dist(squirrel, nuts[i])

class Solution(object):
def minDistance(self, height, width, tree, squirrel, nuts):
"""
:type height: int
:type width: int
:type tree: List[int]
:type squirrel: List[int]
:type nuts: List[List[int]]
:rtype: int
"""
path = []
tx, ty = tree
sx, sy = squirrel
for x, y in nuts:
p = abs(tx-x)+abs(ty-y)
path.append(p)
s = 2*sum(path)
ans = 2 ** 31
for i in xrange(len(nuts)):
x, y = nuts[i]
p = abs(sx-x)+abs(sy-y)
ans = min(ans, s-path[i]+p)
return ans


dp(k, i, j) = dp(k-1, i-1, j) + dp(k-1, i+1, j) + dp(k-1, i, j-1) + dp(k-1, i, j+1)

class Solution(object):
def findPaths(self, m, n, N, x, y):
"""
:type m: int
:type n: int
:type N: int
:type i: int
:type j: int
:rtype: int
"""
def init(x, y):
ans = 0
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx = x+dx
ny = y+dy
if nx<0 or nx>=m or ny<0 or ny>=n:
ans += 1
return ans
ans = 0
s = [[0]*n for _ in xrange(m)]
for i in xrange(n):
s[0][i] = init(0, i)
s[m-1][i] = init(m-1, i)
for i in xrange(m):
s[i][0] = init(i, 0)
s[i][n-1] = init(i, n-1)

for _ in xrange(N):
ans = (ans+s[x][y]) % (10**9+7)
t = [[0]*n for _ in xrange(m)]
for i in xrange(m):
for j in xrange(n):
for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
ni = i+di
nj = j+dj
if ni<0 or ni>=m or nj<0 or nj>=n:
continue
t[ni][nj] = (t[ni][nj]+s[i][j]) % (10**9+7)
s = t
return ans