Official

A - Approximation Editorial by en_translator

For beginners

There are roughly two approaches:

  1. using floating-point number operations (like float, double, or Decimal);
  2. using only integer operations

We will explain these two approaches.

1. Using floating-point number operations

Many languages that comes with floating-point numbers come with round-off or similar functions.

This problem can be solved by using such functions.

Arithmetic operations on floating-point numbers usually involve errors, but (with an straightforward implementation) we can obtain the correct answer.

Outline of proof

There will be a wrong answer if, when you compute the division \(\dfrac AB\), if its actual decimal part is less than \(\dfrac12\) but the computed decimal part is greater than or equal to \(\dfrac12\), or vice versa. (The round function always returns the correct value, putting the error on the input aside.)

\(A\) and \(B\) can be represented correctly in most floating-point number types, so it is only the division that may cause an error.

(As long as it complies IEEE 754) it is guaranteed that the result of a division is always the true value, correctly rounded. Therefore, if there is another floating-point number between the true result of the division and a certain floating-point number \(\alpha\), then the result is never rounded to \(\alpha\).

Under the constraints, we can show that there is always another floating-point number between \(\dfrac AB\) and \(n+\dfrac 12\) for any integer \(n\) (if the significant has a sufficient width), so we can always obtain the correct answer.)

The following is sample code.

#include <iostream>
#include <cmath>

using namespace std;

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

    // Print A / B, rounded off to an integer.
    cout << round(static_cast<double>(A) / B) << endl;

    return 0;
}

A, B = map(int, input().split())

# Print A / B, rounded off to an integer.
print(round(A / B))

2. Using only integer operations

The integer closest to \(\dfrac AB\) is the maximum number not exceeding \(\dfrac AB+\dfrac12\).

Many programming languages provides an operation to find the integer part of a division of an integer by another integer. Thus, we may calculate \(\dfrac AB+\dfrac12=\dfrac{2A+B}{2B}\) rounded down to an integer.

The following is sample code.

#include <iostream>

using namespace std;

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

    // The answer is (2A + B) / 2B, rounded down
    cout << (2 * A + B) / (2 * B) << endl;

    return 0;
}

A, B = map(int, input().split())

$ The answer is (2A + B) / 2B, rounded down
print((2 * A + B) // (2 * B))

Using \(\left\lfloor\dfrac{\lfloor a/b\rfloor}c\right\rfloor=\left\lfloor\dfrac a{bc}\right\rfloor\) or \(\left\lfloor\dfrac{ab+c}a\right\rfloor=b+\left\lfloor\dfrac ca\right\rfloor\) (where \(\lfloor x\rfloor\) denotes the largest integer not exceeding \(x\)), one can also get the correct answer by the following implementation.

#include <iostream>

using namespace std;

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

    // The answer is (A + B / 2) / B, rounded down
    cout << (A + B / 2) / B << endl;

    return 0;
}

A, B = map(int, input().split())

# The answer is (A + B / 2) / B, rounded down
print((A + B // 2) // B)

posted:
last update: