Problem p03160 (python)

Fixed submission:


def min_cost(stones, N):
    space = [0] * N

    for i in range(1, N):
        one = abs(stones[i] - stones[i - 1]) + space[i - 1]
        
        two = 2 ** 31

        if i - 2 >= 0:
            two = abs(stones[i] - stones[i - 2]) + space[i - 2]

        space[i] = min(one, two)

    return space[i]


if __name__ == '__main__':
    N = int(input())
    #stones = list(map(int, input().strip().split()))
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N))
    
    '''
    stones = [30, 10, 60, 10, 60, 50]
    N = 6
    print(min_cost(stones, N))
    

    stones = [10, 30, 40, 20]
    N = 4
    print(min_cost(stones, N))
    '''

Buggy submission (verdict: Runtime Error):
def min_cost(stones, N, k):
    space = [0] * N
    for i in range(1, N):
        minimum = 2 ** 31
        for j in range(1, k + 1):
            cost = 2 ** 31

            if i - j >= 0:
                cost = abs(stones[i] - stones[i - j]) + space[i - j]

            minimum = min(minimum, cost)

        space[i] = minimum

    return space[i]


if __name__ == '__main__':
    N, k = [int(a) for a in input().strip().split()]
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N, k))

Buggy submission (verdict: Runtime Error):
def min_cost(stones, N, k):
    space = [0] * N
    for i in range(1, N):
        minimum = 2 ** 31
        for j in range(1, k + 1):
            cost = 2 ** 31

            if i - j >= 0:
                cost = abs(stones[i] - stones[i - j]) + space[i - j]

            minimum = min(minimum, cost)

        space[i] = minimum

    return space[i]


if __name__ == '__main__':
    N, k = [int(a) for a in input().strip().split()]
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N, k))

Buggy submission (verdict: Runtime Error):
def min_cost(stones, N, k):
    space = [0] * N
    for i in range(1, N):
        minimum = 2 ** 31
        for j in range(1, k + 1):
            cost = 2 ** 31

            if i - j >= 0:
                cost = abs(stones[i] - stones[i - j]) + space[i - j]

            minimum = min(minimum, cost)

        space[i] = minimum

    return space[i]


if __name__ == '__main__':
    N, k = [int(a) for a in input().strip().split()]
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N, k))

Buggy submission (verdict: Runtime Error):
def min_cost(stones, N):
    def jump(stones, index, N):
        if index == N:
            return 0

        if memo[index] != -1:
            return memo[index]

        left = abs(stones[index] - stones[index + 1]) + jump(stones, index + 1, N)

        right = 2 ** 31
        if index + 2 <= N:
            right = abs(stones[index] - stones[index + 2]) + jump(stones, index + 2, N)

        memo[index] = min(left, right)

        return memo[index]

    memo = [-1] * N
    return jump(stones, 0, N - 1)


if __name__ == '__main__':
    N = int(input())
    #stones = list(map(int, input().strip().split()))
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N))
    
    '''
    stones = [30, 10, 60, 10, 60, 50]
    N = 6
    print(min_cost(stones, N))
    

    stones = [10, 30, 40, 20]
    N = 4
    print(min_cost(stones, N))
    '''

Buggy submission (verdict: Runtime Error):
import time

def min_cost(stones, N):
    def jump(stones, index, N):
        if index == N:
            return 0

        if dp[index] != -1:
            return dp[index]

        left = abs(stones[index] - stones[index + 1]) + jump(stones, index + 1, N)

        right = 2 ** 31
        if index + 2 <= N:
            right = abs(stones[index] - stones[index + 2]) + jump(stones, index + 2, N)

        dp[index] = min(left, right)

        return dp[index]

    dp = [-1] * (N + 1)
    return jump(stones, 0, N - 1)


if __name__ == '__main__':
    N = int(input())
    #stones = list(map(int, input().strip().split()))
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N))
    
    '''
    stones = [30, 10, 60, 10, 60, 50]
    N = 6
    print(min_cost(stones, N))

    stones = [10, 30, 40, 20]
    N = 4
    print(min_cost(stones, N))
    '''

Buggy submission (verdict: Runtime Error):

def min_cost(stones, N):
    def jump(stones, index, N):
        if index == N:
            return 0

        if dp[index] != -1:
            return dp[index]

        left = abs(stones[index] - stones[index + 1]) + jump(stones, index + 1, N)

        right = 2 ** 31
        if index + 2 <= N:
            right = abs(stones[index] - stones[index + 2]) + jump(stones, index + 2, N)

        dp[index] = min(left, right)

        return dp[index]

    dp = [-1] * N
    return jump(stones, 0, N - 1)


if __name__ == '__main__':
    N = int(input())
    #stones = list(map(int, input().strip().split()))
    stones = [int(a) for a in input().strip().split()]
    print(min_cost(stones, N))

    



'''
    stones = [30, 10, 60, 10, 60, 50]
    N = 6
    print(min_cost(stones, N))

    stones = [10, 30, 40, 20]
    N = 4
    print(min_cost(stones, N))
'''

Buggy submission (verdict: Runtime Error):
def min_cost(stones, N):
    def jump(stones, index, N):
        if index == N:
            return 0

        if dp[index] != -1:
            return dp[index]

        left = abs(stones[index] - stones[index + 1]) + jump(stones, index + 1, N)

        right = 2 ** 31
        if index + 2 <= N:
            right = abs(stones[index] - stones[index + 2]) + jump(stones, index + 2, N)

        dp[index] = min(left, right)

        return dp[index]

    dp = [-1] * N
    return jump(stones, 0, N - 1)


if __name__ == '__main__':
    N = int(input())
    stones = list(map(int, input().strip().split()))
    print(min_cost(stones, N))


'''
    stones = [30, 10, 60, 10, 60, 50]
    N = 6
    print(min_cost(stones, N))

    stones = [10, 30, 40, 20]
    N = 4
    print(min_cost(stones, N))
'''