Statistics

Problem Statement for "GreaterGame"

Problem Statement

Cat Snuke and wolf Sothe are playing the Greater Game. The game is played with cards. Each card has a number written on it. There are 2N cards. The numbers on the cards are the integers between 1 and 2N, inclusive.


At the beginning of the game, each player gets N of the cards and chooses the order in which he wants to play them. The game then consists of N turns. In each turn, both players play one of their cards simultaneously. The player who revealed the card with the larger number gets a point.


You are given a int[] hand. The elements of hand are the numbers on Snuke's cards. He can play those cards in any order he chooses.


Obviously, Snuke can determine the numbers on Sothe's cards, but he does not necessarily know the order in which Sothe is going to play his cards. You are given the information Snuke has about Sothe in a int[] sothe. For each i, element i of sothe is either the number on the card Sothe will play in turn i (0-based index), or -1 if Snuke does not know the card Sothe will play in that turn.


Snuke wants to play according to a strategy that maximizes the expected number of points he'll get. Find that strategy and return the corresponding expected number of Snuke's points at the end of the game.


As shown in Example 0, the optimal strategy for Snuke may involve some random decisions. However, note that before the game starts Snuke must choose the order in which he is going to play all his cards. He is not allowed to change their order after he sees some of the cards played by Sothe.

Definition

Class:
GreaterGame
Method:
calc
Parameters:
int[], int[]
Returns:
double
Method signature:
double calc(int[] hand, int[] sothe)
(be sure your method is public)

Constraints

  • N will be between 1 and 50, inclusive.
  • hand and sothe will contain exactly N elements each.
  • Each element of hand will be an integer between 1 and 2N, inclusive.
  • Each element of sothe will be either -1, or an integer between 1 and 2N, inclusive.
  • The positive integers in hand and sothe will be distinct.

Examples

  1. {4,2}

    {-1,-1}

    Returns: 1.5

    Sothe will play the cards 1 and 3 in some unknown order. The best strategy for Snuke is to flip a coin and to play his cards either in the order {2,4} or in the order {4,2} with equal probability. This leads to two equally likely results of the game: Snuke plays his 2 against Sothe's 1, and his 4 against Sothe's 3. In this case, Snuke wins both turns and thus scores 2 points. Snuke plays his 2 against Sothe's 3, and his 4 against Sothe's 1. In this case, Snuke scores 1 point. Therefore, the expected number of Snuke's points is 1.5.

  2. {4,2}

    {1,3}

    Returns: 2.0

    If Snuke plays card 2 first and card 4 next, he is guaranteed to score 2 points.

  3. {2}

    {-1}

    Returns: 1.0

    Sothe's only card has to be 1, and thus Snuke is guaranteed to win the only turn of this game.

  4. {1,3,5,7}

    {8,-1,4,-1}

    Returns: 2.5

  5. {1}

    {2}

    Returns: 0.0

  6. {2}

    {1}

    Returns: 1.0

  7. {1}

    {-1}

    Returns: 0.0

  8. {6,12,17,14,20,8,16,7,2,15}

    {-1,-1,4,-1,11,3,13,-1,-1,18}

    Returns: 8.0

  9. {15,8,7,9,30,13,17,2,21,29,20,22,14,18,23}

    {26,-1,-1,-1,16,24,-1,6,-1,27,-1,1,19,-1,28}

    Returns: 12.000000000000002

  10. {31,30,25,1,19,33,40,37,36,14,38,6,22,28,11,29,39,20,2,10}

    {-1,-1,4,27,-1,-1,13,-1,8,-1,-1,-1,3,9,34,-1,32,-1,24,26}

    Returns: 17.3

  11. {13,21,47,43,28,46,4,6,25,26,11,32,12,30,35,48,29,38,33,22,36,17,19,50,2}

    {-1,27,-1,-1,-1,37,39,-1,15,41,20,-1,3,-1,-1,-1,49,16,-1,31,10,-1,-1,24,7}

    Returns: 19.75

  12. {9,50,54,49,51,16,23,4,55,30,38,22,44,52,19,13,58,59,42,35,12,37,40,28,25,8,1,18,32,57}

    {46,47,48,-1,3,-1,43,2,7,-1,-1,26,41,14,17,-1,-1,-1,-1,-1,-1,-1,-1,-1,36,33,-1,-1,21,45}

    Returns: 24.066666666666666

  13. {29,22,9,20,74,28,79,61,84,86,83,15,42,48,37,36,4,51,100,35,81,50,5,82,76,3,78,87,95,96,99,34,47,73,6,98,21,54,64,1,77,89,26,72,25,66,91,13,63,90}

    {8,57,45,24,31,14,92,58,39,53,46,17,40,75,16,56,33,30,65,41,67,69,55,80,18,12,85,2,52,70,62,43,93,44,60,94,32,71,19,11,27,88,59,49,7,10,38,23,68,97}

    Returns: 46.0

  14. {67,39,91,96,46,51,28,64,11,16,31,25,8,52,62,82,57,50,41,81,73,86,68,40,78,1,32,55,14,88,66,74,22,21,26,19,71,47,15,100,80,49,53,38,18,42,33,10,69,5}

    {90,13,9,59,72,85,37,36,94,29,2,7,75,70,48,87,93,56,30,4,24,61,17,6,12,20,65,95,3,79,77,97,76,54,58,89,45,27,99,44,35,23,43,84,60,34,98,83,63,92}

    Returns: 42.0

  15. {75,77,39,89,25,71,94,34,1,38,15,23,4,58,90,68,31,6,70,60,95,5,85,28,47,63,62,93,2,80,98,69,19,92,54,9,46,17,7,36,76,48,10,78,11,86,32,74,67,35}

    {21,88,13,79,73,30,96,12,64,84,22,66,61,18,40,37,72,42,27,65,82,16,56,55,41,53,87,14,91,44,100,20,50,3,8,33,81,51,59,83,24,99,57,26,49,97,43,52,45,29}

    Returns: 43.0

  16. {50,86,27,16,36,17,46,78,95,32,68,41,21,3,42,11,35,90,39,76,100,89,63,19,31,85,6,96,58,66,61,24,87,98,94,59,13,45,48,5,23,83,57,65,37,54,7,93,1,56}

    {80,69,75,44,73,15,26,29,88,38,92,8,14,47,71,79,9,4,12,77,67,74,20,2,40,30,51,52,82,10,55,43,62,97,18,22,64,84,72,28,60,49,34,91,81,25,99,33,53,70}

    Returns: 46.0

  17. {75,34,76,71,68,9,42,69,3,4,35,46,72,80,84,96,87,74,11,99,83,25,89,85,100,17,81,58,66,7,12,41,50,95,79,39,82,64,36,77,94,53,19,88,91,97,60,32,6,56}

    {31,40,62,92,44,93,8,13,67,22,30,27,70,78,47,73,45,29,16,57,49,24,1,61,38,10,52,20,21,43,-1,18,5,15,59,65,55,86,90,54,23,2,26,51,37,33,28,63,14,98}

    Returns: 48.0

  18. {41,49,63,61,52,21,99,35,9,44,31,83,1,94,95,80,92,82,38,74,15,8,96,64,20,88,18,37,76,85,40,79,59,70,3,87,91,12,24,47,36,73,97,42,89,86,28,6,67,48}

    {93,14,22,72,68,13,27,11,45,60,34,51,66,84,32,98,46,5,69,4,56,58,-1,16,39,71,77,25,17,23,-1,50,55,26,53,78,62,30,57,54,90,2,65,10,81,43,100,7,75,29}

    Returns: 49.0

  19. {53,37,75,42,85,99,30,73,48,83,40,82,77,49,50,46,81,36,55,87,4,31,88,56,16,78,59,13,47,6,33,18,67,24,62,34,61,3,17,22,94,20,52,35,9,5,10,2,91,8}

    {38,60,54,-1,69,72,63,25,68,66,39,-1,7,95,26,76,15,65,12,74,29,44,100,32,96,14,28,1,89,21,19,51,45,41,93,23,57,70,11,58,71,-1,84,79,98,43,86,27,97,90}

    Returns: 40.0

  20. {79,72,34,64,61,15,21,65,27,45,3,98,54,48,9,41,19,22,82,74,87,59,35,66,71,80,78,55,28,67,47,14,56,36,96,94,99,43,95,44,18,33,2,60,86,37,68,84,12,57}

    {-1,5,40,77,-1,97,100,53,49,62,70,75,63,31,8,92,83,11,6,30,46,50,20,23,42,-1,16,25,4,26,24,73,91,17,51,88,58,93,13,1,10,69,29,39,76,7,85,81,-1,90}

    Returns: 47.0

  21. {7,72,11,70,48,58,45,91,82,53,8,5,44,66,83,29,17,49,74,98,96,20,84,69,94,22,93,68,63,32,47,57,43,18,26,19,34,80,100,88,2,27,78,87,54,52,99,76,41,9}

    {-1,-1,92,71,-1,42,14,75,39,24,28,1,25,56,13,21,59,23,12,35,61,46,64,-1,60,3,4,15,51,79,86,37,90,30,97,89,65,77,31,-1,40,55,33,38,81,16,73,10,67,36}

    Returns: 48.400000000000006

  22. {42,84,16,34,60,38,13,81,90,100,19,22,53,45,65,15,99,69,1,51,57,78,96,48,61,62,56,7,35,28,94,11,46,97,32,91,64,10,31,50,92,52,3,44,71,25,43,95,30,41}

    {27,75,88,14,54,20,72,-1,5,6,4,68,-1,8,85,-1,2,21,24,77,66,40,55,58,86,63,89,23,82,17,-1,26,33,36,80,39,9,-1,76,59,67,73,12,79,-1,29,47,18,83,74}

    Returns: 43.000000000000014

  23. {69,79,68,63,20,51,32,24,83,71,49,44,34,86,96,7,57,30,1,40,33,19,18,42,72,31,56,74,6,78,45,99,54,53,92,67,77,62,9,55,58,38,14,52,95,5,82,76,22,80}

    {-1,70,43,98,8,81,29,97,3,85,-1,73,59,41,60,88,47,10,23,90,-1,16,37,15,-1,89,39,21,28,65,46,66,17,87,100,50,64,75,-1,-1,12,48,61,2,84,-1,4,11,13,35}

    Returns: 42.999999999999986

  24. {95,2,35,87,51,44,91,55,10,20,15,60,98,11,78,86,4,45,39,14,92,56,77,83,27,12,69,82,40,84,68,9,8,70,38,49,88,63,53,58,5,17,90,80,64,23,18,28,7,81}

    {-1,-1,1,72,100,-1,-1,43,-1,22,75,67,61,30,13,59,50,57,34,31,-1,25,96,73,29,42,99,97,47,71,94,54,46,32,62,48,89,3,26,93,21,41,-1,37,36,6,16,-1,65,66}

    Returns: 41.125

  25. {66,76,88,24,63,30,65,69,99,58,14,53,36,51,92,13,21,78,61,89,91,41,57,3,81,100,84,71,60,72,43,32,77,86,97,9,10,80,85,73,42,34,64,96,6,23,19,5,56,33}

    {25,15,50,7,-1,38,79,48,45,4,49,-1,98,26,35,87,47,70,94,93,44,18,67,-1,74,-1,52,-1,29,1,95,83,2,28,-1,20,12,40,62,27,-1,75,90,39,31,-1,-1,59,11,17}

    Returns: 48.66666666666666

  26. {10,36,69,53,11,98,51,21,96,42,37,94,43,97,35,8,27,81,92,75,61,70,100,59,57,99,82,29,38,20,12,86,5,45,25,78,40,14,85,76,72,68,64,74,50,56,28,63,62,88}

    {-1,-1,1,3,65,-1,-1,-1,83,71,73,55,46,49,90,2,89,58,60,93,19,32,-1,91,80,4,-1,-1,95,13,23,77,16,22,87,6,34,66,9,52,-1,39,48,15,26,18,17,54,67,-1}

    Returns: 48.39999999999999

  27. {27,77,72,47,85,80,66,68,44,57,49,39,94,41,70,36,92,8,74,48,15,67,43,73,95,84,3,1,16,99,51,14,33,50,25,45,6,75,89,29,86,59,52,88,32,98,26,5,76,54}

    {-1,-1,-1,38,69,71,24,12,96,42,78,56,31,18,9,65,79,20,-1,97,23,7,81,53,-1,-1,11,37,28,55,35,82,58,-1,100,-1,19,34,63,-1,4,62,2,17,93,90,10,-1,-1,83}

    Returns: 45.363636363636374

  28. {59,39,55,20,2,62,81,68,64,41,63,29,33,84,15,77,58,56,75,1,4,25,51,100,43,42,34,91,95,22,73,10,45,17,7,24,99,23,90,26,52,92,40,37,71,35,44,82,30,32}

    {-1,89,-1,46,48,3,66,9,-1,47,-1,69,14,12,93,19,-1,78,28,96,50,11,38,54,97,70,60,87,-1,13,36,-1,74,16,79,49,-1,72,6,-1,-1,-1,57,85,76,53,18,80,5,-1}

    Returns: 40.58333333333336

  29. {3,74,34,47,6,92,30,20,70,13,33,89,11,56,51,7,28,19,49,93,17,99,63,35,73,27,64,66,46,98,65,77,78,71,24,14,37,45,81,2,38,95,5,26,84,52,9,90,18,94}

    {85,100,-1,1,8,96,68,69,-1,-1,-1,97,-1,29,4,80,83,72,-1,79,91,59,39,-1,31,82,10,-1,44,57,16,-1,-1,88,58,86,-1,54,-1,23,87,40,75,67,36,-1,60,32,42,50}

    Returns: 39.15384615384617

  30. {32,78,69,76,19,24,27,72,39,88,95,77,47,50,70,25,18,40,49,13,33,71,52,87,26,80,46,6,83,82,99,68,94,56,21,57,84,11,64,79,53,2,85,34,61,35,55,43,5,20}

    {-1,91,65,-1,28,41,89,4,63,29,-1,75,92,90,51,15,7,62,37,-1,-1,38,-1,67,36,-1,-1,10,-1,-1,66,-1,14,-1,42,58,81,86,93,100,8,-1,45,97,-1,23,22,60,73,59}

    Returns: 42.49999999999998

  31. {80,44,21,58,65,85,71,15,56,92,45,51,18,30,5,7,33,90,35,37,98,24,79,76,74,42,31,49,100,60,3,55,87,8,28,19,91,63,95,89,1,96,23,69,54,40,12,83,52,67}

    {-1,57,88,-1,-1,17,73,-1,94,27,-1,-1,50,36,10,20,-1,59,-1,-1,75,-1,32,46,29,77,93,48,53,-1,9,-1,82,66,-1,16,34,47,41,78,86,97,11,70,14,-1,2,26,-1,13}

    Returns: 43.46666666666666

  32. {13,73,1,90,81,52,57,39,34,60,7,48,17,89,87,70,96,41,44,84,72,27,37,29,100,63,62,8,76,4,83,88,45,47,32,59,9,21,43,75,20,91,80,61,58,95,79,26,50,85}

    {94,-1,93,14,33,-1,16,18,-1,65,10,-1,-1,-1,46,-1,64,12,35,51,3,28,74,67,53,6,99,-1,71,66,-1,77,54,31,5,23,-1,-1,-1,40,-1,2,98,25,-1,36,-1,-1,22,86}

    Returns: 44.4375

  33. {7,49,92,42,83,24,76,1,91,13,40,47,89,50,65,41,6,86,96,84,87,88,77,4,98,82,67,72,38,23,53,93,51,62,74,57,60,52,94,54,64,18,30,71,9,32,55,25,44,79}

    {-1,-1,69,-1,-1,12,66,100,90,-1,27,59,11,-1,33,-1,15,2,97,-1,73,58,75,28,-1,35,-1,3,26,-1,-1,20,45,56,14,17,-1,46,36,78,-1,16,81,-1,-1,63,21,-1,34,85}

    Returns: 44.470588235294116

  34. {62,28,47,9,31,11,80,77,10,5,97,91,27,29,55,22,12,95,71,82,74,2,73,37,81,76,87,57,44,70,98,6,48,83,90,32,15,21,88,72,84,61,7,66,38,79,45,1,17,4}

    {-1,8,-1,52,-1,68,43,-1,-1,-1,-1,100,14,78,86,36,50,-1,69,18,-1,99,41,-1,-1,-1,42,63,-1,65,51,-1,-1,67,64,-1,49,24,92,58,30,-1,16,54,53,-1,93,33,13,89}

    Returns: 38.11111111111113

  35. {51,47,19,72,95,22,62,68,92,66,44,58,100,23,84,11,80,18,30,54,14,29,7,49,98,71,32,91,99,65,93,13,96,1,25,48,31,9,90,75,6,27,35,16,52,55,53,20,76,83}

    {28,70,-1,5,17,63,-1,34,-1,88,87,-1,-1,4,8,61,77,-1,69,56,37,10,60,73,64,-1,-1,-1,97,-1,89,81,-1,33,94,85,-1,42,78,12,-1,-1,-1,-1,-1,26,-1,-1,24,82}

    Returns: 39.578947368421034

  36. {55,29,10,75,85,3,32,31,68,39,93,89,8,25,11,37,60,41,18,48,83,61,30,47,9,95,40,84,88,14,100,4,86,21,98,59,34,67,92,62,53,36,76,70,58,54,23,56,96,20}

    {33,74,6,-1,-1,17,-1,90,73,43,16,-1,12,-1,-1,-1,57,35,99,-1,49,-1,-1,-1,42,-1,-1,66,-1,45,-1,-1,1,65,26,87,5,51,44,63,28,46,-1,-1,15,50,-1,-1,64,91}

    Returns: 40.45

  37. {23,53,97,59,85,8,52,42,22,55,96,6,69,39,14,41,74,64,65,84,87,11,83,36,12,90,21,56,28,33,49,17,62,81,94,93,31,43,32,89,63,95,47,1,70,19,48,60,3,45}

    {18,-1,35,-1,46,76,98,86,13,-1,40,-1,-1,16,88,-1,24,-1,100,27,77,50,-1,-1,-1,-1,-1,25,91,-1,4,-1,75,-1,38,-1,79,-1,92,-1,9,-1,-1,10,54,73,2,-1,30,80}

    Returns: 38.57142857142857

  38. {74,75,85,72,76,8,24,96,3,97,59,100,47,61,82,15,68,29,80,88,17,66,60,90,20,81,71,10,35,86,52,49,94,79,64,56,54,58,22,32,89,6,62,13,40,87,98,50,34,42}

    {-1,51,-1,-1,95,21,14,26,92,-1,1,-1,-1,65,57,5,99,-1,-1,53,-1,78,-1,77,30,-1,2,-1,-1,93,-1,69,-1,-1,19,18,-1,63,-1,38,-1,-1,16,73,41,-1,27,-1,48,67}

    Returns: 45.5

  39. {65,60,27,67,72,76,91,82,62,59,53,15,40,38,81,99,73,17,68,42,57,7,54,18,35,95,78,88,79,87,19,71,2,70,23,50,86,52,21,26,48,29,58,85,36,98,1,9,69,77}

    {4,-1,-1,-1,-1,61,94,-1,37,3,-1,97,80,49,8,-1,90,24,-1,22,-1,14,16,45,-1,-1,-1,93,10,34,-1,89,-1,-1,-1,-1,63,-1,13,39,-1,31,-1,33,-1,-1,56,100,-1,66}

    Returns: 41.826086956521735

  40. {66,39,20,56,34,68,32,92,43,91,8,74,75,10,80,29,83,16,15,67,99,87,5,25,48,22,95,57,17,60,62,97,63,44,21,3,45,88,31,30,42,13,7,47,28,1,84,26,24,59}

    {12,-1,49,-1,-1,-1,-1,81,-1,-1,-1,-1,-1,71,40,41,-1,69,76,-1,-1,35,-1,18,33,64,-1,51,46,-1,-1,85,-1,6,-1,2,14,94,77,61,50,-1,70,54,86,-1,37,-1,-1,-1}

    Returns: 33.58333333333334

  41. {46,7,63,55,36,65,56,28,59,23,87,93,70,48,9,76,91,1,16,43,33,84,60,82,90,71,32,81,99,64,69,89,51,78,92,14,15,40,4,73,29,35,80,94,2,77,13,75,31,88}

    {79,-1,-1,-1,37,-1,-1,18,39,3,5,-1,47,97,-1,-1,61,85,54,98,8,12,-1,-1,41,83,67,-1,-1,74,-1,-1,-1,66,-1,58,-1,-1,22,-1,-1,-1,-1,-1,53,-1,52,34,-1,11}

    Returns: 40.52000000000002

  42. {45,67,56,85,25,58,7,86,41,63,34,92,31,11,10,77,74,70,8,44,95,37,6,64,68,17,33,29,91,43,62,5,18,83,53,87,52,60,39,71,66,65,90,54,97,84,47,49,89,20}

    {-1,100,-1,76,-1,-1,26,-1,-1,21,-1,-1,96,46,-1,-1,-1,-1,40,-1,28,-1,-1,42,94,38,9,30,-1,82,-1,99,12,-1,-1,35,78,-1,14,16,-1,1,-1,13,-1,-1,69,-1,-1,75}

    Returns: 38.76923076923078

  43. {4,98,19,87,47,23,69,33,2,100,90,77,28,76,48,95,57,54,13,38,20,24,60,22,14,11,6,83,78,55,68,8,51,50,37,39,72,80,88,1,91,30,16,94,85,63,25,18,99,15}

    {-1,-1,-1,59,-1,-1,-1,-1,-1,-1,-1,84,-1,73,27,-1,36,62,-1,-1,10,-1,-1,17,56,34,81,-1,-1,-1,93,35,-1,-1,89,-1,82,-1,21,42,12,70,-1,64,-1,29,31,-1,41,-1}

    Returns: 35.22222222222221

  44. {75,40,33,3,67,97,18,7,60,84,2,85,92,43,54,13,30,69,32,73,47,93,72,90,11,52,41,44,80,82,70,20,1,23,46,89,88,99,48,63,53,42,74,91,66,8,86,4,14,17}

    {-1,98,6,-1,-1,34,87,95,-1,27,-1,-1,-1,-1,5,-1,79,-1,19,-1,71,64,-1,35,-1,-1,36,-1,-1,39,-1,-1,68,-1,-1,-1,59,51,49,10,-1,-1,-1,29,-1,-1,-1,-1,78,55}

    Returns: 36.42857142857144

  45. {83,84,63,33,90,67,66,98,19,79,53,22,99,12,89,93,78,29,50,62,6,61,52,68,54,37,82,92,8,60,16,42,55,28,96,1,87,31,59,15,13,10,40,86,49,32,100,45,41,85}

    {35,80,-1,69,-1,81,-1,-1,39,97,-1,3,46,9,-1,88,-1,-1,18,-1,-1,-1,30,64,-1,-1,71,-1,36,-1,-1,-1,-1,-1,-1,48,-1,17,25,73,-1,-1,-1,-1,-1,-1,5,65,-1,-1}

    Returns: 38.65517241379309

  46. {11,86,9,4,10,18,67,92,61,2,17,56,54,3,62,24,41,19,39,60,96,84,27,64,26,28,45,80,55,73,69,1,20,15,32,33,50,31,49,16,12,13,43,48,89,63,14,78,29,6}

    {-1,-1,23,-1,47,81,74,79,94,97,-1,52,95,-1,70,77,36,-1,-1,7,-1,66,-1,-1,-1,58,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,40,46,-1,-1,-1,-1,75,-1,-1,-1,-1,91,37,-1}

    Returns: 24.200000000000003

  47. {64,31,94,6,58,79,53,84,60,23,63,17,16,70,71,4,97,42,20,10,52,88,90,11,47,3,44,69,93,12,77,87,91,9,55,80,78,38,48,29,34,54,35,96,7,86,13,73,30,61}

    {41,82,-1,-1,-1,62,21,66,37,-1,-1,-1,-1,-1,15,-1,-1,-1,-1,-1,-1,-1,-1,67,-1,-1,89,45,75,-1,5,-1,-1,36,-1,83,-1,51,49,50,24,-1,-1,-1,65,-1,-1,-1,-1,-1}

    Returns: 34.29032258064516

  48. {63,16,11,37,89,82,92,65,43,100,58,52,35,5,78,54,88,51,31,12,57,56,38,84,15,17,29,98,39,75,7,46,61,19,69,22,93,77,13,48,21,87,36,44,41,45,3,97,94,83}

    {40,67,91,-1,70,55,8,-1,74,47,-1,-1,-1,62,-1,-1,-1,-1,50,-1,-1,-1,-1,86,-1,-1,-1,72,1,-1,73,-1,-1,-1,-1,-1,42,-1,-1,25,-1,-1,-1,-1,95,76,-1,-1,-1,-1}

    Returns: 34.65625

  49. {70,63,32,89,25,72,99,11,9,91,82,21,34,66,36,39,71,56,69,60,81,57,74,1,6,46,31,93,30,41,80,10,47,86,85,62,15,4,2,59,77,14,13,22,40,29,90,92,17,16}

    {-1,-1,-1,-1,44,-1,-1,20,-1,26,52,-1,28,-1,-1,79,-1,-1,-1,-1,-1,35,38,94,-1,-1,-1,23,5,-1,42,-1,-1,19,45,-1,-1,-1,-1,-1,58,-1,-1,-1,-1,-1,88,-1,-1,95}

    Returns: 31.242424242424246

  50. {26,87,82,59,2,69,4,8,28,86,57,91,9,33,88,51,40,52,72,98,16,23,34,54,29,64,56,73,15,68,76,13,24,75,45,92,5,67,89,97,42,19,66,14,21,46,6,3,41,70}

    {55,53,-1,-1,-1,-1,-1,-1,-1,-1,80,20,-1,49,94,-1,50,-1,-1,-1,-1,18,48,-1,30,-1,-1,58,74,-1,-1,-1,-1,-1,-1,-1,-1,-1,78,-1,62,-1,-1,-1,27,-1,37,-1,-1,-1}

    Returns: 29.941176470588243

  51. {60,3,43,42,10,95,9,31,67,84,58,16,46,76,56,62,77,69,33,89,53,22,2,41,90,15,66,4,85,68,78,54,50,25,83,59,5,65,48,51,20,80,13,30,96,24,52,1,39,17}

    {-1,-1,72,-1,-1,-1,79,-1,91,45,-1,44,34,-1,-1,-1,-1,-1,-1,-1,-1,40,-1,-1,-1,73,-1,-1,18,100,-1,-1,-1,82,-1,-1,-1,-1,-1,97,-1,-1,-1,-1,-1,81,-1,-1,26,38}

    Returns: 28.65714285714286

  52. {96,25,16,47,64,32,84,9,44,88,93,5,48,1,31,55,67,94,10,57,70,21,51,99,95,6,63,50,62,34,100,52,87,54,30,28,15,65,35,85,38,69,59,98,27,66,29,89,53,17}

    {-1,-1,-1,-1,-1,75,20,-1,-1,68,-1,-1,-1,78,46,-1,74,-1,49,-1,-1,-1,76,-1,-1,-1,-1,-1,-1,-1,11,-1,-1,-1,-1,-1,12,-1,-1,71,8,39,-1,86,-1,-1,-1,-1,-1,-1}

    Returns: 33.0

  53. {81,97,78,34,4,12,44,62,83,53,99,11,68,40,96,70,10,61,92,86,77,9,75,37,84,95,79,76,58,8,38,28,46,23,71,45,43,32,21,35,3,22,100,69,29,33,19,80,13,89}

    {5,98,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,60,42,-1,-1,66,1,-1,-1,-1,-1,39,88,-1,73,-1,-1,-1,17,-1,87,-1,-1,-1,31,-1,-1,-1,-1,-1,-1,6,-1,-1,-1,-1,-1,-1}

    Returns: 33.08108108108108

  54. {36,68,96,70,35,3,56,65,26,57,49,22,51,88,66,69,89,10,15,80,72,8,38,40,13,90,86,93,18,85,30,52,44,2,75,81,58,29,45,97,95,25,63,42,91,32,47,76,37,99}

    {-1,28,94,-1,31,-1,-1,-1,-1,-1,-1,-1,-1,-1,4,-1,-1,-1,-1,-1,24,-1,-1,-1,-1,61,-1,-1,-1,-1,-1,-1,87,27,-1,-1,-1,-1,-1,92,1,-1,14,-1,-1,21,-1,-1,-1,-1}

    Returns: 34.55263157894737

  55. {90,39,88,29,2,100,76,21,37,58,74,83,71,68,65,60,22,87,52,44,31,77,34,63,4,70,35,10,49,18,13,75,6,84,98,26,57,8,80,82,1,97,14,24,46,30,33,47,59,11}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,67,-1,92,-1,-1,-1,38,-1,12,41,-1,-1,-1,-1,81,-1,20,-1,-1,9,-1,-1,96,-1,-1,-1,17,7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 28.84615384615385

  56. {24,95,44,64,65,37,3,86,8,47,91,57,94,99,90,12,93,59,25,81,87,54,66,23,34,5,45,22,56,6,92,20,19,96,75,29,60,77,72,88,68,69,43,63,53,55,10,17,48,51}

    {-1,-1,-1,74,32,-1,13,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,2,-1,-1,-1,-1,-1,18,-1,-1,-1,-1,-1,39,-1,-1,14,71,-1,-1,-1,-1,-1,-1,-1,-1,-1,58,-1,-1}

    Returns: 33.0

  57. {12,51,76,55,41,59,26,82,10,4,84,86,30,28,53,29,60,42,49,70,13,99,24,57,8,33,95,22,15,25,65,45,58,100,78,56,81,66,61,79,91,71,90,16,77,97,52,27,48,62}

    {-1,-1,-1,-1,-1,1,-1,-1,96,21,-1,-1,-1,14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,98,-1,-1,-1,-1,-1,-1,-1,94,-1,-1,9,-1,40,34,-1,-1,-1,-1,-1,-1}

    Returns: 31.8780487804878

  58. {38,91,7,71,43,18,74,42,57,92,77,69,95,25,89,97,34,53,61,100,68,96,85,98,3,49,32,90,94,66,75,63,6,17,30,62,50,64,35,31,72,19,37,41,22,82,21,99,15,88}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,20,26,-1,16,-1,-1,-1,58,-1,-1,-1,-1,-1,-1,-1,8,27,-1,-1,-1,-1,-1,47,45,-1,-1,-1,-1,-1,-1,-1}

    Returns: 35.09523809523808

  59. {92,53,24,13,1,44,77,33,52,20,87,71,76,38,15,60,9,27,62,100,5,22,25,88,47,17,11,69,40,50,79,83,96,21,70,97,42,31,81,68,19,29,86,74,80,59,35,58,67,4}

    {-1,-1,-1,-1,-1,-1,-1,16,-1,-1,-1,-1,-1,-1,-1,-1,-1,85,-1,-1,-1,-1,78,-1,-1,-1,-1,-1,18,-1,-1,-1,-1,-1,-1,48,-1,-1,-1,-1,65,-1,-1,-1,-1,-1,-1,28,-1,-1}

    Returns: 28.023255813953494

  60. {88,22,23,29,81,75,9,69,42,25,18,53,64,62,6,85,35,56,36,33,71,20,78,98,73,19,24,72,76,21,40,89,82,31,84,27,10,7,41,44,38,46,79,48,11,94,55,95,57,5}

    {-1,-1,-1,-1,-1,-1,92,-1,-1,-1,-1,-1,-1,74,-1,-1,-1,66,-1,-1,-1,-1,-1,-1,54,-1,-1,-1,-1,-1,-1,-1,-1,-1,100,-1,4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 26.136363636363637

  61. {56,16,12,76,43,52,50,15,32,47,64,85,97,3,63,77,88,14,29,40,44,17,9,46,34,11,100,73,57,6,42,91,78,37,28,84,59,92,20,55,66,48,94,65,60,67,68,24,25,31}

    {13,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,26,-1,-1,-1,-1,-1,-1,-1,-1,82,-1,-1,-1,-1,-1,-1,-1,-1,-1,18,-1,-1,-1,23,-1,-1,-1,-1,-1,-1}

    Returns: 26.577777777777783

  62. {73,8,11,39,28,57,68,20,38,69,1,79,54,78,29,34,89,31,42,19,6,76,51,15,61,26,56,14,25,43,90,27,36,30,72,65,45,88,16,40,35,86,81,10,13,9,58,52,97,21}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,64,-1,-1,-1,-1,-1,-1,-1,-1,67,-1,-1,-1,-1,-1,-1,96,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,41,-1,-1,-1,-1}

    Returns: 20.826086956521745

  63. {92,34,36,21,82,66,98,75,94,5,11,90,33,67,14,35,23,74,43,54,46,51,16,1,87,49,22,71,8,32,42,64,44,38,13,37,97,91,47,95,79,72,48,96,41,63,18,86,19,70}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,60,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,84,-1,-1,-1,61,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 27.659574468085115

  64. {89,93,7,36,50,79,40,82,58,68,24,91,55,94,33,97,11,49,60,37,70,100,20,83,9,30,86,54,72,67,16,47,38,64,71,80,43,56,74,19,48,28,87,57,95,84,18,34,17,62}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,21,-1,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 31.041666666666675

  65. {67,52,17,70,2,90,8,65,79,22,72,32,9,26,85,14,61,23,57,7,74,29,82,36,97,27,16,21,18,92,4,80,5,89,12,64,75,91,77,58,10,6,59,53,94,46,60,15,19,1}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,41,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 20.3265306122449

  66. {2,83,59,24,12,80,85,30,28,92,100,35,21,44,63,54,76,81,46,48,70,74,25,88,87,43,84,65,93,42,26,17,73,98,72,68,67,55,47,11,22,3,86,23,8,37,97,78,49,62}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 29.160000000000004

  67. {17,98,82,1,11,86,55,80,100,20,68,79,72,74,58,22,34,2,37,67,46,93,41,94,65,83,49,13,39,10,48,42,54,15,33,24,35,71,45,70,16,5,76,19,75,81,56,27,87,26}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 24.519999999999985

  68. {78,41,44,12,34,28,36,8,72,90,52,81,35,61,74,83,65,23,80,53,98,33,89,93,14,27,95,32,20,67,51,2,77,29,31,50,56,54,99,18,38,62,49,97,17,75,88,66,76,87}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 29.299999999999986

  69. {70,83,81,95,20,82,60,26,84,68,87,45,56,12,13,61,17,23,22,71,21,74,29,5,46,78,97,58,9,100,62,6,14,30,66,4,88,90,8,16,79,18,55,7,24,76,80,98,42,41}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 24.439999999999998

  70. {16,62,66,28,93,33,13,51,82,6,14,61,55,12,63,50,35,90,58,5,94,1,24,86,9,30,100,88,47,7,19,17,75,77,97,87,98,36,89,79,20,70,18,80,38,59,91,29,68,39}

    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}

    Returns: 25.800000000000008

  71. {6, 12, 17, 14, 20, 8, 16, 7, 2, 15 }

    {-1, -1, 4, -1, 11, 3, 13, -1, -1, 18 }

    Returns: 8.0

  72. {27, 71, 30, 39, 85, 2, 63, 56, 5, 42, 96, 19, 77, 6, 34, 60, 22, 75, 61, 58, 95, 98, 72, 38, 86, 14, 64, 43, 99, 4, 7, 80, 21, 35, 24, 65, 62, 37, 13, 49, 48, 46, 81, 69, 32, 73, 94, 16, 44, 74 }

    {59, 20, -1, 8, 55, 50, -1, -1, 25, 36, -1, -1, 9, 23, -1, 47, 82, 11, -1, 28, -1, 53, -1, 100, 45, -1, 89, 87, 57, -1, -1, -1, 79, 97, 54, -1, -1, -1, -1, -1, 17, -1, -1, -1, 92, -1, 91, 76, -1, -1 }

    Returns: 36.916666666666664

  73. {18, 4, 22, 34, 5, 88, 29, 85, 66, 52, 28, 73, 83, 31, 38, 14, 80, 27, 74, 72, 41, 2, 48, 10, 1, 21, 94, 54, 91, 26, 8, 86, 71, 51, 49, 7, 35, 95, 60, 89, 67, 61, 63, 68, 87, 20, 42, 19, 53, 58 }

    {45, 90, -1, 99, 82, 12, -1, 75, 62, -1, 77, 15, -1, 50, -1, -1, -1, 84, -1, -1, 46, -1, 16, -1, -1, 98, -1, -1, 32, -1, 64, 69, 100, -1, -1, 33, 6, 13, 9, -1, -1, 39, -1, -1, 96, 17, 23, -1, -1, -1 }

    Returns: 34.66666666666667

  74. {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50 }

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

    Returns: 13.0

  75. {2, 3, 4 }

    {5, 6, -1 }

    Returns: 1.0

  76. {1, 2 }

    {3, 4 }

    Returns: 0.0

  77. {1, 3, 4 }

    {-1, -1, -1 }

    Returns: 0.6666666666666666

  78. {1, 2, 3, 4 }

    {5, 6, 7, 8 }

    Returns: 0.0

  79. {1, 4, 5, 8, 10 }

    {2, 3, 6, 7, 9 }

    Returns: 4.0

  80. {2, 3, 5, 7 }

    {8, -1, -1, -1 }

    Returns: 2.0

  81. {2, 3, 6 }

    {-1, 4, 5 }

    Returns: 2.0

  82. {2, 3 }

    {4, -1 }

    Returns: 1.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: