HardIneq
SRM 132 · 2003-02-01 · by PabloGilberto
SRM 132 · 2003-02-01 · by PabloGilberto
Problem Statement
Problem Statement
A very famous algorithms text presents its readers with a seemingly simple math problem in its opening chapter:
Find the smallest positive integer value of n such that a*(n^k) < k^n, where a and k are given integral values and ^ denotes exponentiation.
Solving this problem algebraically involves using the overly complicated Lambert W function. Instead you are to solve the problem by creating a class HardIneq with a method biggestVal which, given a and k, returns the smallest positive integer value of n such that a*(n^k) < k^n.
Find the smallest positive integer value of n such that a*(n^k) < k^n, where a and k are given integral values and ^ denotes exponentiation.
Solving this problem algebraically involves using the overly complicated Lambert W function. Instead you are to solve the problem by creating a class HardIneq with a method biggestVal which, given a and k, returns the smallest positive integer value of n such that a*(n^k) < k^n.
Notes
- Remember that log(x^y) = y * log(x) and that log(x*y) = log(x) + log(y)
Constraints
- a will be between 1 and 10000, inclusive
- k will be between 2 and 1000, inclusive
Examples
0)
10 5 Returns: 8
if n = 1, we have a*(n^k) = 10*(1^5) = 10, and k^n = 5^1 = 5. 10 is not less than 5. n=2: 10*2^5 is not less than 5^2 n=2: 10*3^5 is not less than 5^3 and so on. Not until we get to n = 8, and have 10*8^5 = 327680, and 5^8 = 390625 is the inequality satisfied.
1)
1 2 Returns: 1
1*(1^2) is less than 2^1, so we return 1.
2)
2 20 Returns: 1
3)
2000 200 Returns: 202
4)
1000 100 Returns: 102
61)
27 3 Returns: 10
Note that 27*9^3 is equal to 3^9.
Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HardIneq with a public method int biggestVal(int a, int k) · 67 test cases · 2 s / 256 MB per case