Soluție HackerRank pentru Solve Equations, subdomeniul Geometry, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Solve Equations
  • Domeniu: Geometry
  • Limbaj: Python 3

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

Cerință

You are given a straight line, a · x + b · 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 ≤ q ≤ 10^5
+ 1 ≤ a ≤ 10^8
+ 1 ≤ b ≤ 10^8
+ 1 ≤ c ≤ 10^8

Cod sursă

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()
HackerRank Geometry – Solve Equations