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

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$ $B = 3$ and $A \neq 3$ $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.
Hardcode every possible input.

Subtask 2

$B$ $B$ is always a multiple of $10$ $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$ $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)))$ $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}$ $\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}$ $\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)))$ $O (\log^{2} (max (a, b)))$ per test case.

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

Overall, this solution leads to a simpler implementation.

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

Comments

1

tortle commented on July 29, 2021, 8: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]