1072 - 게임

형택이가 앞으로 더해야 하는 판을 k 라고 할 때, 소수점을 버렸을 때, $\frac{Y+k}{X+k}$ != $\frac{Y}{X}$ 가 되는 가장 큰 정수 k 를 구하는 게 문제죠.

수의 변화가 일어나는 부분은 Y+k 가 2Y 가 되거나, X+k 가 2X 가 되는 경우인데, X만 증가하는 경우(지는 경우)는 없으므로 Y+k 가 2Y에 가까워지면서 $\frac{Y+k}{X+k} > \frac{Y}{X}$ 가 되는 정수 k를 구하면 됩니다.

비례방정식으로 아래처럼 나타낼 수 있습니다
$$ {Y+k} : {X+k} = 2Y : X $$
그리고 여기서 아래 수식을 만족해야 겠죠.
$$\frac{x^2}{\left(99x-100y\right)}\le k \in \mathbb Z$$
근데 수식으로 정리해서 했더니 잘 안되더군요.
답은 바이너리 서치로 해야하나봅니다.

근데 근사값을 계산할 때 주의해야 할 점은 위 식대로라면 k로 인한 차이가 0.01 을 넘기는 부분, 즉 $ \frac{y+mid}{x+mid} - \frac{y}{x} \ge 1e^{-2} $ 가 되어야 하지만,
소수의 부정확성 때문에 양 변에 100을 곱하여 1의 차이로 계산하면 됩니다. 다시 말해, $ 100\frac{y+mid}{x+mid} - 100\frac{y}{x} \ge 1 $ 와 같이 하면 됩니다.