TopCoder problem "FoxCardGame" used in Member SRM 491 (Division I Level Three)



Problem Statement

    

Fox Jiro and Haruko play a game with two piles of cards: pile A and pile B. Pile A and pile B contain same number of cards. Each card contains a real number between 1.0 and 100.0. Initially, the two players have 0 points. Then they repeat following operations exactly k times:



  • They choose two cards from the piles (one from pile A and another from pile B).
  • The choosen cards are removed from the piles.
  • Jiro earns max{a+b, a*b} points and Haruko earns min{a+b, a*b} points (where a and b are the numbers written on the two cards that were removed).


You are given a double[] pileA, a double[] pileB, and an int k. Return the maximal possible value of (Jiro's points) / (Haruko's points).

 

Definition

    
Class:FoxCardGame
Method:theMaxProportion
Parameters:double[], double[], int
Returns:double
Method signature:double theMaxProportion(double[] pileA, double[] pileB, int k)
(be sure your method is public)
    
 

Notes

-The returned value must have an absolute or relative error less than 1e-9.
 

Constraints

-pileA and pileB will contain between 1 and 50 elements, inclusive.
-pileA and pileB will contain the same number of elements.
-Each element of pileA and pileB will be between 1.0 and 100.0, inclusive.
-k will be between 1 and the number of elements in pileA, inclusive.
 

Examples

0)
    
{1, 2, 3}
{4, 5, 6}
2
Returns: 1.7692307692307692
  1. Choosing cards with numbers 3 and 6, Jiro earns 3*6 = 18 points and Haruko earns 3+6 = 9 points.
  2. Choosing cards with numbers 1 and 4, Jiro earns 1+4 = 5 points and Haruko earns 1*4 = 4 points.

So the solution is (18+5) / (9+4) = 1.769230...

1)
    
{1.234, 5.678, 9.012, 3.456, 7.89}
{2.345, 6.789, 9.876, 5.432, 1.012}
3
Returns: 4.159424420079523
2)
    
{1, 1.1, 1.2, 1.3, 1.4, 1.5}
{5, 10, 15, 20, 25, 30}
2
Returns: 1.3972602739726028
3)
    
{85.302, 92.798, 76.813, 37.994, 36.737, 98.659}
{13.352, 7.3094, 54.761, 8.2706, 63.223, 37.486}
3
Returns: 33.58603889836175

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11236

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14244&pm=11236

Writer:

wrong

Testers:

Rustyoldman , ivan_metelsky , Mimino , rng_58

Problem categories:

Graph Theory, Greedy, Simple Search, Iteration