# The Fourth Dimension Space

## Topcoder 463 Div 2 1000

### Problem Statement

Taro and Hanako are playing a game called Nisoku, which is played as follows. Initially, there is a pile of cards. Each card contains a real number between 1.5 and 10.0, inclusive. You are given a vector <double> cards, the i-th element of which is the number written on the i-th card.

Repeat the following step until there is only one card left in the pile: Remove any two cards from the pile, and add one new card to the pile. Write either a+b or a*b on the new card, where a and b are the numbers written on the two cards that were removed.

Return the maximal possible number written on the final card in the pile.

### Definition

 Class: Nisoku Method: theMax Parameters: vector Returns: double Method signature: double theMax(vector cards) (be sure your method is public)

### Notes

- Your return value must have an absolute or relative error less than 1e-9.

### Constraints

- cards will contain between 2 and 50 elements, inclusive.
- Each element of cards will be between 1.5 and 10.0, inclusive.

### Examples

0)

 `{5, 8}`
`Returns: 40.0`
 5 * 8 = 40.
1)

 `{1.5, 1.8}`
`Returns: 3.3`
 1.5 + 1.8 = 3.3.
2)

 `{8.26, 7.54, 3.2567}`
`Returns: 202.82857868`
3)

 `{1.5, 1.7, 1.6, 1.5}`
`Returns: 9.920000000000002`
4)

 ```{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10}```
`Returns: 1.0E50`
 The answer can be extremely big.

#include<iostream>
#include
<algorithm>
#include
<vector>
using namespace std;

class Nisoku
{
public:

double theMax(vector<double>cards)

{

int i,j;
sort(cards.begin(),cards.end());

double ans=0;

for(i=0;i<=cards.size();i+=2)

{

double p=1;

for(j=0;j<i/2;j++)
p
*=(cards[j]+cards[i-1-j]);

for(j=i;j<cards.size();j++)
p
*=cards[j];
ans
=max(ans,p);
}

return ans;
}

}
;

posted on 2010-03-02 22:27 abilitytao 阅读(1022) 评论(0)  编辑 收藏 引用