公式

B - Integer Division 解説 by en_translator


The theme of this problem is whether you can properly implement floor division, which is frequently used in competitive programming. If you couldn’t solve this problem or spent a lot of time, take this opportunity to learn how to implement floor division correctly.

Let’s put aside the detailed description; there are two main key points.

1. Don’t use decimals

This is a common mistakes for Python users. Some of them tries to compute floor divisions via decimals, like C = int(A / B). At a glance this seems correct, but you should avoid this as much as possible, as this will lead to a bug sooner or later.

General floating point number types like float in Python and double in C++ have a precision of at most (\(53\) binary digits) \(\simeq\) (\(16\) decimal digits). Thus, trying to compute a large number like \(10^{18}\) causes a precision error, yielding a wrong result.

n1 = 10**18 - 42
n2 = int(float(n1))
print(n1) #  999999999999999958 が出力される
print(n2) # 1000000000000000000 が出力される

2. Beware of negative divisions

In this problem, \(X\) can be down to \(-10^{18}\), i.e. the divisor may be negative. It seems that there is no difference from positive divisor, but in fact there is a big issue that there are multiple definitions of negative divisions depending on programming language.

  • We’ll explain the details later. For example, the integer division where \(-24\) is the dividend and \(10\) is the divisor results in \(-2\) or \(-3\) depending on languages.

If “the intended behavior of negative divisions” and “the actual behavior of the division” are different, some of you may have trouble with figuring out what is wrong with their WA (Wrong Answer) code.

As in these examples, it is a very common mistake to write a buggy code believing that you are doing the right thing, without noticing that the intended and actual behavior are different.
There is a famous programmer’s meme: “the code does not work as intended; it work as written.” In other words, “if you mistakenly write a code in a wrong way, it won’t work as intended.” It’s natural in a sense, but cannot be underestimated, as most of bugs in the world are actually based on such wrong assumption.
Also, if you can learn through the experience in competitive programming how to figure out the mistakes in your code by comparing the “intended behavior” and “actual behavior”, you will be able to implement wider range of programs.

Well, let’s get down to the details. Because of 2., this problem has different solutions in different languages. In this editorial we will introduce solutions in C++ and Python. If you are using other languages, we recommend you to find out the way by checking out the submissions by top participants in “Results” tab above.

Python

In Python, you can write just like this:

X = int(input())
print(X // 10)

This is because the floor division operator // in Python is defined to be the floored fraction, where floor function is the same as defined in the problem statement, \(\lfloor \ \rfloor\).

See also: Python Language Reference, 6.7 Binary Arithmetic Operations

print(47 // 10)   # outputs 4 
print(-24 // 10)  # outputs -3

Therefore, this problem can be solved by naturally implementing using //.

In general, if you want to compute floor division of A by B, you can write as A // B and it will work properly. If you always use int(A / B), we recommend you to use A // B from now on.

C++

The problem is in C++. In C++, / is a floor division operator, but in fact you cannot directly use this.
Here is a sample code that executes the division in the Samples.

#include <iostream>
#include <iostream>
using namespace std;

int main() {
  cout << 47 / 10 << endl;  // outputs 4
  cout << -24 / 10 << endl; // outputs -2
}

Why -24 / 10 results in -2? Because divisions in C++ (precisely speaking, C++11 and later) are defined to be “the mathematical quotient ignoring the fractional part”.

  • In -24/10 for example, \(-24/10 = -2.4\). Removing \(.4\) results in \(-2\), which is the answer.

See also: C++ International Standard

Due to the reason described above, in the integral division in C++, the result is rounded up instead of rounded down when “the divisor is negative” and “the remainder is non-zero”. In such case, subtracting \(1\) from the result yields the right answer.

Therefore, the following code will be AC (Accepted) for this problem.

#include <iostream>
using namespace std;

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

An alternative way is to use modulo operator %. In C++, % is defined to be an operator satisfying (a / b) * b + a % b = a, so the quotient is rounded down only if “a % b is negative”.

Therefore, the following code will be AC too.

#include <iostream>
using namespace std;

int main() {
  long long X;
  cin >> X;
  cout << X / 10 - (X % 10 < 0) << "\n";
}

Generally, the floor division of A by B is obtained as

  • A / B if both A and B are positive;
  • A / B - (A % B < 0) if A or B may be negative.

We think it is worth remembering.

That’s all for the editorial. The problem may have been difficult in a different way as usual, but floor division has been appeared, and will appear many times, so we’d be happy to take this chance to learn it.

投稿日時:
最終更新: