TopCoder problem "NotationLength" used in TCHS SRM 41 (Division I Level Two)



Problem Statement

    NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.



It is known that the binary notation (radix 2) of any integer is at most 4 times as long as the corresponding decimal notation. In this problem, you will examine a similar property for radices other then 2.

You are given an int radix and ints low and high. Calculate the ratio of the length of the radix-based notation to the length of the decimal notation for each integer between low and high, inclusive. Return the average of these ratios.



 

Definition

    
Class:NotationLength
Method:avgRatio
Parameters:int, int, int
Returns:double
Method signature:double avgRatio(int radix, int low, int high)
(be sure your method is public)
    
 

Notes

-Numbers in radix-based notation are represented using the digits from 0 to radix-1, inclusive (uppercase letters A, B, C, ... are used to represent "digits" 10, 11, 12, ...). The number anan-1...a1a0 in radix-based notation corresponds to the number an*radixn + an-1*radixn-1 + ... + a1*radix + a0 in decimal notation. For example, B7F is the 16-based notation of the decimal number 11 * 162 + 7 * 16 + 15 = 2943.
-When calculating notation lengths, numbers must be represented with no extra leading zeros.
-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-high will be between 1 and 1000000, inclusive.
-low will be between 1 and high, inclusive.
-radix will be between 2 and 16, inclusive.
 

Examples

0)
    
16
16
99
Returns: 1.0
Both decimal and hexadecimal notations of each integer between 16 and 99 are exactly 2 characters long, and the ratio of these lengths is 1.
1)
    
3
7
11
Returns: 2.0
|   Decimal notation   |   Ternary notation   |   Lengths ratio  |
|         7            |          21          |        2.0       |
|         8            |          22          |        2.0       |
|         9            |         100          |        3.0       |
|        10            |         101          |        1.5       |
|        11            |         102          |        1.5       |
Average lengths ratio is (2.0+2.0+3.0+1.5+1.5)/5 = 2.0.
2)
    
2
1
31
Returns: 2.4838709677419355
3)
    
8
1313
1313
Returns: 1.0
1313 in decimal notation is 2441 in octal notation.
4)
    
5
1
1000000
Returns: 1.4452407023781983

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7744

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10788&pm=7744

Writer:

Nickolas

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Math