PROBLEM LINK
int Elligence; (INTL2019) - CHFEDR
Practice Link
Author: Vishal Gaur
Editorialist: Vishal Gaur
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math, Exponentiation, Digital Root
PROBLEM:
Chef likes strings which contain all vowels. The chef is very confused to form a string as Vowels and Consonants have some cost v and c respectively, associated with them. The absolute values of v and c will always be some power of 5 and 2 respectively. Chef wants to minimize the cost C to form the string. As Chef is fond of exponents and Digital Root so he decided to apply these operations to get the final cost C:
- Find Digital Root of |c|^v.
- Find Digital Root of |v|^c.
Chef wants the minimum of above two as the final cost C of the string.
QUICK EXPLANATION:
The digital root of a power of 2 or 5 is 1, 2, 4, 5, 7, or 8. Digital roots of the powers of 2 progress in the sequence 1, 2, 4, 8, 7, 5. Digital roots of the powers of 5 progress in the sequence 1, 5, 7, 8, 4, 2. This also implies for the Negative Powers of 2 and 5. Digital roots of the negative powers of 2 progress in the sequence 1, 5, 7, 8, 4, 2. Digital roots of the negative powers of 5 progress in the sequence 1, 2, 4, 8, 7, 5. So, simply we have to find digital Roots DR_1 = dr(p_1) where p_1 = (log_2|c| * v) \% 6 and DR_2 = dr(p_2) where p_2 = (log_5|v| * c) \% 6 and Answer is minimum of DR_1 and DR_2.
EXPLANATION:
The digital Roots of power of 2 and 5 can be 1, 2, 4, 5, 7, 8, and they follow a sequence as mentioned above. So dr(2^x) = dr(2^{x \% 6}) and dr(5^y) = dr(5^{y \% 6}).
As mentioned above, how the digital roots progress in the sequence for the powers of 2 and 5. You can notice that the progress of digital root for positive powers of 2 and for negative powers of 5 are same. Similarly for positive powers of 5, they progress same as that for negative powers of 2. For Example:
dr(2^2) =4 and dr(5^{-2}) = 4 , As 5^{-2} = 0.04
dr5^{2} = 7 and dr(2^{-2}) = 7, As 2^{-2} = 0.25
Instead of finding Digital Roots for Negative Powers of 2, we will find Digital Root of corresponding Positive Power of 5 and vice-versa.
So, after finding Digital Roots of v and c print the minimum of both as the solution.
ALTERNATIVE SOLUTION:
An alternative solution can be doing iterative modular exponentiation of v and c by 9. It will finally result in Digital Roots of exponentiation of v and c.
Something like this:
pow(2, abs(v * log(abs(c), 2)), 9)
pow(5, abs(c * log(abs(v), 5)), 9)
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.
Alternative solution can be found here.