Codeforces #172 Div2 B "Nearest Fraction"
問題
整数 X Y Nが与えられる。
X / Yに最も近い値をA / Bの形で出力しなさい。
ただし、B <= Nに制限される。
候補が2つ以上ある場合、なるべくBの小さいものを、
それでもまだ複数ある場合Aの小さいものを出力しなさい。
制約
1 <= X, Y, N <= 10^5
考えた事
10^5か・・
1 <= B <= N, 1 <= A <= X / Yで全探索したら
計算量でだめだな。
A / B <= X / Yとなるような、最も大きいAから始めよう
ん?そのようなAであれば、
A / B <= X / Y <= (A+1) / Bになるから、
それぞれのBで探索すべきAは2個だけだな、よしいける!
WA
doubleの誤差かな?
じゃあ暫定結果の分数と確かめる分数とX / Yの分数の
分母を合わせちゃって、整数で比較できるようにしよう!
WA
あ、10^5*10^5*10^5でintがオーバーフローしてたは
AC
ソースコード
typedef long long ll; int main() { ll X, Y, N; cin >> X >> Y >> N; ll A = 1, B = 1; // 暫定チャンピオン for( ll b = N; b >= 1; b-- ){ ll a = b * X / Y + 1; // X / Y <= (A+1) / B ll to = B * b * X; // 近づくべき値 ll att = B * Y * a; // 挑戦者の値 ll def = b * Y * A; // チャンピオンの値 if( abs( to - def ) >= abs( to - att ) ){ A = a; B = b; } a = a - 1; // A / B <= X / Y att = B * Y * a; if( abs( to - def ) >= abs( to - att ) ){ A = a; B = b; } } cout << A << '/' << B << endl; }