時間制限:1000ミリ秒
メモリ制限65536:KB
問題
5年生の教育さえも受けていないので、牛達には分数の問題は難しい。助けてあげてほしい。問題は簡単だ。
既約分数(分子と分母の最大公約数が1なのでこれ以上約分できない)が与えられる。それに一番近い(等しくはない)既約分数で分母が1から32767までの範囲のもののうち、最小のものを求めよ。
入力
1行目にスペース区切りの二つの整数N,D(1<=N<D<=32767)が与えられ、それぞれ分子と分母である。
出力
1行目にスペース区切りの二つの整数を、それぞれが入力とは異なるが一番近い一番小さい分数の分子と分母になるように出力せよ。
入力の例
2 3
出力の例
21845 32767
ヒント
入力:2/3
出力:21845/32767 = .666676839503.... ~ 0.666666.... = 2/3
出典
USACO 2005 October Silver