BOJ 30762 Shall We Play a Game?

문제 링크:

문제 내용

정수 알아맞히기 게임을 하려고 합니다. 당신의 상대는 1 이상 $10^{18}$ 이하의 정수 $n$을 숨기고 있습니다. 당신은 다음의 쿼리를 6번 이하로 하여 $n$의 값을 알아내야 합니다.

• X x: 1 이상 $10^{18}$ 이하의 정수 $x$를 쿼리합니다. 상대는 1 이상 $n$ 이하의 정수 중에서 $x$의 배수의 개수의 비율, 즉 $\frac{\left\lfloor \frac{n}{x} \right\rfloor}{n}$의 값을 기약분수 형태로 당신에게 알려줍니다.

인터랙션

먼저, 플레이할 게임의 수 $g$가 주어집니다. ($1 \le g \le 1000$)

각 게임에 대해, 당신의 프로그램은 X {x의 값}을 출력하여 쿼리를 할 수 있습니다. 인터랙터는 그 결과로 나오는 분수를 {분자} {분모}의 형태로 당신의 프로그램의 입력으로 전달합니다. 쿼리의 형식이 올바르지 않거나, $x$의 값이 범위 밖에 있거나, 쿼리 횟수를 초과했다면 -1을 대신 전달합니다.

$n$의 값을 알아냈다면, N {n의 값}을 출력합니다. 이 출력은 쿼리 횟수에 포함되지 않습니다. 인터랙터는 그 값이 맞다면 Correct, 아니라면 Wrong을 전달합니다. Correct라면 다음 게임을 진행하면 됩니다.

모든 출력 이후에는 flush를 하여야 합니다. -1이나 Wrong을 받았거나, 모든 게임이 종료되었다면 즉시 프로그램을 종료해야 합니다. 그렇지 않으면 TLE, RTE 등의 예상치 못한 채점 결과를 받을 수 있습니다.

문제 풀이