Statistics

Problem Statement for "TheProgrammingContestDivTwo"

Problem Statement

Farmer John and Fox Brus are participating in a programming contest as a team.

The duration of the contest is T minutes and they are given N tasks. Solutions can be submitted at any time during the contest, including exactly T minutes after the start of the contest. It takes them requiredTime[i] minutes to solve the i-th task.

The score in this contest is represented by two numbers, solved and penalty. Initially both numbers are 0. If they solve a task t minutes after the start of the contest, solved increases by 1 and penalty increases by t. Two scores are compared by solved first. If two scores have different solved, the score with bigger solved is better. If two scores have the same solved, the score with smaller penalty is better.

Return a int[] containing exactly two integers that describes the best score they can get. The first integer of the return value must represent solved and the second integer must represent penalty.

Definition

Class:
TheProgrammingContestDivTwo
Method:
find
Parameters:
int, int[]
Returns:
int[]
Method signature:
int[] find(int T, int[] requiredTime)
(be sure your method is public)

Constraints

  • T will be between 1 and 100,000, inclusive.
  • requiredTime will contain between 1 and 50 elements, inclusive.
  • Each element of requiredTime will be between 1 and 100,000, inclusive.

Examples

  1. 74

    {47}

    Returns: {1, 47 }

    They can solve the task. solved will be 1 and penalty will be 47.

  2. 74

    {4747}

    Returns: {0, 0 }

    They don't have time enough to solve the task.

  3. 47

    {8, 5}

    Returns: {2, 18 }

    The order is important. If they solve task 0 first and task 1 second, solved will be 2 and penalty will be 21. If they solve task 1 first and task 0 second, solved will be 2 and penalty will be 18.

  4. 47

    {12, 3, 21, 6, 4, 13}

    Returns: {5, 86 }

  5. 58

    {4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8}

    Returns: {10, 249 }

  6. 100000

    {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000}

    Returns: {1, 100000 }

  7. 100000

    {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: {50, 1275 }

  8. 100000

    {2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000, 2000}

    Returns: {50, 2550000 }

  9. 100000

    {100000}

    Returns: {1, 100000 }

  10. 100000

    {1}

    Returns: {1, 1 }

  11. 100000

    {78655, 900, 3792, 2727, 11762, 23903, 81013, 93484, 16756, 16062, 71435, 33494, 22157, 97528, 46337, 29409, 80715, 15638, 3676, 27084, 42368, 38735, 50028, 24417, 99019, 94304, 60398, 19417, 71492, 66583, 47839, 32092, 30891, 98437, 17476, 96981, 36972, 57098, 85362, 72872, 64730, 56324, 99946, 6957, 96796, 70832, 52534, 89819, 66109, 41056}

    Returns: {10, 351773 }

  12. 100000

    {48947, 77445, 50005, 43774, 586, 78981, 15189, 99986, 13930, 14423, 21793, 54045, 77485, 96278, 38065, 40565, 72969, 15042, 70353, 53350, 73374, 98641, 4159, 80543, 95381, 47609, 2424, 1852, 20363, 22586, 45390, 30027, 5256, 25386, 14034, 22086, 73100, 63838, 85831, 84334, 42011, 99294, 77576, 90059, 31982, 33729, 63920, 15280, 46580, 81266}

    Returns: {10, 316897 }

  13. 100000

    {83474, 2314, 99075, 62766, 52487, 38912, 91761, 756, 4509, 22128, 32218, 28672, 30306, 13772, 45782, 84754, 24876, 73180, 68451, 19794, 32958, 91216, 46838, 31019, 87370, 6962, 39688, 34811, 61174, 31140, 68501, 13123, 50113, 31071, 75866, 38998, 59200, 6523, 7780, 68872, 29309, 30589, 20941, 79655, 48947, 60806, 53586, 5120, 69355, 75766}

    Returns: {10, 292073 }

  14. 100000

    {12955, 72088, 72714, 71219, 1778, 81052, 82080, 95854, 2368, 92667, 94284, 82948, 42838, 56248, 91578, 86683, 81807, 91634, 51022, 65473, 56629, 63376, 3718, 73519, 84828, 93352, 66175, 53722, 62471, 33262, 86908, 42494, 75010, 89089, 9338, 21068, 37892, 19158, 26107, 42367, 50969, 1119, 40902, 23167, 31220, 30941, 34868, 82420, 59510, 65546}

    Returns: {9, 284466 }

  15. 100000

    {26334, 30997, 30633, 63237, 81620, 32064, 14474, 58786, 62804, 49442, 5497, 85618, 52892, 66187, 351, 78395, 96650, 95225, 46816, 34731, 91856, 72061, 42222, 79175, 77907, 56628, 41701, 67914, 44751, 7126, 79248, 52453, 2285, 58944, 4705, 95070, 29632, 82445, 59045, 87294, 22305, 44290, 53245, 86370, 11496, 34645, 74035, 41912, 29871, 46555}

    Returns: {9, 283336 }

  16. 100000

    {4557, 3041, 598, 96, 2183, 2607, 2317, 1158, 2729, 3126, 3856, 665, 1904, 3546, 4895, 336, 4801, 4655, 2621, 2757, 3444, 4566, 4906, 4811, 4747, 2191, 3833, 106, 3912, 2774, 3921, 532, 722, 992, 773, 4268, 2009, 3145, 2965, 2080, 1943, 866, 320, 538, 4908, 1056, 3515, 4393, 2301, 3539}

    Returns: {43, 1456214 }

  17. 100000

    {4476, 4040, 3882, 2915, 3535, 4096, 1539, 2667, 4772, 2065, 58, 4363, 143, 867, 3081, 4667, 1910, 386, 4751, 414, 972, 4526, 3678, 4616, 4397, 1925, 4649, 1653, 4921, 3556, 3159, 2469, 1254, 4395, 369, 2995, 3056, 583, 1291, 409, 2529, 3352, 717, 2827, 197, 94, 4924, 16, 2258, 2370}

    Returns: {43, 1322710 }

  18. 100000

    {2422, 3411, 2839, 3540, 2683, 3392, 2025, 1883, 1166, 2579, 100, 2189, 2638, 2961, 4773, 2984, 3290, 4990, 2509, 4973, 1197, 3025, 4804, 4243, 1380, 4783, 648, 730, 4933, 772, 3802, 2549, 2628, 1726, 2621, 2444, 2139, 1167, 1520, 787, 2035, 1859, 202, 2707, 1739, 3994, 1838, 1378, 4472, 3768}

    Returns: {44, 1662919 }

  19. 100000

    {270, 419, 2347, 2453, 832, 3459, 4538, 3872, 1481, 1230, 3221, 3223, 4900, 1349, 281, 4670, 2525, 4632, 1551, 885, 512, 856, 990, 3932, 3288, 3682, 2512, 3942, 4656, 4029, 3508, 616, 74, 1393, 2002, 3213, 4180, 3782, 3801, 3220, 3493, 4696, 1566, 1454, 767, 4685, 1326, 503, 2744, 1869}

    Returns: {44, 1452537 }

  20. 100000

    {3269, 2906, 3234, 548, 2155, 4055, 2665, 782, 2237, 676, 4588, 3899, 2962, 4964, 877, 2325, 2457, 3827, 4751, 4321, 1596, 2587, 3241, 2921, 548, 1079, 3405, 1957, 1370, 3114, 4982, 1162, 729, 932, 4151, 1511, 2438, 4336, 1203, 787, 182, 662, 800, 3754, 4266, 1749, 3513, 4021, 1791, 4692}

    Returns: {44, 1529976 }

  21. 23166

    {1210, 308, 3154, 2036, 2755, 4064, 1660}

    Returns: {7, 44497 }

  22. 80964

    {3713, 1342, 1333, 4344, 2497, 3447, 3510, 4238}

    Returns: {8, 90274 }

  23. 93081

    {3299, 2697, 899, 2142, 4185, 2242, 4540, 3799, 254, 2786, 2148, 2448, 1081, 1657, 2871, 3064, 3005, 1244, 3753, 4777, 2784, 314, 3150, 3269, 3396, 1865}

    Returns: {26, 689142 }

  24. 40725

    {305, 3840, 4980, 1739, 1592, 3757, 781, 2732, 4792, 944, 153, 1953}

    Returns: {12, 112896 }

  25. 66505

    {614, 4953, 2085, 4251, 1606, 601, 4096, 3299, 897, 731, 3473, 3136, 3713, 4961, 3631}

    Returns: {15, 239676 }

  26. 43906

    {4064, 152, 2556, 867, 4673, 3290, 313, 4890, 801, 941, 4708, 4987, 1844, 1556, 4304, 3478, 4474, 3093, 1241}

    Returns: {17, 251084 }

  27. 3889

    {849, 3399, 4110, 3234, 1945}

    Returns: {2, 3643 }

  28. 29151

    {777, 4407, 3521, 2803, 1956, 2651, 4912, 1059, 4437, 4477, 1764, 975, 4526, 1442, 2035, 872, 3316, 1626, 1352, 3717, 4243, 3352, 3609, 1234, 2989, 891, 219, 638, 2164, 3838, 4654, 4693, 3001, 1207, 4655, 3732, 1775, 3445, 3807, 4184, 2701, 723, 3012, 4656}

    Returns: {20, 220436 }

  29. 80251

    {518, 4731, 2524, 2729, 1163, 4257, 1832, 4636, 2157, 1992, 999, 1910, 100}

    Returns: {13, 139099 }

  30. 83325

    {1615, 3668, 25, 2963, 2621, 3349}

    Returns: {6, 37964 }

  31. 47

    {8, 5 }

    Returns: {2, 18 }

  32. 100

    {20, 15, 19, 18 }

    Returns: {4, 172 }

  33. 58

    {4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8 }

    Returns: {10, 249 }

  34. 100

    {100, 100, 100, 100, 100 }

    Returns: {1, 100 }

  35. 58

    {4, 5, 82, 3, 4, 65, 7, 6, 8, 7, 6, 4, 8, 7, 6, 37, 8, 111, 123, 3, 11, 123, 333, 11112, 1231, 123, 1, 66, 55, 77, 6, 123, 6, 66 }

    Returns: {12, 291 }

  36. 47

    {12, 3, 21, 6, 4, 13 }

    Returns: {5, 86 }

  37. 10

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

    Returns: {10, 55 }

  38. 6

    {1, 2, 3 }

    Returns: {3, 10 }

  39. 47

    {12, 3, 21, 4, 13, 5 }

    Returns: {5, 83 }

  40. 74

    {4747 }

    Returns: {0, 0 }

  41. 25

    {5, 8, 5, 5, 5, 8, 8 }

    Returns: {4, 50 }

  42. 10

    {5, 5 }

    Returns: {2, 15 }

  43. 10000

    {2, 1, 3, 4, 5 }

    Returns: {5, 35 }

  44. 10

    {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    Returns: {4, 20 }

  45. 1

    {1, 1 }

    Returns: {1, 1 }

  46. 47

    {12, 3, 21, 6, 3, 13 }

    Returns: {5, 82 }

  47. 1

    {2 }

    Returns: {0, 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: