HackerRank Geometry – Solve Equations

Challenge: Solve Equations

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464740462

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/solve-equations/problem

Cerinta

You are given a straight line, $a \cdot x + b \cdot y = c$. Find the point closest to the origin that also satisfies the following properties:  

1. $x$ and $y$ are *integers*.  
2. $x$ is *greater than* zero.  

If more than one solution exists satisfying $1$ and $2$, then choose the point in which $x$ is minimal.  

Given $q$ queries consisting of $a_i$, $b_i$, and $c_i$, find and print the point satisfying the above conditions for each respective query. Each point must be printed on a new line as two space-separated integers denoting the point's respective $x_i$ and $y_i$ values.

**Note:** It is guaranteed that there will always be integral points on the line.

Input Format

The first line contains an integer, $q$, denoting the number of queries.  
Each line $i$ of the $q$ subsequent lines contains three space-separated integers describing the respective values of $a_i$, $b_i$, and $c_i$ for the query.

Output Format

For each query, print $2$ space-separated integers on a new line denoting the respective values of $x_i$ and $y_i$ for the point satisfying the $i^{th}$ query.

Constraints

+ $1 \le q \le 10^5$  
+ $1 \le a \le 10^8$  
+ $1 \le b \le 10^8$  
+ $1 \le c \le 10^8$

Cod sursa

import sys

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def solve_one(a, b, c):
    g, xg, yg = egcd(a, b)
    mul = c // g
    x0 = xg * mul
    y0 = yg * mul

    dx = b // g
    dy = -a // g

    # x = x0 + k*dx > 0 => k >= L
    L = (-x0) // dx + 1

    num = -(x0 * dx + y0 * dy)
    den = dx * dx + dy * dy
    kf = num // den
    kc = -((-num) // den)

    cand = {L, L + 1, kf - 1, kf, kf + 1, kc - 1, kc, kc + 1}

    best = None
    for k in cand:
        if k < L:
            continue
        x = x0 + dx * k
        y = y0 + dy * k
        if x <= 0:
            continue
        d2 = x * x + y * y
        key = (d2, x, y)
        if best is None or key < best[0]:
            best = (key, x, y)

    return best[1], best[2]

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    q = int(data[0])
    out = []
    idx = 1
    for _ in range(q):
        a = int(data[idx]); b = int(data[idx + 1]); c = int(data[idx + 2]); idx += 3
        x, y = solve_one(a, b, c)
        out.append(f"{x} {y}")
    sys.stdout.write('\n'.join(out))

if __name__ == '__main__':
    main()