Official

B - Integer Division Returns Editorial by en_translator


First, we explain ceiling division, and how to do it.
Given an integer \(a\) and \(b\), the ceiling division is an operation that finds \(a \div b\) with fractional part rounded up.

  • For example, if \(a = 7\) and \(b = 3\), we have \(7 \div 3 = 2.3333\dots\); rounding up the fractional part, we obtain \(3\).

On the other hand, the / operator (division operator, // in Python) basically does truncating division. (Precisely speaking, this is true when \(a\) and \(b\) are positive. Details are explained later.) So an additional care is required when using / to do ceiling division.

For simplicity, we first describe cases where \(a \geq 0\) and \(b \gt 0\). Let

  • \(\lceil x \rceil\) be the minimum integer not less than \(x\), and
  • \(\lfloor x \rfloor\) be the maximum integer not greater than \(x\).

If \(x\) is positive, \(\left \lceil x \right \rceil\) corresponds to rounding down the fractional part of \(x\), and \(\left \lfloor x \right \rfloor\) to rounding up. (This is not true for negative values. Details are explained later.) We can also assert the following equality. (Proof omitted.)

\[\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor\]

Using this equation, one can implement ceiling division \(a \div b\) by

(a + b - 1) / b

namely, by adding \((b-1)\) and \(a\) before performing floor division. This expression (a + b - 1) / b is very frequently used, so learn it if you did not know.

If \(a\) is positive, it is no problem to use the expression above, but in this problem, \(a\) can be negative, which is an issue; because there are two ways of negative flooring division.
“Truncating the fractional part of \(x\)” can be interpreted in the following to ways:

  1. Computing \(\lfloor x \rfloor\).
  2. Discarding the fractional part.

If \(x\) is positive, these interpretations yield the same result. For example, truncating \(3.7\) yields the same result:

  • \(\lfloor 3.7 \rfloor = 3\), so it yields \(3\).
  • Discarding \(.7\), the value \(3.7\) becomes \(3\).

However, if \(x\) is negative, for example, truncating \(-2.4\) yields different results:

  • \(\lfloor -2.4 \rfloor = -3\), so it yields \(3\).
  • Discarding \(.4\), the value \(-2.4\) becomes \(-2\).

This problem asks to find \(\dfrac{X}{10}\). The equation

\[\left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor\]

which was introduced above is true for both positive and negative \(a\) and \(b\), so one can assign \(a = X\) and \(b = 10\) to get

\[\left \lceil \frac{X}{10} \right \rceil = \left \lfloor \frac{X + 10 - 1}{10} \right \rfloor = \left \lfloor \frac{X+9}{10} \right \rfloor.\]

In this problem, if (X + 9) / 10 is interpreted as “1. computing \(\lfloor x \rfloor\),” then the correct answer is obtained.
However, the rounding-down behavior of truncating division differs language to language:

  1. Computing \(\lfloor x \rfloor\) \(\to\) adopted by Python.
  2. Discarding the fractional part \(\to\) adopted by C++.

Therefore, the answer code may be different for languages other than explained in this editorial. If you use them, do search which behavior your language adopts.
In this editorial, we explain solutions in Python and C++.

In Python

Python computes \(\lfloor x \rfloor\) when performing truncating division.

See also: Python Language Reference, 6.7 Binary arithmetic operations

Therefore, we can just naturally implement the code to solve this problem.

  • Sample code
X = int(input())
print((X + 9) // 10)

By the way, some users might write the following code using math.ceil function, but this is wrong. (Indeed, this will not give the correct answer for Sample Input / Output 5).

  • Wrong code
import math

X = int(input())
print(math.ceil(X / 10))

This is because, the result of \(X / 10\) is of float type, which may contain computational errors.
General decimal types (double-precision floating point number type) has a precision of only about \(53\) binary digits (or about \(16\) decimal digits). Thus, if you try to compute large numbers like \(10^{18}\), a precision error prevent you from getting the correct value.
In general, it is discouraged to use float type to compute flooring/ceiling division, as it may cause a bug in the future. To avoid effects of errors, do try to use only integer types when doing flooring/ceiling divisions.

In C++

The C++ standard (precisely, C++11 or later) specifies that division is obtained as the mathematical quotient, ignoring the decimal part. (See also: The Standard : Standard C++) For example, if the quotient is \(-2.4\), it ignores the fractional part \(.4\) and returns \(-2\) as the answer. This matches the second pattern, discarding the fractional part, as explained above.
In such an integer division, it yields a value larger by one than \(\lfloor x \rfloor\) when the denominator is negative and there is a remainder.
We can get the correct answer by subtracting the result by one.

  • Sample code
#include <iostream>
using namespace std;

int main() {
  long long X;
  cin >> X;
  if ((X + 9) < 0 and (X + 9) % 10 != 0) {
    cout << (X + 9) / 10 - 1 << endl;
  } else {
    cout << (X + 9) / 10 << endl;
  }
}

This way, the problem as been solved in C++ and Python.

As an easier similar problem, please take a look at ABC239B: Integer Division. If you could not solve this problem, we recommend you to solve it. (Also, note that this editorial uses some parts of the editorial of ABC239B.)

posted:
last update: