TopCoder Statistics - Problem Statement

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

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.
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

1

31

Returns: 2.4838709677419355
8

1313

1313

Returns: 1.0

1313 in decimal notation is 2441 in octal notation.
5

1

1000000

Returns: 1.4452407023781983
16

386

24642

Returns: 0.8473595250851031
14

31

118

Returns: 0.9280303030303041
7

2544

2794

Returns: 1.25
2

5215

5827

Returns: 3.25
13

16381

18539

Returns: 0.7999999999999704
4

1

73

Returns: 1.547945205479452
16

25956

29620

Returns: 0.8000000000000324
4

23875

28182

Returns: 1.6000000000001093
14

20557

23365

Returns: 0.7999999999999868
5

2590

7930

Returns: 1.47495787305748
15

636

2728

Returns: 0.7934782608695652
11

17171

30865

Returns: 1.0
5

1087

20869

Returns: 1.362432391447795
11

2962

19531

Returns: 0.9439831019914263
8

85

567

Returns: 1.0541752933057258
6

867

3759

Returns: 1.2282521027768176
2

2235

8166

Returns: 3.171569453809845
12

8263

13912

Returns: 0.8614867256638272
2

5812

30876

Returns: 3.0088649511268843
9

198

17757

Returns: 1.05410497342445
7

255

454

Returns: 1.1866666666666699
2

12413

31519

Returns: 2.958434081750124
10

19777

19997

Returns: 1.0
10

5062

9645

Returns: 1.0
10

3702

10750

Returns: 1.0
3

4103

20812

Returns: 1.9355565529618763
6

18017

26499

Returns: 1.2000000000000388
12

12626

31163

Returns: 0.9125040457439275
16

6747

13829

Returns: 0.8918537342934769
7

11215

13385

Returns: 1.0
6

5393

6359

Returns: 1.25
9

406

23262

Returns: 1.0415664056233687
5

14361

16200

Returns: 1.2626086956522211
7

4268

24453

Returns: 1.1467551768555218
9

3388

13405

Returns: 1.0858205230584947
14

22503

27923

Returns: 0.8000000000000808
2

6181

9923

Returns: 3.3656826075340636
7

301

9475

Returns: 1.2166485013623989
11

31042

31189

Returns: 1.0
4

23925

29606

Returns: 1.6000000000001708
6

199

30435

Returns: 1.234167851748997
3

19391

27430

Returns: 1.9927363184079605
10

2214

25072

Returns: 1.0
8

5388

11041

Returns: 1.2039264237707819
11

21557

30623

Returns: 1.0
3

23823

23995

Returns: 2.0
11

100

529

Returns: 0.9837209302325581
5

4596

5241

Returns: 1.5
13

9161

20693

Returns: 0.8145495534553225
6

3826

7751

Returns: 1.25
2

527

1093

Returns: 3.2260435038212676
3

2429

7542

Returns: 2.0480054751662102
13

7256

22241

Returns: 0.8366208461228671
15

16575

32658

Returns: 0.7999999999998173
3

23410

28547

Returns: 2.0
12

5927

21091

Returns: 0.8584108143749997
11

13629

23940

Returns: 0.9803723816912323
7

185

6260

Returns: 1.194865042791312
12

630

15400

Returns: 0.9145487780107014
4

1065

1270

Returns: 1.5
14

8592

11506

Returns: 0.8966037735849373
7

8424

14814

Returns: 1.0616491941793147
16

17370

28844

Returns: 0.8000000000000361
10

2009

5249

Returns: 1.0
14

743

30012

Returns: 0.8483566791932162
13

1150

5162

Returns: 0.9347744829304759
5

14501

17065

Returns: 1.3123586744639997
9

13683

17242

Returns: 1.0
14

5691

23520

Returns: 0.8483342680871888
11

4065

6055

Returns: 1.0
3

29979

30734

Returns: 2.0
5

499

17799

Returns: 1.3615831454833394
13

24001

32686

Returns: 0.8950034538337879
6

6426

23647

Returns: 1.2426605504591528
6

280

1183

Returns: 1.2654867256637277
16

28051

29869

Returns: 0.7999999999999734
15

961

3805

Returns: 0.7913005272407733
12

1997

7467

Returns: 1.0
4

5280

8112

Returns: 1.75
14

21524

21818

Returns: 0.800000000000004
2

1

1000000

Returns: 3.217908257195455
14

14

1000000

Returns: 0.9208769618734073
13

1

10000

Returns: 0.9676049999999999
2

512

512

Returns: 3.3333333333333335

Statistics

Problem Statement for "NotationLength"

Problem Statement

Definition

Notes

Constraints

Examples