Connection Status:
Competition Arena > MergersDivOne

MergersDivOne

SRM 536 · 2011-11-22 · by meret

SRM 536 · 2011-11-22 · by meret · Greedy, Sorting
Class Name: MergersDivOne
Return Type: double
Method Name: findMaximum
Arg Types: (vector<int>)
Problem Statement

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 r0, r1, ..., rm - 1 is equal to the average of these revenues, that is (r0 + r1 + ... + rm - 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.

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
0)
{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.

1)
{10, -17}
Returns: -3.5
2)
{12, 12, 12, 12, 12}
Returns: 12.0

We can just merge all the companies at once.

3)
{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.

4)
{10, -10, 100, -100, 1000, -1000}
Returns: 491.25

Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MergersDivOne with a public method double findMaximum(vector<int> revenues) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous