[UVa] 10090 - Marbles

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 10090 - Marbles
Source            : UVa Online Judge
Category          : Number Theory
Algorithm         : Extended Euclid Algorithm
Verdict           : Accepted

import math
 
def read():
    return map(int, input().split())
 
def LCM(a, b):
    return a * b // math.gcd(a, b)
 
def extended_euclid_algorithm(a, b):
    if b is 0:
        return (1, 0, a)
    else:
        x, y, d = extended_euclid_algorithm(b, a%b)
        x1 = y
        y1 = x - (a // b) * y
        x = x1
        y = y1
        return (x, y, d)
 
def solve():
    while True:
        N = int(input())
        if N is 0:
            return
        c1, n1 = read()
        c2, n2 = read()
        g = math.gcd(n1, n2)
 
        if N % g > 0:
            print("failed")
            continue
 
        a = n1 // g
        b = n2 // g
        c = N // g
 
        x, y, d = extended_euclid_algorithm(a, b)
 
        x *= c
        y *= c
 
        kx = math.ceil(-1.0 * x * g / n2)
        ky = math.floor(1.0 * y * g / n1)
 
        if kx > ky:
            print("failed")
            continue
 
        x1 = x + kx * n2 // g
        y1 = y - kx * n1 // g
        cost1 = c1 * x1 + c2 * y1
 
        x2 = x + ky * n2 // g
        y2 = y - ky * n1 // g
        cost2 = c1 * x2 + c2 * y2
        if cost1 < cost2:
            print("{} {}".format(x1, y1))
        else:
            print("{} {}".format(x2, y2))
    return
 
solve()