Statistics

Problem Statement for "TheTournamentDivOne"

Problem Statement

John and Brus have an interest in team sports tournaments. They are currently investigating the intermediate standings of a tournament. They don't know which games have been played so far. They only know that the tournament is played using the following rules:

Each game is played between two teams and results in either a victory for one team or a draw. If a team wins a game, it gains w points and its opponent gains no points. In case of a draw, each team gains d points. The score of a team is the sum of all the points it has gained from all its games. There are no restrictions on which teams can play against each other, and each pair of teams can play against each other any number of times (possibly zero).

You are given a int[] points representing the intermediate standings of the tournament. The i-th element of points is the score of the i-th team. Return the minimum number of games that could have been played to achieve those standings. If points doesn't represent a valid state, return -1 instead.

Definition

Class:
TheTournamentDivOne
Method:
find
Parameters:
int[], int, int
Returns:
int
Method signature:
int find(int[] points, int w, int d)
(be sure your method is public)

Constraints

  • points will contain between 2 and 50 elements, inclusive.
  • Each element of points will be between 0 and 10,000, inclusive.
  • w will be between 1 and 10,000, inclusive.
  • d will be between 1 and w, inclusive.

Examples

  1. {10, 1, 1}

    2

    1

    Returns: 6

    The first team has five wins or four wins and two draws. The second and the third teams each has one draw.

  2. {1, 1, 1}

    2

    1

    Returns: -1

    These standings are impossible. For each of the three teams to have one point, each one must have played in a game that resulted in a draw. There is no way for three teams to have each played in exactly one game.

  3. {1, 4, 0, 2}

    3

    1

    Returns: 3

    The only win goes to the second team.

  4. {8, 3, 8, 5, 9, 2, 7, 11}

    3

    2

    Returns: 15

  5. {4, 0, 0, 5}

    1

    1

    Returns: 5

  6. {0, 4, 0, 0, 2, 2, 9, 5, 8}

    10

    10

    Returns: -1

  7. {2, 6}

    7

    1

    Returns: -1

  8. {3, 1}

    3

    1

    Returns: -1

  9. {95, 98, 71}

    11

    10

    Returns: -1

  10. {3521, 8037, 8568, 1231, 3712, 9536, 6151, 6617, 2666, 4945, 8274, 9461, 9365, 1906, 690, 3323, 1178, 712, 1865, 4737, 9425, 4181, 5455, 8607, 1406, 8292, 7787, 430, 2445, 4057, 7115, 5075, 9932, 7132, 9015, 3114, 9517, 9794, 1334, 1884, 8533, 7116, 9800, 4766, 5166}

    28

    23

    Returns: -1

  11. {4266, 2058, 9501, 9171, 2766, 2195, 8069, 7548, 5391, 2054, 2564, 1875, 2457, 2554, 5403, 4031}

    94

    4

    Returns: -1

  12. {5252, 3156, 3951, 2542, 1209, 6769, 8027, 9151, 2284, 1115, 801, 8448, 7047, 1470, 8234, 398, 5091, 8403, 2690, 1957, 2726, 9942, 1348}

    31

    6

    Returns: 3401

  13. {9418, 1678, 7930, 7777, 7611, 5559, 4549, 8498, 8142, 8419, 7917, 9348, 1294, 1476, 7619, 6096, 5941, 565, 7533, 1527, 6721, 665, 7245, 4142, 6209, 9605, 7491, 2620, 5929, 8539, 6390, 237}

    56

    50

    Returns: -1

  14. {6181, 1150, 1711, 8189, 5961, 7272, 1378, 7404, 9342, 4776, 7834}

    78

    44

    Returns: -1

  15. {9328, 6341, 6925, 7238, 9259, 6400, 4621, 8900, 6565, 9984, 5266, 7434, 1380, 5626, 460, 738, 2687, 9037, 3942, 7605, 9846, 3988, 4608, 5994, 9310, 3997, 2889, 1170, 393, 7612, 4832, 3359}

    64

    22

    Returns: -1

  16. {4848, 3453, 7757, 3513, 7470, 2252, 6596, 1637, 8210}

    9133

    1649

    Returns: -1

  17. {9498, 3829, 2101, 2221, 2824, 2971, 9272, 6069, 4864, 1098, 7196, 6168, 6329, 6181, 3422, 5965, 1201, 6891, 4752, 6589, 6232, 5236, 3062, 9243, 4864, 9164, 4558, 141, 4222, 1513, 4354, 4900, 4344}

    366

    55

    Returns: -1

  18. {5967, 8141, 1564, 4900, 1376, 1324, 1551, 4355, 8938, 2488, 9913, 7654, 5981, 6761, 5024, 85, 3665, 7276, 6437, 7295, 324, 2889, 5133, 4647, 2290, 7927, 4209, 5439, 7517, 5111, 6059, 8368, 9747, 400, 1589, 1824, 6744, 4300, 3734, 7704, 8411, 7282, 1616, 2353, 2061, 631}

    5011

    707

    Returns: -1

  19. {2082, 2485, 3876, 2182, 5409, 9149, 7797, 1506, 6627, 3401, 4346, 4092, 4233, 504, 4962, 6430, 282, 1633, 1115, 9527, 772, 5444, 6275, 472, 4724, 2499, 3745, 5345, 5632, 3512, 8259, 9331, 7448, 3749, 2992, 8519, 4232, 7352, 8072, 2613, 5477, 1233, 6328, 7510, 6390, 1701, 5649, 7432}

    21

    2

    Returns: 10862

  20. {8590, 7988, 377, 5626, 3047, 9131, 3499, 6174, 7128, 6423, 2270, 1167, 171, 9267, 5250, 8229, 4238, 4552, 5623, 3263, 6953, 7385, 6470, 7672, 8120, 8975, 8706, 1999}

    446

    354

    Returns: -1

  21. {0, 0}

    3

    1

    Returns: 0

  22. {0, 0, 0}

    2

    1

    Returns: 0

  23. {4115, 4334, 4274, 3323, 3711, 5425, 8445, 6787, 2932, 5516, 2884, 7429, 2166, 8607, 8736, 8114, 2292, 9364, 9568, 8665, 2689, 3406, 8521, 9180, 7906, 8461, 8864, 7945, 1131, 2616, 9230, 3177, 9800, 5015, 2455, 6075, 2057, 6711, 8536, 1114, 4533, 9766}

    22

    8

    Returns: -1

  24. {7115, 9591, 1255, 3532, 2815, 7739, 9046, 7990, 2942, 3470, 5233, 4771, 9284, 2381, 5966, 2724, 8426, 9569, 2198, 3542, 7690, 1984, 7958, 9305, 8604, 9638, 1052, 1325, 2151, 7502, 1403, 7455, 5530, 3485, 6348, 2821, 2421, 2957, 6915, 6549, 2362, 7650, 7448}

    22

    7

    Returns: 10545

  25. {6517, 5559, 9611, 8625, 2455, 3565, 8533, 6678, 3476, 4526, 4367, 8580, 8419, 5917, 3237, 1488, 8238, 8142, 2548, 8498, 9491, 5807, 2294, 5664, 7142, 8941, 6245, 2066, 7311, 6929, 9440, 8544, 8227, 6208, 4538, 7096, 7619, 1348, 5721, 3418, 2126, 5929, 6776, 7390, 5620, 4604, 6769}

    31

    2

    Returns: 9338

  26. {7764, 7149, 2558, 9067, 3042, 5168, 4862, 8618, 7790, 5451, 9701, 1762, 4504, 2579, 7810, 8173, 8741, 6212, 5115, 5131, 5663, 1481, 7795, 5711, 9445, 1209, 6184, 7801, 6906, 8449, 7413, 6347, 6822, 7498, 8424, 2106, 3334, 4347, 7462, 3630, 1076, 5590, 7239, 3795, 3947, 9967, 6959}

    8

    4

    Returns: -1

  27. {4354, 6151, 4098, 4196, 1320, 9100, 1353, 4558, 8826, 4462, 1675, 3916, 6415, 6752, 9329, 3924, 5219, 6062, 6168, 4422, 9181, 7497, 8871, 5974, 5128, 7492, 9864, 3141, 5344, 6222, 8589, 2236, 4994, 9220, 3829, 9243, 5833, 1031, 6747, 7241, 8232, 1647, 8899, 8164}

    75

    1

    Returns: 4323

  28. {9414, 2858, 7625, 4627, 9866, 8885, 2034, 2164, 7906, 3978, 7147, 1260, 3291, 4567, 5070, 8425, 9514, 5127, 2587, 7107, 4214, 5021, 6547, 2680, 7832, 3715, 5192, 6815, 4510, 8352, 6455, 2341, 1228, 6588, 7326, 9993, 3471, 1475, 7136, 1566, 8579, 1168, 5652, 9025, 5599, 5883, 6424}

    51

    16

    Returns: 5274

  29. {7125, 2328, 1516, 4092, 9666, 2308, 7844, 3978, 9114, 3498, 2281, 5053, 9816, 9142, 8511, 8057, 6632, 8222, 7377, 6182, 5527, 3232, 7809, 8495, 6852, 1724, 3331, 1608, 5400, 5797, 6926, 2646, 3232, 2443, 6519, 3553, 2521, 3081, 7345, 8742, 1248, 1346, 5649, 7135, 5400}

    71

    7

    Returns: 4083

  30. {9334, 8411, 5298, 3336, 6404, 2156, 4447, 4811, 3073, 4099, 1329, 1366, 2377, 7162, 5376, 8538, 4903, 5325, 1731, 9902, 9149, 6734, 3775, 9195, 3953, 1067, 5182, 5930, 7231, 7431, 8658, 2790, 2847, 3480, 2454, 1905, 2216, 9474, 9451, 3572}

    66

    47

    Returns: -1

  31. {9707, 8908, 5670, 7489, 5977}

    101

    57

    Returns: 347

  32. {511, 2892}

    555

    7

    Returns: -1

  33. {8073, 30, 9871, 745}

    43

    3

    Returns: 462

  34. {6555, 9717}

    9

    9

    Returns: -1

  35. {6555, 9708}

    9

    9

    Returns: -1

  36. {5462, 7011, 5716, 7766}

    11

    1

    Returns: 2371

  37. {1491, 6953}

    15

    3

    Returns: -1

  38. {4504, 2309, 310}

    463

    96

    Returns: -1

  39. {1615, 7736}

    822

    731

    Returns: -1

  40. {4821, 6218}

    36

    9

    Returns: -1

  41. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000}

    10000

    10000

    Returns: 25

  42. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000}

    1

    1

    Returns: 250000

  43. {9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999}

    2

    1

    Returns: -1

  44. {6155, 3790, 3787, 2559, 381, 416, 5983, 7493, 7522, 5721, 514, 7662, 6292, 4507, 3415, 4268, 6705, 4471, 5970, 5672, 8356, 8401, 2395, 9091, 9707, 710, 902, 4277, 5576, 3520, 8908, 8739, 795, 2896, 4175, 5442, 2685, 4967, 9711, 164, 6464, 7016, 2155, 9238, 5463, 5834, 2910, 6557, 2212, 7768}

    3

    2

    Returns: 62586

  45. {9581, 6780, 2509, 5213, 5311, 566, 8095, 7783, 6610, 7913, 5556, 1984, 6479, 2779, 7763, 6650, 4828, 7722, 6445, 1416, 104, 8983, 7409, 2089, 826, 3395, 5012, 5312, 6058, 1358, 9046, 9324, 9412, 8160, 9263, 7520, 3547, 2190, 3601, 9536, 3307, 6746, 4425, 4906, 4136, 5858, 7082}

    3

    2

    Returns: 65152

  46. {45, 61, 96, 7, 65, 5, 69, 88, 52, 37, 37, 91, 17, 21, 23, 73, 29, 34, 7, 26, 81, 99, 73, 35, 44, 41, 27, 99, 77, 31, 52, 81, 2, 11, 63, 91, 90, 49, 25, 34, 17, 7, 29, 11, 65, 63, 73, 84, 69, 68}

    3

    2

    Returns: 628

  47. {5, 41, 3, 19, 83, 65, 83, 45, 17, 90, 83, 41, 21, 33, 2, 77, 91, 1, 11, 1, 7, 86, 77, 61, 65, 10, 23, 77, 73, 27, 37, 49, 9, 11, 9, 5, 82, 97, 6, 22, 53, 66, 29, 1, 89, 51, 32}

    7

    1

    Returns: 333

  48. {28,31,11}

    5

    3

    Returns: -1

  49. {19,22,28}

    3

    1

    Returns: 25

  50. {73,52,15,50,22,82,40,40,34}

    18

    1

    Returns: 60

  51. {26,17,37,9,43,61}

    1

    1

    Returns: 97

  52. {12,16,31,1}

    5

    1

    Returns: 18

  53. {53,59,38,42,53,31}

    3

    1

    Returns: 94

  54. {16,5,10}

    3

    2

    Returns: -1

  55. {74,11,86}

    1

    1

    Returns: 86

  56. {3,10,12}

    3

    1

    Returns: 10

  57. {4,8}

    2

    1

    Returns: 6

  58. {8,0}

    4

    4

    Returns: 2

  59. {71,28,70,44}

    1

    1

    Returns: 107

  60. {14,20}

    1

    1

    Returns: 20

  61. {22,2}

    1

    1

    Returns: 22

  62. {80,53}

    17

    12

    Returns: -1

  63. {5,5,4,9,1,6,6,0,7,5}

    7

    1

    Returns: 19

  64. {0,0}

    18

    1

    Returns: 0

  65. {33,36,37,29,50,41}

    5

    4

    Returns: 32

  66. {1,3,3,1,2,2,4}

    1

    1

    Returns: 8

  67. {4,4,5,27,30,6,31,13,38,5}

    1

    1

    Returns: 82

  68. {6,3,9}

    5

    3

    Returns: 3

  69. {2,41,73,63,54,5,44,43,60,3}

    7

    3

    Returns: -1

  70. {2,10,13}

    2

    2

    Returns: -1

  71. {20,22,7,30,7,28}

    2

    2

    Returns: -1

  72. {12,3,26,0,23,26,27,31}

    4

    1

    Returns: 41

  73. {15,14,15,64,9,67,32,44,79}

    13

    3

    Returns: -1

  74. {18,8,8}

    18

    2

    Returns: 5

  75. {40,17,27,31,2,43,36,26,27,41}

    3

    1

    Returns: 99

  76. {0,0,0,0}

    1

    1

    Returns: 0

  77. {7,5}

    5

    1

    Returns: -1

  78. {0,1,0,1,0}

    1

    1

    Returns: 1

  79. {51,12,52}

    7

    4

    Returns: -1

  80. {45,49,10,37,16,26,45}

    15

    2

    Returns: 35

  81. {71,91,42,1,3,17,49}

    4

    1

    Returns: 72

  82. {33,63,61,20,24,69,38}

    6

    1

    Returns: 56

  83. {24,7,8,15,24,27}

    5

    1

    Returns: 27

  84. {18,3,8}

    3

    1

    Returns: 11

  85. {16,60,60}

    5

    1

    Returns: 32

  86. {36,60,68,67,11,69,41,14,26}

    11

    1

    Returns: 52

  87. {29,24,29,0,12,29}

    7

    2

    Returns: 24

  88. {77,51,23,24,0,37,32,55,75,30}

    11

    2

    Returns: 52

  89. {19,34,25}

    16

    1

    Returns: 25

  90. {63,56,72,54,37,14,25}

    7

    2

    Returns: 51

  91. {5,60,19,0,87}

    5

    1

    Returns: 39

  92. {19,47,26}

    7

    1

    Returns: 26

  93. {7,26,12}

    5

    1

    Returns: 15

  94. {77,5,65,39}

    19

    1

    Returns: 42

  95. {65,47,36,23,54,55,16,52,33}

    5

    4

    Returns: 54

  96. {46,9,51,43,22}

    1

    1

    Returns: 86

  97. {39,35,65,6}

    5

    3

    Returns: 25

  98. {2,29,61,5}

    3

    2

    Returns: 28

  99. {3,1,14,8}

    4

    4

    Returns: -1

  100. {9,39}

    6

    3

    Returns: 8

  101. {37,0}

    7

    1

    Returns: -1

  102. {34,27,52,14,8,43,32,23,38,35}

    9

    2

    Returns: 49

  103. {80,36,67,70,86,31,68,52,71,15}

    12

    1

    Returns: 73

  104. {10, 1, 1 }

    2

    1

    Returns: 6

  105. {11, 7, 6, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    3

    2

    Returns: 117507

  106. {10000, 9999 }

    9999

    2

    Returns: -1

  107. {9, 3 }

    10

    3

    Returns: -1

  108. {100, 99, 98, 97, 96, 95, 94 }

    2

    1

    Returns: -1

  109. {90, 9, 9 }

    10

    9

    Returns: 10

  110. {100, 2, 2 }

    1

    1

    Returns: 100

  111. {1, 3, 5, 5, 5, 5, 5, 5 }

    3

    2

    Returns: -1

  112. {10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991, 9990, 9989, 9988, 9987, 9986, 9985, 9984, 9983, 9982, 9981, 9980, 9979, 9978, 9977, 9976, 9975, 9974, 9973, 9972, 9971, 9970, 9969, 9968, 9967, 9966, 9965, 9964, 9963, 9962, 9961, 9960, 9959, 9958, 9957, 9956, 9955, 9954, 9953, 9952, 9951 }

    23

    13

    Returns: 19220

  113. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    2

    1

    Returns: 250000

  114. {19, 3, 4 }

    4

    3

    Returns: 6

  115. {1, 4, 0, 2, 5 }

    3

    1

    Returns: 5

  116. {9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999, 9999 }

    2

    2

    Returns: -1

  117. {4, 4, 4, 4, 4 }

    3

    1

    Returns: 8

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: