구슬
시간 제한1초메모리 제한512 MB
빨간 구슬과 초록 구슬의 개수를 r ≤ g이고 총합이 N 이상 M 이하가 되도록 정할 때, 두 개를 뽑아 색이 다를 확률이 정확히 p/q가 되는 해를 총합이 최소인 것으로 구한다.
문제
캠퍼스 봄 축제의 부스에서 Toni는 빨간 구슬과 초록 구슬이 든 그릇에서 구슬 두 개를 뽑는 게임을 하려고 한다. 빨간 구슬 하나와 초록 구슬 하나가 나오면 다음 단계로 넘어간다.
Toni는 빨간 구슬 하나와 초록 구슬 하나를 뽑을 확률을 정확히 정하고 싶어 한다. 확률을 쉽게 짐작하지 못하도록 그릇에 구슬을 충분히 많이 넣고 싶지만, 그릇 크기에 한계가 있어 구슬 개수의 최댓값을 정해야 한다.
그릇에 빨간 구슬과 초록 구슬을 각각 몇 개 넣어야 하는지 구하는 프로그램을 작성하시오.
입력
입력은 공백으로 구분된 네 개의 십진 정수 p, q, N, M을 포함하는 한 줄로 이루어진다. 빨간 구슬의 개수 r과 초록 구슬의 개수 g를 구해야 하며, 다음 조건을 만족해야 한다. r ≤ g, N ≤ (r+g) ≤ M ≤ 1000, 2 ≤ N ≤ 1000이고, (r+g)는 N 이상인 합 중 가장 작다. 또한 그릇에서 구슬을 정확히 두 개 무작위로 뽑을 때 빨간 구슬 하나와 초록 구슬 하나(순서는 상관없다)를 뽑을 확률은 정확히 p/q이다. q > 0이고 GCD(p, q)는 항상 1이다. Toni의 조건을 만족하는 답이 없으면 NO SOLUTION을 출력한다.
출력
출력은 공백으로 구분된 두 십진 정수 r과 g를 한 줄에 출력하거나, 주어진 입력에 대한 답이 없으면 NO SOLUTION을 출력한다.