【AtCoder】ABC 407 A - Approximation | 緑コーダーが解くAtCoder

atcoder.jp

配点: 150 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 26 / NoviSteps: 7Q

問題概要
制約
考察
実装例
コメント

問題概要

正整数 $A$ と正の奇数 $B$ が与えられるので、実数 $\dfrac{A}{B}$ との差が最小となる整数を出力せよ。

制約

$1\leq A, B\leq407$
入力は全て整数

考察

答えの候補となる整数は、 $\left\lfloor \dfrac{A}{B} \right\rfloor$ と $\left\lceil \dfrac{A}{B} \right\rceil$ の2つである。

したがって、実数 $\dfrac{A}{B}$ とこれら2整数との差の絶対値をそれぞれ計算し、小さい方を答えとして出力すればよい。

実装例において、床関数と天井関数については以下の記事で紹介したものを使っている。

yuulis.hatenablog.com

実装例

#include <bits/stdc++.h>
using namespace std;

template <class T1, class T2>
inline auto div_floor(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a >= 0)
        return a / b;
    else
        return (a + 1) / b - 1;
}
template <class T1, class T2>
inline auto div_ceil(T1 a, T2 b)
{
    if (b < 0)
        a *= -1, b *= -1;
    if (a <= 0)
        return a / b;
    else
        return (a - 1) / b + 1;
}

// ======================================== //

int main()
{
    int A, B;
    cin >> A >> B;

    double div = (double)A / B;

    int x = div_floor(A, B);
    int y = div_ceil(A, B);

    if (abs(div - x) <= abs(div - y))
    {
        cout << x << endl;
    }
    else if (abs(div - x) > abs(div - y))
    {
        cout << y << endl;
    }

    return 0;
}