Official

A - Tax Included Price Editorial by evima


Let \(f(A)\) denote the tax-included price of an integer \(A\).


◆Solution 1: Using Periodicity

When \(A\) increases by \(100\), \(\frac{100+t}{100}A\) increases by \(100+t\), so we have \(f(A+100) = f(A) + (100 + t)\).

From this, we can see that the property of whether a positive integer \(x\) can be the tax-included price of some integer has a period of \(100 + t\). For example, if the tax rate is \(3\) percent as in 【Sample Input 2】, the values that cannot be the tax-included price of any integer are:

\[(34,68,102), (137,171,205), (240,274,308), \ldots\]

They start with values less than \(100+t = 103\), \((34,68,102)\), and have a period of \(103\).

In the end, we can solve the problem as follows:

  • Compute \(f(1), \ldots, f(100)\) to find out which of the values at most \(100 + t\) cannot be the tax-included price of any integer.
  • Let us say that the \(N\)-th smallest value that cannot be the tax-included price of any integer is the \(x\)-th value in the \(y\)-th period. Find \(x\) and \(y\) to compute the answer.

This solution solves the problem in \(O(1)\) time.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22160671 (Python, \(O(1)\) time)


◆Solution 2: Using Binary Search by Counting

For example, if the tax rate is \(10\) percent, \(f(100) = 110\). Since different integers are sold for different tax-included prices,

  • there are \(100\) values among \(1, 2, \ldots, 110\) that can be the tax-included price of some integer, and
  • \(10\) values among \(1, 2, \ldots, 110\) that cannot be the tax-included price of any integer.

In this way, we can count the values not exceeding a certain value that cannot be the tax-included price of any integer in \(O(1)\) time: there are \(f(A) - A\) such values not exceeding \(f(A)\).

Using this fact and binary search, we can compute the maximum \(A\) satisfying the following:

  • there are less than \(N\) values not exceeding \(f(A)\) that cannot be the tax-included price of any integer.

We can also see that we can use \(100N\) as the upper limit for this binary search from the above observation. Then, the answer is greater than \(f(A)\) and less than \(f(A+1)\). From the fact that \(f(A+1) \leq f(A) + 2\) under \(t \leq 100\), the answer is \(f(A) + 1\).

This solution solves the problem in \(O(\log N)\) time.

【Sample Implementation】 https://atcoder.jp/contests/arc118/submissions/22160677 (Python, \(O(\log N)\) time)


Regarding Computation Errors

We may not be able to compute \(f(A)\) correctly if we do so in the following manner:

  • first, find \(x = (100+t) / 100 \times A\);
  • then, find \(\lfloor x\rfloor\).

For example, the codes below result in \(x = 112\), which is incorrect.

  • x = int(113 / 100 * 100) in Python;
  • int x = 113 / 100.0 * 100; in C++.

If a real number \(x\) is exactly an integer, \(\lfloor x\rfloor \neq \lfloor x - \varepsilon\rfloor\) holds for any positive integer \(\varepsilon > 0\), so the value \(\lfloor x \rfloor\) may be incorrectly computed even if we compute \(x\) within the absolute error of \(\varepsilon\). This problem cannot be resolved, no matter how much the precision of computation is increased. If we need the exact value after truncating, we need to compute it in a different method.

In this problem and under the constraints, we can compute \(f(A)\) correctly if we do so in the following manner:

  • using integer division rounding down to divide \((100+t)\times A\) by \(100\);
  • calculating \(x = (100+t) / 100 \times A\) as a fraction and then adding a small value before truncating (for example, calculate \(\lfloor x + 0.001\rfloor\) instead of \(\lfloor x\rfloor\)).

posted:
last update: