시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 504 | 184 | 133 | 38.000% |
컴퓨터가 기본적으로 지원하는 것은 이진수에 기반한 정수 뿐이기 때문에, 이를 이용하여 실수(소수)를 표현하기 위한 방법이 연구되어 왔다. 여러 가지 방법들 중에서 현재는 부동 소수점 방식이 채택되어 널리 사용되고 있다. 하지만 이 방법은 오차 등의 문제가 있는 완벽하지 못한 방법이다.
당신은 실수를 다루는 프로그램을 하나 설계하게 되었는데, 이 프로그램 안에서 기약분수를 이용하여 실수를 표현하기로 하였다. 프로그램을 설계하는 과정에서 실수들의 대소 비교에 대해 살펴보게 되었고, 이 과정에서 한 실수에 가장 가까운 분수가 무엇인지 알아보고 싶어졌다.
기약분수 하나가 주어졌을 때, 이 분수에 가장 가까운 기약분수를 구하는 프로그램을 작성하시오. 가장 가깝다는 말은, 물론 두 분수가 표현하는 실수의 차이가 최소이며, 자기 자신과는 달라야 한다. 또, 그러한 기약분수가 여러 가지인 경우 가장 작은 것이다.
우리가 다루는 분수들은 분모와 분자가 모두 1 이상 32767 이하라고 가정하자. 기약분수란 분모와 분자의 최대 공약수가 1인 분수를 말한다.
첫째 줄에 분수를 표현하는 분자와 분모가 주어진다. 단, 분자는 분모보다 작다.
첫째 줄에 우리가 찾는 분수를 표현하는 분자와 분모를 공백으로 구분해 출력한다.
2 3
21845 32767
Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO October 2005 Contest > Silver ?번