# Gearing Up for Destruction
# ==========================

# As Commander Lambda's personal assistant, you've been assigned the task of configuring the LAMBCHOP doomsday device's axial orientation gears. It should be pretty
# simple - just add gears to create the appropriate rotation ratio. But the problem is, due to the layout of the LAMBCHOP and the complicated system of beams and pipes supporting it,
# the pegs that will support the gears are fixed in place.

# The LAMBCHOP's engineers have given you lists identifying the placement of groups of pegs along various support beams. You need to place a gear on each peg (otherwise the gears
# will collide with unoccupied pegs). The engineers have plenty of gears in all different sizes stocked up, so you can choose gears of any size, from a radius of 1 on up. Your goal
# is to build a system where the last gear rotates at twice the rate (in revolutions per minute, or rpm) of the first gear, no matter the direction. Each gear (except the last)
# touches and turns the gear on the next peg to the right.

# Given a list of distinct positive integers named pegs representing the location of each peg along the support beam, write a function answer(pegs) which, if there is a solution,
# returns a list of two positive integers a and b representing the numerator and denominator of the first gear's radius in its simplest form in order to achieve the goal above,
# such that radius = a/b. The ratio a/b should be greater than or equal to 1. Not all support configurations will necessarily be capable of creating the proper rotation ratio, so if
# the task is impossible, the function answer(pegs) should return the list [-1, -1].

# For example, if the pegs are placed at [4, 30, 50], then the first gear could have a radius of 12, the second gear could have a radius of 14, and the last one a radius of 6. Thus,
# the last gear would rotate twice as fast as the first one. In this case, pegs would be [4, 30, 50] and answer(pegs) should return [12, 1].

# The list pegs will be given sorted in ascending order and will contain at least 2 and no more than 20 distinct positive integers, all between 1 and 10000 inclusive.

from fractions import Fraction

def invert(matrix):
    n = len(matrix)
    inverse = [[Fraction(0) for col in range(n)] for row in range(n)]

    for i in range(n):
        inverse[i][i] = Fraction(1)

    for i in range(n):
        for j in range(n):
            if i != j:
                if matrix[i][i] == 0:
                    return false
                ratio = matrix[j][i] / matrix[i][i]
                for k in range(n):
                    inverse[j][k] = inverse[j][k] - ratio * inverse[i][k]
                    matrix[j][k] = matrix[j][k] - ratio * matrix[i][k]

    for i in range(n):
        a = matrix[i][i]
        if a == 0:
            return false
        for j in range(n):
            inverse[i][j] = inverse[i][j] / a
    return inverse



def answer(pegs):
    # your code herel


    if len(pegs) == 2:
        radius_second = (Fraction(pegs[1] - pegs[0]) / Fraction(3))

        if radius_second<1:
            return [-1,-1]

        radius_first = radius_second * Fraction(2)


        return [radius_first.numerator, radius_first.denominator]



    distance = [0] * (len(pegs)-1)



    for i in xrange(0,len(pegs)-1):
        distance[i] = pegs[i+1] - pegs[i]

    #radius = np.linalg.solve(build_matrix(len(pegs)-1), distance)

    a = build_matrix(len(pegs)-1)
    a_inv = invert(a)


    radius_list = []
    for i in range(0, len(a_inv)):
        current_gear_radius = 0
        for j in range(0, len(a_inv[i])):
            current_gear_radius += a_inv[i][j] * distance[j]
        radius_list.append(current_gear_radius)

    for radius in radius_list:
        if radius<1:
            return [-1, -1]

    first_gear_radius = radius_list[-1] * Fraction(2)



    return first_gear_radius.numerator,first_gear_radius.denominator

def build_matrix(n):
    mat = [[0 for x in range(n)] for y in range(n)]

    mat[0][0] = 1
    mat[0][n-1] = 2

    for i in range(1,n):
        mat[i][i-1] = 1
        mat[i][i] = 1

    return mat

print answer([4,30,50])