SortEstimate
SRM 230 · 2005-02-08 · by AdminBrett
SRM 230 · 2005-02-08 · by AdminBrett · Math, Search
Problem Statement
Problem Statement
You have implemented a sorting algorithm that requires exactly c*n*lg(n) nanoseconds to sort n integers. Here lg denotes the base-2 logarithm. Given time nanoseconds, return the largest double n such that c*n*lg(n) <= time.
Notes
- lg(n) = ln(n)/ln(2) where ln denotes the natural log.
- Your return value must have a relative or absolute error less than 1e-9.
Constraints
- c will be between 1 and 100 inclusive.
- time will be between 1 and 2000000000 inclusive.
Examples
0)
1 8 Returns: 4.0
Given 8 nanoseconds we can sort 4 integers since 1*4*lg(4) = 4*2 = 8
1)
1 1073741824 Returns: 4.237868701779632E7
2)
1 20971520 Returns: 1048576.0
3)
1 1744830463 Returns: 6.7108863963560425E7
4)
2 16 Returns: 4.0
Now that c = 2 we need twice as many nanoseconds to sort 4 integers.
5)
37 12392342 Returns: 23104.999312341137
We can almost sort 23105 integers, but not quite.
6)
1 2000000000 Returns: 7.637495090348122E7
Largest possible return.
Submissions are judged against all 48 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SortEstimate with a public method double howMany(int c, int time) · 48 test cases · 2 s / 256 MB per case