Editorial for CPC '21 Contest 1 P1 - AQT and Fractions


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

The number of possible inputs is very small in this subtask. Here are some solutions:

  • The only time when the digits infinitely repeat is when B=3 and A \neq 3, so we can just check for this specific case and use something like the to_string(int) method in C++ to count the number of digits past the decimal.
  • Hard code every possible input.

Subtask 2

B is always a multiple of 10, so the decimal will never repeat infinitely, so we can convert the fraction to a string and just check the number of digits. Note that we cannot simply just count the number of digits in B, as the fraction may not be completely reduced. Make sure to be careful about precision (i.e. using arbitrary precision integers).

Time Complexity: \mathcal{O}(\log(\max(a,b))) per test case.

Subtask 3

This subtask exists to reward solutions that would get full marks but fail due to precision or overflow errors.

Subtask 4

One possible solution is to observe that a finite decimal value for \frac{A}{B} can only get so long with the input constraints, so we can perform long division to find the value of \frac{A}{B} and assume that the answer is infinite if our decimal gets too long.

Time Complexity: \mathcal{O}(\log^2(\max(a,b))) per test case.

Alternatively, start by assuming that \frac{A}{B} is fully reduced (if it is not the case, reduce the fraction first). Next, notice the following:

  • The only way for the decimal to be finite is if B = 2^a \cdot 5^b for some a,b \in \mathbb Z where a,b \ge 0.
  • Again let B = 2^a \cdot 5^b where a,b \in \mathbb Z and a,b \ge 0. The number of digits to the right of the decimal is always \max(a,b). We can show that this is true with the following:
    • Let c=a-\min(a,b) and d=b-\min(a,b). We can rewrite B as 10^{\min(a,b)} \cdot 2^c \cdot 5^d and notice that either c=0 or d=0 (or both).
    • Every power of 10 (the 10^{\min(a,b)} portion) adds 1 additional digit by 'shifting' the current decimal to the right.
    • Every additional power of 2 or 5 (either c or d respectively) will always increase the number of digits by 1 as the fraction is already reduced.
    • Thus, if c \neq 0 the number of digits is \min(a,b)+c, otherwise the number of digits is \min(a,b)+d, which is equivalent to \max(a,b).

Overall, this solution leads to a simpler implementation.

Time Complexity: \mathcal{O}(\log(\max(a,b))) per test case.


Comments


  • 0
    tortle  commented on July 29, 2021, 4:49 p.m.

    Could someone explain why dividing by 2 or 5 increases the digits after the decimal point by 1? (given that the original number without the decimal point has no factor of 2 or 5)

    If there were just one non-zero digit after the decimal point, I could see why this would be true, since I could literally just test out the possible digits.

    But I can't seem to convince myself of this when multiple non-zero digits are involved; for example, I know that if we have 0.01 divided by 2 the 1 gets "halved" and we get 0.005; but where x is a placeholder for some nonzero digit, if we divide x.x1 by 2, the 1 getting "halved" contributes a 0.005, but the other nonzero digits also get "halved," so what's to keep those contributions from adding enough to the thousandths place that the last 5 ticks up to a bigger (more to the left) place? [I hope that made sense lol]