Statistics

Problem Statement for "CuttingGrass"

Problem Statement

There are N blades of grass in Fox Ciel's garden numbered 0 to N-1. Since she doesn't like tall grass, she wants to make it so that the sum of heights of all grass blades is at most H.

At time 0, the height of the i-th grass blade is init[i]. At each positive integer time t, the following activities happen (in the specified relative order):

1. First, for each i, 0 &le i &lt N, the i-th grass blade becomes higher by grow[i].
2. Then, Ciel chooses a single grass blade and cuts it. The height of this grass blade becomes zero.
3. Finally, Ciel calculates the sum of heights of all grass blades. If it is at most H, then she considers her goal achieved.

Return the earliest possible time she can achieve her goal. If the sum of heights of all grass blades doesn't exceed H at time 0, return 0. If it's impossible to achieve the goal, return -1.

Definition

Class:
CuttingGrass
Method:
theMin
Parameters:
int[], int[], int
Returns:
int
Method signature:
int theMin(int[] init, int[] grow, int H)
(be sure your method is public)

Constraints

  • init will contain between 1 and 50 elements, inclusive.
  • init and grow will contain the same number of elements.
  • Each element of init will be between 0 and 100,000, inclusive.
  • Each element of grow will be between 1 and 100,000, inclusive.
  • H will be between 0 and 1,000,000, inclusive.

