Problem p03222 (python)

Fixed submission:
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)

DP = [[None] * W for i in range(H)]

def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    if DP[depth - 1][clm - 1] != None: return DP[depth - 1][clm - 1]
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        coeff = possible_route
        if clm > 1: coeff -= raw_route[clm - 1]
        if clm < W: coeff -= raw_route[clm]
        ans += coeff * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    if DP[depth - 1][clm - 1] == None: DP[depth - 1][clm - 1] = ans % (10 ** 9 + 7)
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)

DP = [[None] * W for i in range(H)]

def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    if DP[depth - 1][clm - 1] != None: return DP[depth - 1][clm - 1]
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        if clm == 1: ans += (possible_route - raw_route[clm]) * draw(depth + 1, clm)
        elif clm == W: ans += (possible_route - raw_route[clm - 1]) * draw(depth + 1, clm)
        else: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    if DP[depth - 1][clm - 1] == None: DP[depth - 1][clm - 1] = ans % (10 ** 9 + 7)
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max:
        if clm == 1: ans += (possible_route - raw_route[clm]) * draw(depth + 1, clm)
        elif clm == W: ans += (possible_route - raw_route[clm - 1]) * draw(depth + 1, clm)
        else: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import sys
sys.setrecursionlimit(10000)

H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
H, W, K = map(int, input().split())

raw_route = [0] * W # 0 in unused
possible_route = 0

for i in range(2 ** (W - 1)):
    # check
    i_tmp = i
    last = 0
    for j in range(W - 1):
        if i_tmp % 2 == last == 1: break
        last = i_tmp % 2
        i_tmp = i_tmp // 2
    else:
        # valid drawing
        i_tmp = i
        for j in range(W - 1):
            if i_tmp % 2 == 1: raw_route[j + 1] += 1
            i_tmp = i_tmp // 2
        possible_route += 1

# print("#", raw_route)            
            
def draw(depth, clm):
    # done
    if depth == H + 1: return 1
    # running
    ## param
    range_min = K - (H - depth)
    range_max = K + (H - depth)
    ## calc ans
    ans = 0
    # print("##", depth, clm, (range_min, range_max))
    ### go straight
    if range_min <= clm <= range_max: ans += (possible_route - raw_route[clm - 1] - raw_route[clm]) * draw(depth + 1, clm)
    ### go left
    if range_min <= clm - 1 and 1 <= clm - 1: ans += raw_route[clm - 1] * draw(depth + 1, clm - 1)
    ### go right
    if clm + 1 <= range_max and clm + 1 <= W: ans += raw_route[clm] * draw(depth + 1, clm + 1)
    ## end
    return ans % (10 ** 9 + 7)

print(draw(1, 1))