Nisoku
SRM 463 · 2009-11-12 · by rng_58
SRM 463 · 2009-11-12 · by rng_58 · Greedy, Math
Problem Statement
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 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.
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.
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.
Submissions are judged against all 250 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Nisoku with a public method double theMax(vector<double> cards) · 250 test cases · 2 s / 256 MB per case