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 <double>
Returns:	double
Method signature:	double theMax(vector <double> 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

{5, 8}

Returns: 40.0

5 * 8 = 40.

{1.5, 1.8}

Returns: 3.3

1.5 + 1.8 = 3.3.

{8.26, 7.54, 3.2567}

Returns: 202.82857868

{1.5, 1.7, 1.6, 1.5}

Returns: 9.920000000000002

{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 閱讀(1081) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