Examples

  1. {5, 8, 58}

    {2, 1, 1}

    16

    Returns: 1

    At time 1: The heights of grass blades 0, 1, 2 become 7, 9, 59, respectively. Suppose that Ciel cuts grass blade 2. The height of grass blade 2 becomes zero. The sum of heights of all grass blades is 7 + 9 + 0 = 16, so she achieves her goal.

  2. {5, 8}

    {2, 1}

    58

    Returns: 0

    At time 0, the sum of heights of all grass blades is 13 and doesn't exceed H.

  3. {5, 8}

    {2, 1}

    0

    Returns: -1

    It's impossible to achieve the goal.

  4. {5, 1, 6, 5, 8, 4, 7}

    {2, 1, 1, 1, 4, 3, 2}

    33

    Returns: 5

    One of the optimal strategies is to cut grass blade 2, 0, 6, 5, 4 (0-indexed) at time 1, 2, 3, 4, 5 respectively.

  5. {49, 13, 62, 95, 69, 75, 62, 96, 97, 22, 69, 69, 52}

    {7, 2, 4, 3, 6, 5, 7, 6, 5, 4, 7, 7, 4}

    517

    Returns: 8

  6. {27452, 7066, 27676, 42510, 1298, 281, 25087, 37955, 47657, 11828, 14803, 46075, 45122, 23486, 489, 2393, 21128, 29058, 34225, 23953, 10743, 17065, 31508, 26232, 16120, 35255, 36787, 35940, 10925, 43039, 49305, 23639, 27759, 29905, 13878, 6817, 18327, 21164, 16832, 49286, 1358, 40187, 21455, 23173, 10964, 5544, 37282, 4167, 18200, 48396}

    {899, 661, 388, 733, 786, 70, 176, 622, 27, 878, 958, 988, 983, 259, 949, 712, 333, 296, 22, 661, 593, 332, 409, 635, 498, 919, 731, 9, 484, 863, 754, 344, 336, 7, 863, 929, 383, 770, 206, 648, 59, 306, 313, 771, 687, 544, 380, 21, 37, 720}

    1000000

    Returns: 9

  7. {39345, 577, 628, 1456, 558, 13268, 30376, 44622, 11057, 21302, 1215, 27559, 23675, 44154, 18449, 23710, 19244, 32419, 4496, 4800, 45034, 9374, 19788, 30383, 16579, 43346, 11022, 17611, 12658, 20354, 38351, 25479, 2460, 23964, 13765, 5763, 13013, 24076, 11684, 23631, 33498, 23603, 14690, 41150, 10583, 42512, 22402, 46122, 22426, 32585}

    {460, 744, 433, 90, 233, 60, 167, 136, 121, 851, 639, 147, 73, 668, 271, 441, 793, 1000, 176, 550, 59, 455, 278, 356, 705, 864, 68, 474, 7, 117, 540, 79, 480, 733, 755, 836, 854, 353, 539, 143, 866, 492, 967, 191, 333, 588, 282, 246, 992, 279}

    1000000

    Returns: 3

  8. {42544, 35710, 7085, 4007, 34386, 5302, 28913, 6545, 37453, 2227, 31335, 44024, 21063, 38397, 27717, 46086, 32456, 38217, 25859, 345, 16841, 23610, 35876, 13544, 1870, 49020, 45994, 23368, 532, 36835, 18715, 18089, 31456, 9504, 39857, 5832, 12116, 6351, 26604, 16086, 486, 25735, 6979, 19895, 21119, 47423, 10154, 1497, 2078, 20201}

    {220, 840, 148, 744, 21, 36, 653, 634, 890, 537, 273, 411, 960, 415, 694, 954, 934, 599, 577, 561, 915, 864, 354, 313, 639, 438, 25, 303, 127, 743, 914, 537, 855, 390, 277, 325, 760, 214, 498, 682, 631, 723, 593, 732, 625, 423, 712, 393, 351, 635}

    1000000

    Returns: 5

  9. {48626, 45854, 11602, 8368, 43119, 6356, 35241, 33063, 43150, 38322, 43449, 3749, 26046, 14059, 37168, 1684, 14759, 26276, 34438, 11969, 9461, 24963, 15896, 14676, 10675, 15947, 6090, 27846, 23625, 2535, 25639, 25889, 28439, 35980, 12460, 9214, 44752, 29075, 28248, 11585, 28850, 24122, 16610, 33056, 33098, 32009, 46245, 22177, 12744, 27479}

    {94, 832, 809, 737, 940, 63, 525, 232, 758, 434, 870, 988, 201, 689, 537, 709, 472, 781, 589, 229, 54, 534, 143, 741, 894, 123, 14, 165, 440, 402, 282, 400, 849, 593, 838, 542, 486, 729, 851, 940, 843, 789, 897, 1, 523, 173, 904, 933, 996, 303}

    1000000

    Returns: 12

  10. {22381, 24683, 26513, 17915, 8739, 12817, 19927, 25661, 6504, 10331, 45030, 4697, 37704, 47856, 8654, 5075, 5364, 31037, 43996, 10697, 46672, 15163, 8747, 20508, 30605, 27321, 30549, 16844, 37995, 23947, 9277, 16244, 31481, 40231, 8551, 37641, 21065, 28536, 45553, 42519, 44690, 15414, 41961, 47017, 33694, 17452, 24930, 735, 33511, 27867}

    {323, 432, 183, 127, 372, 543, 498, 484, 421, 825, 519, 998, 203, 754, 920, 19, 575, 169, 411, 480, 74, 198, 818, 221, 661, 417, 39, 760, 838, 415, 526, 819, 976, 762, 335, 273, 257, 881, 807, 38, 955, 944, 646, 390, 721, 188, 962, 777, 405, 836}

    1000000

    Returns: 11

  11. {1231, 1536, 1519, 1940, 1539, 1385, 1599, 1613, 1394, 1803, 1763, 1706, 1863, 1452, 1818, 1914, 1386, 1954, 1496, 1722, 1616, 1862, 1755, 1215, 1233, 1078, 1448, 1241, 1732, 1561, 1633, 1307, 1844, 1911, 1371, 1338, 1989, 1789, 1656, 1413, 1929, 1182, 1815, 1474, 1540, 1797, 1586, 1427, 1996, 1202}

    {86, 55, 2, 86, 96, 71, 81, 53, 79, 22, 23, 8, 69, 32, 35, 39, 30, 18, 92, 64, 88, 1, 48, 81, 91, 75, 44, 77, 3, 33, 9, 52, 56, 4, 19, 73, 52, 18, 8, 77, 91, 59, 50, 62, 42, 87, 89, 24, 71, 67}

    63601

    Returns: 36

  12. {1231, 1536, 1519, 1940, 1539, 1385, 1599, 1613, 1394, 1803, 1763, 1706, 1863, 1452, 1818, 1914, 1386, 1954, 1496, 1722, 1616, 1862, 1755, 1215, 1233, 1078, 1448, 1241, 1732, 1561, 1633, 1307, 1844, 1911, 1371, 1338, 1989, 1789, 1656, 1413, 1929, 1182, 1815, 1474, 1540, 1797, 1586, 1427, 1996, 1202}

    {86, 55, 2, 86, 96, 71, 81, 53, 79, 22, 23, 8, 69, 32, 35, 39, 30, 18, 92, 64, 88, 1, 48, 81, 91, 75, 44, 77, 3, 33, 9, 52, 56, 4, 19, 73, 52, 18, 8, 77, 91, 59, 50, 62, 42, 87, 89, 24, 71, 67}

    63600

    Returns: 37

  13. {1889, 1958, 1825, 1304, 1555, 1437, 1697, 1607, 1129, 1639, 1600, 1791, 1029, 1194, 1608, 1713, 1792, 1807, 1932, 1158, 1738, 1919, 1821, 1360, 1148, 1769, 1643, 1577, 1045, 1809, 1512, 1181, 1351, 1476, 1267, 1607, 1858, 1676, 1402, 1547, 1265, 1554, 1831, 1808, 1885, 1550, 1764, 1415, 1609, 1270}

    {65, 13, 90, 68, 36, 68, 32, 58, 70, 100, 30, 75, 34, 76, 57, 77, 40, 30, 79, 99, 100, 49, 35, 54, 7, 2, 3, 82, 29, 17, 79, 38, 9, 93, 49, 80, 14, 36, 54, 98, 96, 37, 42, 45, 54, 22, 21, 52, 66, 76}

    52041

    Returns: 44

  14. {1889, 1958, 1825, 1304, 1555, 1437, 1697, 1607, 1129, 1639, 1600, 1791, 1029, 1194, 1608, 1713, 1792, 1807, 1932, 1158, 1738, 1919, 1821, 1360, 1148, 1769, 1643, 1577, 1045, 1809, 1512, 1181, 1351, 1476, 1267, 1607, 1858, 1676, 1402, 1547, 1265, 1554, 1831, 1808, 1885, 1550, 1764, 1415, 1609, 1270}

    {65, 13, 90, 68, 36, 68, 32, 58, 70, 100, 30, 75, 34, 76, 57, 77, 40, 30, 79, 99, 100, 49, 35, 54, 7, 2, 3, 82, 29, 17, 79, 38, 9, 93, 49, 80, 14, 36, 54, 98, 96, 37, 42, 45, 54, 22, 21, 52, 66, 76}

    52040

    Returns: 45

  15. {1448, 1646, 1737, 1029, 1239, 1956, 1421, 1162, 1580, 1438, 1283, 1600, 1722, 1466, 1944, 1337, 1464, 1457, 1180, 1734, 1700, 1949, 1530, 1988, 1679, 1465, 1360, 1735, 1187, 1357, 1319, 1884, 1948, 1554, 1918, 1934, 1863, 1486, 1136, 1291, 1894, 1360, 1448, 1264, 1603, 1356, 1665, 1825, 1187, 1639}

    {22, 81, 62, 29, 63, 71, 43, 39, 56, 52, 92, 54, 10, 45, 78, 23, 12, 75, 56, 51, 72, 53, 90, 49, 92, 85, 86, 77, 21, 69, 8, 87, 58, 86, 28, 36, 80, 55, 82, 73, 60, 46, 66, 22, 63, 90, 66, 1, 98, 88}

    83108

    Returns: 0

  16. {1448, 1646, 1737, 1029, 1239, 1956, 1421, 1162, 1580, 1438, 1283, 1600, 1722, 1466, 1944, 1337, 1464, 1457, 1180, 1734, 1700, 1949, 1530, 1988, 1679, 1465, 1360, 1735, 1187, 1357, 1319, 1884, 1948, 1554, 1918, 1934, 1863, 1486, 1136, 1291, 1894, 1360, 1448, 1264, 1603, 1356, 1665, 1825, 1187, 1639}

    {22, 81, 62, 29, 63, 71, 43, 39, 56, 52, 92, 54, 10, 45, 78, 23, 12, 75, 56, 51, 72, 53, 90, 49, 92, 85, 86, 77, 21, 69, 8, 87, 58, 86, 28, 36, 80, 55, 82, 73, 60, 46, 66, 22, 63, 90, 66, 1, 98, 88}

    83107

    Returns: 0

  17. {1926, 1957, 1069, 1136, 1390, 1817, 1037, 1113, 1020, 1530, 1221, 1989, 1721, 1826, 1922, 1293, 1412, 1671, 1691, 1360, 1620, 1554, 1901, 1624, 1816, 1064, 1904, 1353, 1993, 1051, 1358, 1297, 1907, 1444, 1850, 1873, 1434, 1111, 1933, 1200, 1939, 1032, 1689, 1849, 1315, 1381, 1155, 1545, 1936, 1376}

    {65, 61, 42, 17, 2, 98, 26, 82, 32, 40, 21, 6, 54, 45, 70, 41, 12, 26, 30, 57, 80, 99, 19, 12, 21, 80, 25, 61, 31, 39, 52, 40, 54, 55, 75, 6, 49, 19, 67, 26, 44, 2, 7, 68, 72, 64, 47, 99, 88, 38}

    43412

    Returns: 44

  18. {1926, 1957, 1069, 1136, 1390, 1817, 1037, 1113, 1020, 1530, 1221, 1989, 1721, 1826, 1922, 1293, 1412, 1671, 1691, 1360, 1620, 1554, 1901, 1624, 1816, 1064, 1904, 1353, 1993, 1051, 1358, 1297, 1907, 1444, 1850, 1873, 1434, 1111, 1933, 1200, 1939, 1032, 1689, 1849, 1315, 1381, 1155, 1545, 1936, 1376}

    {65, 61, 42, 17, 2, 98, 26, 82, 32, 40, 21, 6, 54, 45, 70, 41, 12, 26, 30, 57, 80, 99, 19, 12, 21, 80, 25, 61, 31, 39, 52, 40, 54, 55, 75, 6, 49, 19, 67, 26, 44, 2, 7, 68, 72, 64, 47, 99, 88, 38}

    43411

    Returns: 45

  19. {1771, 1620, 1250, 1140, 1349, 1669, 1824, 1364, 1622, 1563, 1895, 1536, 1469, 1531, 1111, 1714, 1258, 1438, 1487, 1844, 1122, 1418, 1845, 1587, 1761, 1614, 1500, 1307, 1407, 1377, 1424, 1476, 1357, 1275, 1647, 1385, 1724, 1264, 1940, 1530, 1278, 1231, 1625, 1217, 1104, 1168, 1690, 1694, 1462, 1101}

    {97, 45, 99, 61, 1, 40, 53, 1, 83, 42, 95, 77, 21, 25, 96, 10, 61, 12, 86, 45, 64, 5, 64, 64, 61, 25, 83, 5, 44, 60, 46, 97, 97, 74, 12, 96, 73, 18, 22, 86, 62, 10, 59, 96, 65, 41, 87, 3, 100, 89}

    79597

    Returns: 0

  20. {1771, 1620, 1250, 1140, 1349, 1669, 1824, 1364, 1622, 1563, 1895, 1536, 1469, 1531, 1111, 1714, 1258, 1438, 1487, 1844, 1122, 1418, 1845, 1587, 1761, 1614, 1500, 1307, 1407, 1377, 1424, 1476, 1357, 1275, 1647, 1385, 1724, 1264, 1940, 1530, 1278, 1231, 1625, 1217, 1104, 1168, 1690, 1694, 1462, 1101}

    {97, 45, 99, 61, 1, 40, 53, 1, 83, 42, 95, 77, 21, 25, 96, 10, 61, 12, 86, 45, 64, 5, 64, 64, 61, 25, 83, 5, 44, 60, 46, 97, 97, 74, 12, 96, 73, 18, 22, 86, 62, 10, 59, 96, 65, 41, 87, 3, 100, 89}

    79596

    Returns: 0

  21. {1591, 1016, 1910, 1612, 1318, 1711, 1030, 1560, 1428, 1181, 1997, 1539, 1105, 1999, 1249, 1770, 1911, 1135, 1363, 1903, 1861, 1515, 1617, 1795, 1567, 1587, 1382, 1752, 1734, 1036, 1512, 1164, 1275, 1706, 1610, 1140, 1295, 1654, 1936, 1313, 1091, 1845, 1489, 1309, 1842, 1747, 1230, 1298, 1542, 1585}

    {54, 41, 88, 8, 34, 7, 92, 38, 88, 95, 84, 97, 22, 50, 67, 70, 26, 13, 37, 29, 72, 49, 81, 26, 8, 17, 87, 20, 88, 15, 9, 80, 87, 16, 59, 19, 97, 3, 53, 15, 93, 11, 92, 31, 85, 26, 38, 86, 19, 85}

    56755

    Returns: 36

  22. {1591, 1016, 1910, 1612, 1318, 1711, 1030, 1560, 1428, 1181, 1997, 1539, 1105, 1999, 1249, 1770, 1911, 1135, 1363, 1903, 1861, 1515, 1617, 1795, 1567, 1587, 1382, 1752, 1734, 1036, 1512, 1164, 1275, 1706, 1610, 1140, 1295, 1654, 1936, 1313, 1091, 1845, 1489, 1309, 1842, 1747, 1230, 1298, 1542, 1585}

    {54, 41, 88, 8, 34, 7, 92, 38, 88, 95, 84, 97, 22, 50, 67, 70, 26, 13, 37, 29, 72, 49, 81, 26, 8, 17, 87, 20, 88, 15, 9, 80, 87, 16, 59, 19, 97, 3, 53, 15, 93, 11, 92, 31, 85, 26, 38, 86, 19, 85}

    56754

    Returns: 37

  23. {1544, 1936, 1350, 1748, 1706, 1861, 1288, 1093, 1603, 1550, 1342, 1634, 1072, 1046, 1764, 1313, 1001, 1146, 1737, 1492, 1161, 1436, 1209, 1605, 1146, 1132, 1367, 1978, 1499, 1536, 1019, 1034, 1098, 1932, 1516, 1038, 1236, 1071, 1450, 1038, 1497, 1029, 1256, 1161, 1943, 1497, 1971, 1818, 1382, 1411}

    {5, 2, 89, 28, 13, 86, 30, 4, 15, 41, 21, 97, 98, 76, 34, 98, 23, 66, 3, 41, 21, 50, 17, 15, 82, 24, 40, 20, 88, 27, 11, 6, 6, 41, 98, 16, 39, 40, 51, 98, 8, 29, 34, 63, 34, 31, 76, 33, 14, 73}

    65391

    Returns: 17

  24. {1544, 1936, 1350, 1748, 1706, 1861, 1288, 1093, 1603, 1550, 1342, 1634, 1072, 1046, 1764, 1313, 1001, 1146, 1737, 1492, 1161, 1436, 1209, 1605, 1146, 1132, 1367, 1978, 1499, 1536, 1019, 1034, 1098, 1932, 1516, 1038, 1236, 1071, 1450, 1038, 1497, 1029, 1256, 1161, 1943, 1497, 1971, 1818, 1382, 1411}

    {5, 2, 89, 28, 13, 86, 30, 4, 15, 41, 21, 97, 98, 76, 34, 98, 23, 66, 3, 41, 21, 50, 17, 15, 82, 24, 40, 20, 88, 27, 11, 6, 6, 41, 98, 16, 39, 40, 51, 98, 8, 29, 34, 63, 34, 31, 76, 33, 14, 73}

    65390

    Returns: 18

  25. {1187, 1909, 1352, 1486, 1587, 1380, 1098, 1774, 1053, 1729, 1455, 1088, 1119, 1553, 1099, 1498, 1385, 1893, 1703, 1066, 1342, 1995, 1544, 1352, 1039, 1017, 1975, 1512, 1856, 1311, 1688, 1918, 1341, 1280, 1447, 1923, 1073, 1400, 1802, 1959, 1197, 1869, 1565, 1237, 1513, 1808, 1434, 1198, 1104, 1877}

    {94, 92, 28, 10, 88, 66, 66, 76, 36, 18, 13, 86, 83, 61, 80, 31, 66, 17, 88, 79, 63, 95, 50, 53, 41, 71, 91, 6, 86, 82, 4, 58, 4, 66, 99, 22, 14, 54, 1, 11, 100, 48, 63, 32, 67, 9, 96, 67, 15, 68}

    60018

    Returns: 38

  26. {1187, 1909, 1352, 1486, 1587, 1380, 1098, 1774, 1053, 1729, 1455, 1088, 1119, 1553, 1099, 1498, 1385, 1893, 1703, 1066, 1342, 1995, 1544, 1352, 1039, 1017, 1975, 1512, 1856, 1311, 1688, 1918, 1341, 1280, 1447, 1923, 1073, 1400, 1802, 1959, 1197, 1869, 1565, 1237, 1513, 1808, 1434, 1198, 1104, 1877}

    {94, 92, 28, 10, 88, 66, 66, 76, 36, 18, 13, 86, 83, 61, 80, 31, 66, 17, 88, 79, 63, 95, 50, 53, 41, 71, 91, 6, 86, 82, 4, 58, 4, 66, 99, 22, 14, 54, 1, 11, 100, 48, 63, 32, 67, 9, 96, 67, 15, 68}

    60017

    Returns: 39

  27. {1516, 1114, 1281, 1701, 1754, 1246, 1953, 1398, 1257, 1879, 1533, 1846, 1654, 1153, 1937, 1534, 1534, 1338, 1425, 1375, 1318, 1560, 1465, 1324, 1637, 1718, 1396, 1723, 1292, 1860, 1300, 1428, 1526, 1091, 1988, 1226, 1718, 1643, 1793, 1032, 1887, 1497, 1696, 1971, 1361, 2000, 1418, 1401, 1309, 1671}

    {60, 44, 84, 31, 63, 6, 77, 75, 35, 32, 40, 4, 19, 14, 34, 18, 25, 82, 73, 9, 94, 19, 58, 34, 22, 15, 78, 42, 97, 84, 13, 99, 13, 75, 46, 2, 11, 94, 17, 24, 44, 95, 26, 19, 16, 93, 29, 56, 20, 51}

    75627

    Returns: 11

  28. {1516, 1114, 1281, 1701, 1754, 1246, 1953, 1398, 1257, 1879, 1533, 1846, 1654, 1153, 1937, 1534, 1534, 1338, 1425, 1375, 1318, 1560, 1465, 1324, 1637, 1718, 1396, 1723, 1292, 1860, 1300, 1428, 1526, 1091, 1988, 1226, 1718, 1643, 1793, 1032, 1887, 1497, 1696, 1971, 1361, 2000, 1418, 1401, 1309, 1671}

    {60, 44, 84, 31, 63, 6, 77, 75, 35, 32, 40, 4, 19, 14, 34, 18, 25, 82, 73, 9, 94, 19, 58, 34, 22, 15, 78, 42, 97, 84, 13, 99, 13, 75, 46, 2, 11, 94, 17, 24, 44, 95, 26, 19, 16, 93, 29, 56, 20, 51}

    75626

    Returns: 12

  29. {1800, 1452, 1318, 1857, 1415, 1663, 1890, 1759, 1925, 1860, 1812, 1561, 1969, 1385, 1095, 1816, 1249, 1030, 1251, 1093, 1210, 1493, 1230, 1893, 1206, 1529, 1943, 1473, 1028, 1631, 1466, 1142, 1481, 1175, 1155, 1318, 1242, 1927, 1008, 1690, 1187, 1960, 1667, 1930, 1070, 1868, 1259, 1428, 1723, 1608}

    {17, 35, 1, 42, 100, 38, 18, 20, 27, 91, 40, 69, 68, 27, 98, 61, 31, 49, 41, 36, 39, 80, 12, 35, 76, 57, 55, 64, 67, 21, 11, 13, 36, 41, 67, 36, 31, 1, 17, 23, 9, 27, 2, 67, 95, 42, 19, 43, 96, 23}

    54929

    Returns: 32

  30. {1800, 1452, 1318, 1857, 1415, 1663, 1890, 1759, 1925, 1860, 1812, 1561, 1969, 1385, 1095, 1816, 1249, 1030, 1251, 1093, 1210, 1493, 1230, 1893, 1206, 1529, 1943, 1473, 1028, 1631, 1466, 1142, 1481, 1175, 1155, 1318, 1242, 1927, 1008, 1690, 1187, 1960, 1667, 1930, 1070, 1868, 1259, 1428, 1723, 1608}

    {17, 35, 1, 42, 100, 38, 18, 20, 27, 91, 40, 69, 68, 27, 98, 61, 31, 49, 41, 36, 39, 80, 12, 35, 76, 57, 55, 64, 67, 21, 11, 13, 36, 41, 67, 36, 31, 1, 17, 23, 9, 27, 2, 67, 95, 42, 19, 43, 96, 23}

    54928

    Returns: 33

  31. {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}

    {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}

    50

    Returns: 0

  32. {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}

    {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}

    49

    Returns: -1

  33. {100000}

    {100000}

    0

    Returns: 1

  34. {0}

    {1}

    0

    Returns: 0

  35. {1586, 1808, 1761, 1209, 1157, 1652, 1279, 1827, 1498, 1670, 1075, 1008, 1623, 1064, 1230, 1034, 1653, 1701, 1373, 1118, 1607, 1139, 1792, 1045, 1958, 1976, 1982, 1660, 1439, 1332, 1256, 1448, 1277, 1225, 1158, 1342, 1946, 1997, 1445, 1300, 1938, 1133, 1567, 1787, 1569, 1245, 1700, 1191, 1427, 1243}

    {19, 26, 38, 33, 73, 10, 27, 46, 74, 93, 29, 27, 28, 82, 84, 20, 95, 87, 24, 85, 50, 5, 24, 2, 25, 19, 13, 56, 15, 93, 43, 34, 13, 89, 11, 70, 16, 62, 23, 81, 47, 21, 43, 7, 56, 12, 77, 36, 6, 83}

    73450

    Returns: 0

  36. {1586, 1808, 1761, 1209, 1157, 1652, 1279, 1827, 1498, 1670, 1075, 1008, 1623, 1064, 1230, 1034, 1653, 1701, 1373, 1118, 1607, 1139, 1792, 1045, 1958, 1976, 1982, 1660, 1439, 1332, 1256, 1448, 1277, 1225, 1158, 1342, 1946, 1997, 1445, 1300, 1938, 1133, 1567, 1787, 1569, 1245, 1700, 1191, 1427, 1243}

    {19, 26, 38, 33, 73, 10, 27, 46, 74, 93, 29, 27, 28, 82, 84, 20, 95, 87, 24, 85, 50, 5, 24, 2, 25, 19, 13, 56, 15, 93, 43, 34, 13, 89, 11, 70, 16, 62, 23, 81, 47, 21, 43, 7, 56, 12, 77, 36, 6, 83}

    73449

    Returns: 7

  37. {1677, 1507, 1915, 1301, 1026, 1206, 1976, 1067, 1536, 1855, 1942, 1602, 1071, 1026, 1669, 1330, 1141, 1751, 1884, 1264, 1920, 1708, 1104, 1955, 1535, 1415, 1942, 1328, 1240, 1068, 1719, 1216, 1353, 1178, 1549, 1919, 1336, 1213, 1428, 1510, 1969, 1748, 1466, 1872, 1678, 1512, 1618, 1111, 1985, 1413}

    {98, 55, 51, 39, 73, 43, 34, 38, 13, 3, 55, 51, 46, 84, 13, 41, 12, 90, 10, 95, 9, 18, 14, 41, 69, 18, 46, 17, 88, 85, 47, 48, 97, 65, 63, 68, 16, 97, 92, 58, 33, 64, 81, 54, 49, 37, 48, 54, 26, 7}

    40487

    Returns: 50

  38. {1677, 1507, 1915, 1301, 1026, 1206, 1976, 1067, 1536, 1855, 1942, 1602, 1071, 1026, 1669, 1330, 1141, 1751, 1884, 1264, 1920, 1708, 1104, 1955, 1535, 1415, 1942, 1328, 1240, 1068, 1719, 1216, 1353, 1178, 1549, 1919, 1336, 1213, 1428, 1510, 1969, 1748, 1466, 1872, 1678, 1512, 1618, 1111, 1985, 1413}

    {98, 55, 51, 39, 73, 43, 34, 38, 13, 3, 55, 51, 46, 84, 13, 41, 12, 90, 10, 95, 9, 18, 14, 41, 69, 18, 46, 17, 88, 85, 47, 48, 97, 65, 63, 68, 16, 97, 92, 58, 33, 64, 81, 54, 49, 37, 48, 54, 26, 7}

    40486

    Returns: -1

  39. {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}

    {91, 14, 17, 69, 14, 85, 93, 33, 11, 16, 67, 67, 47, 82, 2, 1, 92, 90, 30, 18, 31, 14, 23, 73, 72, 99, 10, 18, 53, 10, 47, 37, 25, 44, 18, 69, 51, 42, 32, 35, 87, 98, 84, 85, 83, 82, 74, 97, 92, 88}

    72196

    Returns: 34

  40. {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}

    {91, 14, 17, 69, 14, 85, 93, 33, 11, 16, 67, 67, 47, 82, 2, 1, 92, 90, 30, 18, 31, 14, 23, 73, 72, 99, 10, 18, 53, 10, 47, 37, 25, 44, 18, 69, 51, 42, 32, 35, 87, 98, 84, 85, 83, 82, 74, 97, 92, 88}

    72195

    Returns: 35

  41. {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}

    {31, 74, 81, 85, 88, 82, 66, 53, 59, 99, 46, 40, 50, 83, 69, 59, 80, 73, 23, 79, 75, 1, 92, 79, 85, 70, 45, 86, 66, 35, 99, 35, 59, 73, 60, 61, 33, 10, 14, 92, 77, 18, 65, 20, 81, 58, 63, 88, 92, 48}

    103393

    Returns: 0

  42. {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}

    {31, 74, 81, 85, 88, 82, 66, 53, 59, 99, 46, 40, 50, 83, 69, 59, 80, 73, 23, 79, 75, 1, 92, 79, 85, 70, 45, 86, 66, 35, 99, 35, 59, 73, 60, 61, 33, 10, 14, 92, 77, 18, 65, 20, 81, 58, 63, 88, 92, 48}

    103392

    Returns: 0

  43. {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}

    {76, 65, 77, 41, 53, 100, 42, 84, 97, 51, 34, 72, 64, 22, 10, 76, 9, 5, 12, 60, 13, 30, 70, 26, 32, 33, 9, 28, 66, 90, 97, 6, 92, 31, 19, 59, 3, 46, 51, 56, 29, 34, 40, 21, 87, 76, 87, 21, 46, 73}

    96498

    Returns: 14

  44. {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}

    {76, 65, 77, 41, 53, 100, 42, 84, 97, 51, 34, 72, 64, 22, 10, 76, 9, 5, 12, 60, 13, 30, 70, 26, 32, 33, 9, 28, 66, 90, 97, 6, 92, 31, 19, 59, 3, 46, 51, 56, 29, 34, 40, 21, 87, 76, 87, 21, 46, 73}

    96497

    Returns: 15

  45. {1940, 1539, 1385, 1599, 1613, 1394, 1803, 1763, 1706, 1863, 1452, 1818, 1914, 1386, 1954, 1496, 1722, 1616, 1862, 1755, 1215, 1233, 1078, 1448, 1241, 1732, 1561, 1633, 1307, 1844, 1911, 1371, 1338, 1989, 1789, 1656, 1413, 1929, 1182, 1815, 1474, 1540, 1797, 1586, 1427, 1996, 1202, 1701, 1731, 1538}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    123578

    Returns: 0

  46. {1940, 1539, 1385, 1599, 1613, 1394, 1803, 1763, 1706, 1863, 1452, 1818, 1914, 1386, 1954, 1496, 1722, 1616, 1862, 1755, 1215, 1233, 1078, 1448, 1241, 1732, 1561, 1633, 1307, 1844, 1911, 1371, 1338, 1989, 1789, 1656, 1413, 1929, 1182, 1815, 1474, 1540, 1797, 1586, 1427, 1996, 1202, 1701, 1731, 1538}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    123577

    Returns: 0

  47. {1304, 1555, 1437, 1697, 1607, 1129, 1639, 1600, 1791, 1029, 1194, 1608, 1713, 1792, 1807, 1932, 1158, 1738, 1919, 1821, 1360, 1148, 1769, 1643, 1577, 1045, 1809, 1512, 1181, 1351, 1476, 1267, 1607, 1858, 1676, 1402, 1547, 1265, 1554, 1831, 1808, 1885, 1550, 1764, 1415, 1609, 1270, 1387, 1132, 1616}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    130173

    Returns: 0

  48. {1304, 1555, 1437, 1697, 1607, 1129, 1639, 1600, 1791, 1029, 1194, 1608, 1713, 1792, 1807, 1932, 1158, 1738, 1919, 1821, 1360, 1148, 1769, 1643, 1577, 1045, 1809, 1512, 1181, 1351, 1476, 1267, 1607, 1858, 1676, 1402, 1547, 1265, 1554, 1831, 1808, 1885, 1550, 1764, 1415, 1609, 1270, 1387, 1132, 1616}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    130172

    Returns: 0

  49. {1029, 1239, 1956, 1421, 1162, 1580, 1438, 1283, 1600, 1722, 1466, 1944, 1337, 1464, 1457, 1180, 1734, 1700, 1949, 1530, 1988, 1679, 1465, 1360, 1735, 1187, 1357, 1319, 1884, 1948, 1554, 1918, 1934, 1863, 1486, 1136, 1291, 1894, 1360, 1448, 1264, 1603, 1356, 1665, 1825, 1187, 1639, 1231, 1139, 1109}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    87174

    Returns: 0

  50. {1029, 1239, 1956, 1421, 1162, 1580, 1438, 1283, 1600, 1722, 1466, 1944, 1337, 1464, 1457, 1180, 1734, 1700, 1949, 1530, 1988, 1679, 1465, 1360, 1735, 1187, 1357, 1319, 1884, 1948, 1554, 1918, 1934, 1863, 1486, 1136, 1291, 1894, 1360, 1448, 1264, 1603, 1356, 1665, 1825, 1187, 1639, 1231, 1139, 1109}

    {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

    87173

    Returns: 0

  51. {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}

    {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}

    1225

    Returns: 50

  52. {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}

    {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}

    1224

    Returns: -1

  53. {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}

    {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}

    801197

    Returns: 42

  54. {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}

    {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}

    801196

    Returns: 43

  55. {57050}

    {51131}

    57050

    Returns: 0

  56. {57050}

    {51131}

    57049

    Returns: 1

  57. {58100}

    {22951}

    0

    Returns: 1

  58. {1231, 1536, 1519, 1940, 1539, 1385, 1599, 1613, 1394, 1803, 1763, 1706, 1863, 1452, 1818, 1914, 1386, 1954, 1496, 1722, 1616, 1862, 1755, 1215, 1233, 1078, 1448, 1241, 1732, 1561, 1633, 1307, 1844, 1911, 1371, 1338, 1989, 1789, 1656, 1413, 1929, 1182, 1815, 1474, 1540, 1797, 1586, 1427, 1996, 1202 }

    {86, 55, 2, 86, 96, 71, 81, 53, 79, 22, 23, 8, 69, 32, 35, 39, 30, 18, 92, 64, 88, 1, 48, 81, 91, 75, 44, 77, 3, 33, 9, 52, 56, 4, 19, 73, 52, 18, 8, 77, 91, 59, 50, 62, 42, 87, 89, 24, 71, 67 }

    63601

    Returns: 36

  59. {5, 1, 6, 5, 8, 4, 7 }

    {2, 1, 1, 1, 4, 3, 2 }

    33

    Returns: 5

  60. {5, 8, 58 }

    {2, 1, 1 }

    16

    Returns: 1

  61. {5, 6, 7, 8, 9 }

    {1, 1, 1, 1, 2 }

    11

    Returns: 5

  62. {1 }

    {1 }

    5

    Returns: 0

  63. {100, 100, 100 }

    {1, 1, 100 }

    20

    Returns: 3

  64. {100, 150, 200, 600 }

    {500, 1000, 2405, 5405 }

    1

    Returns: -1

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: