MergersDivOne | Topcoder Archive

Problem Statement

Warning: This problem statement contains superscripts and/or subscripts. It may not display properly outside of the applet.

The candy industry is going through a hard time in Byteland. Some of the biggest companies in the business have decided to perform a series of mergers so as to become one company in the end. Surprisingly, empirical studies conducted by the economists of Byteland have shown that for any m >= 2 the revenue of a company that is created by simultainously merging m companies with revenues equal to r₀, r₁, ..., r_{m - 1} is equal to the average of these revenues, that is (r₀ + r₁ + ... + r_{m - 1}) / m.

You are given a int[] revenues. The revenue of the i-th of the companies that want to merge is equal to revenues[i]. Return the maximum possible revenue of the final company that can be created in any series of mergers that joins all the companies. In each of the mergers, we may merge as many of the currently existing companies as we wish.

Definition

Class:: MergersDivOne
Method:: findMaximum
Parameters:: int[]
Returns:: double
Method signature:: double findMaximum(int[] revenues)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 10-9.
Please note that the revenue of a company may be negative; this means that the company is actually losing money.
It is always possible to merge all companies into a single one: for example, by merging all of them in a single step.

Constraints

revenues will contain between 2 and 50 elements, inclusive.
Each element of revenues will be between -1,000 and 1,000, inclusive.

Examples

```
{5, -7, 3}
```
```
Returns: 1.5
```
The optimal way is to first merge companies 1 and 2, obtaining a company with total revenue -2, and then merge that company with company 0.
```
{10, -17}
```
```
Returns: -3.5
```
```
{12, 12, 12, 12, 12}
```
```
Returns: 12.0
```
We can just merge all the companies at once.
```
{0, 0, 0, 0, 0, 100}
```
```
Returns: 50.0
```
We may first merge companies 0 through 4 and then merge the resulting company with company 5.

{10, -10, 100, -100, 1000, -1000}

Returns: 491.25

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.