#P17348. [ECNA 2025] How Many Balls?

[ECNA 2025] How Many Balls?

Problem Description

If a bag contains rr red balls and gg green balls and two balls are drawn at random, the probability of getting one ball of each color is $$P(r, g) = \frac{2rg}{(r+g)(r + g - 1)}$$

Write a program which takes as input a rational number p/qp/q in lowest terms and determines whether there is a number r106r \leq 10^6 and a grg \geq r for which P(r,g)=p/qP(r, g) = p/q.

Input Format

The only line of input contains two space-separated positive integers pp (p>0p > 0) and qq (2p1q10002p - 1 \leq q \leq 1000). These two integers are guaranteed to be relatively prime.

Output Format

If there is a solution, print the two positive integers rr and gg satisfying the conditions above, separated by a space. If there are multiple solutions, output the one with the smallest rr value. For any rr value, there is at most one gg value (grg \geq r), which solves P(r,g)=p/qP(r,g) = p/q. If there is no solution with r106r \leq 10^6, print the word impossible.

12 25
9 16
8 25
impossible