시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 27 3 2 11.111%

문제

유리수를 표현하기 위해 보통 분수를 사용한다. 분수 a/b에서 a를 분자, b를 분모라고 부르고, a와 b는 모두 정수이다. 분수에서 분모가 너무 큰 숫자이면 수식에서 다루기 힘들어진다. 그래서 수학자들은 분모 b가 매우 큰 분수 a/b가 있을 때, 이를 대신하여 분모가 작은 분수 a1/b1와 a2/b2를 사용한다, 여기서 a1/b1 <= a/b <= a2/b2이고 b1과 b2는 둘 다 특정한 정수 c보다 크지 않아야 한다. (즉, b1,b2 <= c).

분수 a1/b1과 a2/b2를 a/b의 근사치 분수 쌍이라고 하자. 수학자들은 근사치 분수 쌍들 중 두 분수의 차이(즉,  a2/b2-a1/b1 )가 최소가 되는 근사치 분수 쌍을 사용하기를 원한다. 수학자를 도와주기 위해, 주어진 분수에 대해 차이가 최소가 되는 근사치 분수 쌍을 찾는 프로그램을 작성하시오. 

입력

첫째 줄에 세 개의 정수 a, b, c가 주어진다. 이 수들은 0<=a<b<=2*10^9, 1<=c<2*10^9를 만족한다.

출력

첫째 줄에 네 개의 정수 a1, b1, a2, b2를 출력한다. 여기서 a1/b1과 a2/b2는 주어진 분수의 근사치 분수 쌍들 중 그 차이가 최소인 것이어야 하고, a1과 b1이 서로소이고 a2와 b2가 서로소이어야 한다. 단, 값이 0인 분수는 항상 “0 1”을 출력한다.

예제 입력

3 7 4

예제 출력

1 3 1 2

힌트

출처

  • 문제를 번역한 사람: author5