Problem p03061 (python)

Fixed submission:
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

for i in range(2, N+1):
    memo[(0, i)] = gcd(memo[(0, i - 1)], nums[i-1])
    # print("{} {} memo:{}".format(0, i, memo[(0,i)]))


for i in reversed(range(0, N-1)):
    memo[(i, N)] = gcd(memo[(i + 1, N)], nums[i])
    # print("{} {} memo:{}".format(i, N, memo[(i,N)]))

res = 1
for i in range(1, N-1):
    res = max(res, gcd(memo[(0, i)], memo[(i+1, N)]))
    # print("gcd:{}".format(gcd(memo[(0, i)], memo[(i+1, N)])))

res = max(res, memo[(0, N-1)])
res = max(res, memo[(1, N)])

print(res)

Buggy submission (verdict: Runtime Error):
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    if (div == 0):
        return y
    while div != 0:
        div = x % y
        x = y
        y = div
    return x

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

def solve(left, right):
    if (left, right) in memo:
        return memo[(left, right)]
    if left == 0:
        sol = gcd(nums[right - 1], solve(left, right - 1))
        memo[(left, right)] = sol
        return sol
    if right == N:
        sol = gcd(nums[left], solve(left+1, right))
        memo[(left, right)] = sol
        return sol

res = 1
for i in range(1, N-1):
    res = max(res, gcd(solve(0, i), solve(i+1, N)))

res = max(res, solve(0, N-1))
res = max(res, solve(1, N))

print(res)

Buggy submission (verdict: Runtime Error):
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    if (div == 0):
        return y
    while div != 0:
        div = x % y
        x = y
        y = div
    return x

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

def solve(left, right):
    if (left, right) in memo:
        return memo[(left, right)]
    if left == 0:
        sol = gcd(nums[right - 1], solve(left, right - 1))
        memo[(left, right)] = sol
        return sol
    if right == N:
        sol = gcd(nums[left], solve(left+1, right))
        memo[(left, right)] = sol
        return sol

res = 1
for i in range(1, N-1):
    res = max(res, gcd(solve(0, i), solve(i+1, N)))

res = max(res, solve(0, N-1))
res = max(res, solve(1, N))

print(res)

Buggy submission (verdict: Runtime Error):
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    if (div == 0):
        return y
    while div != 0:
        div = x % y
        x = y
        y = div
    return x

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

def solve(left, right):
    if (left, right) in memo:
        return memo[(left, right)]
    if left == 0:
        sol = gcd(nums[right - 1], solve(left, right - 1))
        memo[(left, right)] = sol
        return sol
    if right == N:
        sol = gcd(nums[left], solve(left+1, right))
        memo[(left, right)] = sol
        return sol

res = 1
for i in range(1, N-1):
    res = max(res, gcd(solve(0, i), solve(i+1, N)))

res = max(res, solve(0, N-1))
res = max(res, solve(1, N))

print(res)

Buggy submission (verdict: Runtime Error):
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x,y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    if div:
        return gcd(div, y)
    else:
        return y

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

def solve(left, right):
    if (left, right) in memo:
        return memo[(left, right)]
    if left == 0:
        sol = gcd(nums[right - 1], solve(left, right - 1))
        memo[(left, right)] = sol
        return sol
    if right == N:
        sol = gcd(nums[left], solve(left+1, right))
        memo[(left, right)] = sol
        return sol

res = 1
for i in range(1, N-1):
    res = max(res, gcd(solve(0, i), solve(i+1, N)))

res = max(res, solve(0, N-1))
res = max(res, solve(1, N))

print(res)

Buggy submission (verdict: Runtime Error):
N=int(input())
nums = [int(i) for i in input().split()]

def gcd(x,y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    if div:
        return gcd(div, y)
    else:
        return y

memo = {}
memo[(0, 1)] = nums[0]
memo[(N-1, N)] = nums[N-1]

def solve(left, right):
    if (left, right) in memo:
        return memo[(left, right)]
    if left == 0:
        sol = gcd(nums[right - 1], solve(left, right - 1))
        memo[(left, right)] = sol
        return sol
    if right == N:
        sol = gcd(nums[left], solve(left+1, right))
        memo[(left, right)] = sol
        return sol

res = 1
for i in range(1, N-1):
    res = max(res, gcd(solve(0, i), solve(i+1, N)))

res = max(res, solve(0, N-1))
res = max(res, solve(1, N))

print(res)