Connection Status:
Competition Arena > FoxCardGame

FoxCardGame

Member SRM 491 · 2010-03-12 · by rng_58

Member SRM 491 · 2010-03-12 · by rng_58 · Graph Theory, Greedy, Simple Search, Iteration
Class Name: FoxCardGame
Return Type: double
Method Name: theMaxProportion
Arg Types: (vector<double>, vector<double>, int)
Problem Statement

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

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

Choosing cards with numbers 3 and 6, Jiro earns 3*6 = 18 points and Haruko earns 3+6 = 9 points. 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
4)
{1.426,1.169,1.843,1.083,1.171,1.433,1.990,1.808,1.615,1.278,1.553,1.191,1.452,1.673,1.174,1.494,1.006,1.440,1.827,1.423,1.933,1.373,1.389,1.478,1.734,1.212,1.895,1.187,1.977,1.596,1.446,1.105,1.809,1.224,1.245,1.573,1.593,1.197,1.574,1.055,1.904,1.859,1.961,1.286,1.438,1.276,1.261,1.989,1.525,1.239}
{1.320,1.099,1.779,1.675,1.899,1.173,1.224,1.827,1.713,1.963,1.766,1.344,1.726,1.245,1.759,1.713,1.530,1.589,1.261,1.003,1.057,1.946,1.023,1.543,1.319,1.944,1.729,1.155,1.491,1.959,1.588,1.427,1.510,1.161,1.446,1.390,1.151,1.415,1.331,1.075,1.842,1.938,1.967,1.513,1.737,1.964,1.774,1.357,1.555,1.517}
44
Returns: 1.424390216396957

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

Coding Area

Language: C++17 · define a public class FoxCardGame with a public method double theMaxProportion(vector<double> pileA, vector<double> pileB, int k) · 128 test cases · 2 s / 256 MB per case

Submitting as anonymous