Statistics

Problem Statement for "BuildingCities"

Problem Statement

There is a country with N cities. The cities are located on a two-dimensional plane. The coordinates of the i-th city are given in cityX[i] and cityY[i]. The 0-th city is the capital city while the (N-1)-th city is the center of the market (0-based indexing). Each city is assumed to be a point.

The distance that a citizen needs to travel from one city to another is equal to the Euclidian distance between them. A citizen can travel directly from one city to another if the Euclidian distance does not exceed maxDirect (since they can only carry a limited amount of supplies). Hence, if a citizen wants to go from the capital city to the center of the market then he may need to visit some cities in the journey to restock some supplies.

The king wants to reduce the minimum total distance that a citizen needs to travel from the capital city to the center of the market. He wants this minimum distance to not exceed maxTravel. In order to do so he will create some new cities in the country (he can do so at any coordinates not necessarily integer).

Return the minimum number of new cities needed to be built to achieve his target or -1 if it is impossible.

Definition

Class:
BuildingCities
Method:
findMinimumCities
Parameters:
int, int, int[], int[]
Returns:
int
Method signature:
int findMinimumCities(int maxDirect, int maxTravel, int[] cityX, int[] cityY)
(be sure your method is public)

Notes

  • The Euclidian distance between two points (X1,Y1) and (X2,Y2) is defined as the square root of ((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)).

Constraints

  • maxDirect and maxTravel will be between 1 and 2000, inclusive.
  • cityX and cityY will contain between 2 and 50 elements, inclusive.
  • cityX and cityY will contain the same number of elements.
  • Each element of cityX and cityY will be between 0 and 2000, inclusive.
  • All cities will have distinct locations.
  • To avoid precision problems, if the answer for an input is X >= 0, then it will be possible to build X cities in such way that the minimal travel distance between the capital city and the center of the market is at most maxTravel - 1e-5, and any way of building fewer than X cities will result in this minimal distance being at least maxTravel + 1e-5.

Examples

  1. 1

    5

    {0,0,0,1,2,2,3}

    {0,1,2,2,2,1,1}

    Returns: 1

    Without adding new cities the minimum distance is 6. By building a city at (1,1) the minimum distance can be reduced to 4.

  2. 3

    15

    {2,6,10,14}

    {2,6,2,6}

    Returns: 3

  3. 2

    15

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

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

    Returns: 0

    Sometimes no new cities need to be built.

  4. 2

    5

    {0,5}

    {0,5}

    Returns: -1

    The minimum distance between the two cities will always exceed 5.

  5. 5

    1500

    {0,1000}

    {0,1000}

    Returns: 282

  6. 2000

    2000

    {0,2000}

    {2000,0}

    Returns: -1

  7. 1

    2000

    {4,68}

    {0,1999}

    Returns: -1

  8. 1

    29

    {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,0}

    {0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25}

    Returns: 21

  9. 1

    30

    {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,0}

    {0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25}

    Returns: 20

  10. 1

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 1872

  11. 6

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 293

  12. 36

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 33

  13. 216

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 0

  14. 1296

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 0

  15. 1

    2000

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,1999}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    Returns: 1950

  16. 1

    1455

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: 1445

  17. 8

    1453

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: 180

  18. 64

    1453

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: 22

  19. 512

    1453

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: 2

  20. 819

    1453

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: 1

  21. 800

    1452

    {0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3,4,5,6,1027}

    {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,1027}

    Returns: -1

  22. 133

    2000

    {0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200,0,200,400,600,800,1000,1200}

    {0,0,0,0,0,0,0,200,200,200,200,200,200,200,400,400,400,400,400,400,400,600,600,600,600,600,600,600,800,800,800,800,800,800,800,1000,1000,1000,1000,1000,1000,1000,1200,1200,1200,1200,1200,1200,1200}

    Returns: 12

  23. 526

    984

    {2000,1999,1997,1995,1992,1988,1983,1977,1971,1964,1956,1947,1937,1927,1916,1904,1891,1877,1863,1848,1832,1815,1797,1779,1760,1740,1719,1697,1675,1652,1628,1603,1577,1551,1524,1496,1467,1437,1407,1376,1344,1311,1277,1243,1208,1172,1135,1097,1059,1020}

    {2000,940,979,1017,1055,1092,1128,1163,1197,1231,1264,1296,1327,1357,1387,1416,1444,1471,1497,1523,1548,1572,1595,1617,1639,1660,1680,1699,1717,1735,1752,1768,1783,1797,1811,1824,1836,1847,1857,1867,1876,1884,1891,1897,1903,1908,1912,1915,1917,1919}

    Returns: 1

  24. 160

    1329

    {2000,1999,1997,1995,1992,1988,1983,1977,1971,1964,1956,1947,1937,1927,1916,1904,1891,1877,1863,1848,1832,1815,1797,1779,1760,1740,1719,1697,1675,1652,1628,1603,1577,1551,1524,1496,1467,1437,1407,1376,1344,1311,1277,1243,1208,1172,1135,1097,1059,1020}

    {2000,940,979,1017,1055,1092,1128,1163,1197,1231,1264,1296,1327,1357,1387,1416,1444,1471,1497,1523,1548,1572,1595,1617,1639,1660,1680,1699,1717,1735,1752,1768,1783,1797,1811,1824,1836,1847,1857,1867,1876,1884,1891,1897,1903,1908,1912,1915,1917,1919}

    Returns: 2

  25. 60

    984

    {2000,1999,1997,1995,1992,1988,1983,1977,1971,1964,1956,1947,1937,1927,1916,1904,1891,1877,1863,1848,1832,1815,1797,1779,1760,1740,1719,1697,1675,1652,1628,1603,1577,1551,1524,1496,1467,1437,1407,1376,1344,1311,1277,1243,1208,1172,1135,1097,1059,1020}

    {2000,940,979,1017,1055,1092,1128,1163,1197,1231,1264,1296,1327,1357,1387,1416,1444,1471,1497,1523,1548,1572,1595,1617,1639,1660,1680,1699,1717,1735,1752,1768,1783,1797,1811,1824,1836,1847,1857,1867,1876,1884,1891,1897,1903,1908,1912,1915,1917,1919}

    Returns: 15

  26. 1

    988

    {2000,1999,1997,1995,1992,1988,1983,1977,1971,1964,1956,1947,1937,1927,1916,1904,1891,1877,1863,1848,1832,1815,1797,1779,1760,1740,1719,1697,1675,1652,1628,1603,1577,1551,1524,1496,1467,1437,1407,1376,1344,1311,1277,1243,1208,1172,1135,1097,1059,1020}

    {2000,940,979,1017,1055,1092,1128,1163,1197,1231,1264,1296,1327,1357,1387,1416,1444,1471,1497,1523,1548,1572,1595,1617,1639,1660,1680,1699,1717,1735,1752,1768,1783,1797,1811,1824,1836,1847,1857,1867,1876,1884,1891,1897,1903,1908,1912,1915,1917,1919}

    Returns: 983

  27. 2

    982

    {2000,1999,1997,1995,1992,1988,1983,1977,1971,1964,1956,1947,1937,1927,1916,1904,1891,1877,1863,1848,1832,1815,1797,1779,1760,1740,1719,1697,1675,1652,1628,1603,1577,1551,1524,1496,1467,1437,1407,1376,1344,1311,1277,1243,1208,1172,1135,1097,1059,1020}

    {2000,940,979,1017,1055,1092,1128,1163,1197,1231,1264,1296,1327,1357,1387,1416,1444,1471,1497,1523,1548,1572,1595,1617,1639,1660,1680,1699,1717,1735,1752,1768,1783,1797,1811,1824,1836,1847,1857,1867,1876,1884,1891,1897,1903,1908,1912,1915,1917,1919}

    Returns: -1

  28. 541

    1581

    {432,1383}

    {88,1226}

    Returns: 2

  29. 528

    1021

    {938,790,200,476}

    {1110,1982,97,200}

    Returns: 1

  30. 568

    449

    {922,1268,1806,1479,468,1336}

    {1286,16,189,1243,440,1113}

    Returns: 0

  31. 33

    458

    {603,402,1022,486,1379,1716,1400,1050,1474,218,760,431,171}

    {1654,634,1877,395,1803,1681,712,1145,776,1336,231,302,1805}

    Returns: 13

  32. 536

    1243

    {958,354,1342,48,1973,113,606,1664,652,1251,293,1532,1076,1800,369,1547,1495}

    {1569,1216,152,1876,1240,61,1121,113,834,466,449,329,200,712,1279,972,570}

    Returns: 2

  33. 384

    716

    {743,1034,921,1524,1586,1757,1406,1818,270,141,254,1106,788,852,1393,1843,1082,1148,649,1378,1602,978}

    {789,1904,1016,2,654,494,884,419,766,1759,470,1934,634,367,1796,632,527,785,321,532,1663,1465}

    Returns: 1

  34. 3

    894

    {1770,1923,999,1235,902,381,521,1341,834,329,736,380,422,866,1071,1998,885,1829,270,1108,1172,1397,1738,284,271,381,1247,1532,1104}

    {203,502,1002,443,1139,241,1828,1369,1338,1083,1248,904,886,1585,768,1265,278,1456,768,1128,1304,326,28,1005,793,407,925,1603,799}

    Returns: 297

  35. 1260

    408

    {1435,783,220,1313,221,380,230,717,782,447,567,1877,1361,261,1946,1641,1089,1314,219,1244,634,39,1629,619,404,1879,929,1438,1044,453,1293,724,167,923,71,1315,1391,1232,212,1883,917,118,682,823,1989,1447,841,1356,1667,1735}

    {361,716,296,310,1575,1018,1323,534,249,989,1641,968,415,381,1404,953,987,655,1238,1742,1122,194,1922,171,992,553,341,376,359,874,677,668,516,1652,341,1447,287,1349,588,1376,505,1360,1410,1483,1644,484,1022,1101,1935,637}

    Returns: 0

  36. 1

    2000

    {100,1512}

    {100,1512}

    Returns: 1996

  37. 2

    1999

    {359,1233,513,311,452,531,1120,282,202,96,424,626,135,1831,5,49,1244,891,303,273,210,442,341,589,371,844,849,245,8,177,59,879,647,1061,1248,748,108,915,161,407,6,438,756,715,46,379,1117,331,23,209}

    {790,160,109,349,842,95,736,573,81,57,278,434,29,1196,426,1319,255,91,56,169,501,665,524,261,504,1417,13,1639,814,1514,428,94,103,174,1113,756,73,198,129,457,444,1914,396,74,791,124,382,51,155,58}

    Returns: 373

  38. 40

    1599

    {1556,515,586,509,668,697,180,505,1696,1107,1498,1238,1650,1002,312,1167,368,299,557,1706,308,1761,1758,678,642,710,315,1396,194,1855,14,38,324,299,765,255,1958,1316,715,232,83,1298,32,690,585,1814,76,1401,1593,41}

    {1295,1700,1074,521,839,415,744,522,1804,1752,211,578,232,1336,743,1986,1090,548,991,1362,572,79,1092,123,181,520,27,936,1839,1406,877,517,1448,703,1401,1734,48,1776,1050,704,351,421,1924,1419,1459,1983,1135,35,716,1011}

    Returns: 37

  39. 27

    473

    {62,1596,1243,47,768,402,391,646,668,228,541,201,69,972,1654,135,352,358,419,628,734,659,1145,75,407,204,507,1362,352,151,16,82,279,863,161,14,1776,213,141,586,575,455}

    {553,202,4,258,148,3,44,658,455,1128,550,575,285,88,1316,4,289,758,211,264,36,273,169,116,370,204,150,655,249,190,282,1734,161,7,204,45,111,556,417,432,560,815}

    Returns: 17

  40. 2

    1052

    {585,1224,1108,1074,311,118,73,41,1490,1051,330,1597,1082,209,384,652,112,260,812,30,23,208,476,15,192,802,134,844,57,1583,272,214,108,1550,133,907,680,296,229,395,189,643,72,1316}

    {756,319,622,252,944,275,41,741,166,1665,147,123,26,38,192,1187,281,205,1427,285,799,1520,25,1479,405,71,110,25,812,1094,401,683,29,716,1725,223,93,77,330,44,480,1260,1045,200}

    Returns: 459

  41. 829

    919

    {585,1224,1108,1074,311,118,73,41,1490,1051,330,1597,1082,209,384,652,112,260,812,30,23,208,476,15,192,802,134,844,57,1583,272,214,108,1550,133,907,680,296,229,395,189,643,72,1316}

    {756,319,622,252,944,275,41,741,166,1665,147,123,26,38,192,1187,281,205,1427,285,799,1520,25,1479,405,71,110,25,812,1094,401,683,29,716,1725,223,93,77,330,44,480,1260,1045,200}

    Returns: 1

  42. 5

    1031

    {35,292,1565,644,1574,325,387,1041,356,770,1479,456,540,438,547,327,1307,1111,398,35,1141,1392,109,1176,60,882,1328,1971,971,628,292,1522,175,85,535,350,1688,1659,534,8,1862,175,14,563,122,203,986,1622,139,634}

    {766,8,1297,1737,1818,1899,518,1198,1029,1870,1863,1730,1348,409,251,67,1752,238,1521,1053,436,1700,766,755,121,1858,1199,1510,1911,1112,325,1293,1908,1226,248,1562,1835,120,1215,43,1736,1642,798,1165,1120,678,1152,534,1285,1605}

    Returns: 206

  43. 1

    1281

    {10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804}

    {200,200,200,200,200,201,201,201,201,201,202,202,202,202,202,203,203,203,203,203,204,204,204,204,204,1200,1200,1200,1200,1200,1201,1201,1201,1201,1201,1202,1202,1202,1202,1202,1203,1203,1203,1203,1203,1204,1204,1204,1204,1204}

    Returns: 1275

  44. 1

    1280

    {10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,10,11,12,13,14,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804,800,801,802,803,804}

    {200,200,200,200,200,201,201,201,201,201,202,202,202,202,202,203,203,203,203,203,204,204,204,204,204,1200,1200,1200,1200,1200,1201,1201,1201,1201,1201,1202,1202,1202,1202,1202,1203,1203,1203,1203,1203,1204,1204,1204,1204,1204}

    Returns: -1

  45. 1

    2000

    {400,1600}

    {1900,200}

    Returns: -1

  46. 1

    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,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {0,1,2,3,4,5,6,7,8,9,10,11,1000,2000,1999,1998,1997,1996,1995,1994,1993,1992,1991,1990,1989,0,1,2,3,4,5,6,7,8,9,10,11,12,2000,1999,1998,1997,1996,1995,1994,1993,1992,1991,1990,1989}

    Returns: -1

  47. 1

    2000

    {1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,1400,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    {0,1,2,3,4,5,6,7,8,9,10,11,700,1389,1390,1391,1392,1393,1394,1395,1396,1397,1398,1399,1400,0,1,2,3,4,5,6,7,8,9,10,11,700,1389,1390,1391,1392,1393,1394,1395,1396,1397,1398,1399,1400}

    Returns: 1964

  48. 1

    2000

    {2000,0}

    {2000,0}

    Returns: -1

  49. 1

    7

    {0,0,0,1,2,2,3}

    {0,1,2,2,2,1,1}

    Returns: 0

  50. 1

    50

    {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24}

    {0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25}

    Returns: 0

  51. 1

    48

    {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24}

    {0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25}

    Returns: 2

  52. 1

    35

    {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24}

    {0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25}

    Returns: 24

  53. 180

    565

    {1,240,400}

    {1,160,400}

    Returns: 3

  54. 180

    577

    {1,240,400}

    {1,160,400}

    Returns: 2

  55. 1

    1901

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

    {0,320,1450,1090,813,394,69,988,1085,1140,404,444,640,1653,660,668,1997,1908,1845,446,499,1695,17,1571,1471,252,1037,459,1565,1390,1346,1005,1212,219,704,950,1819,460,1703,155,329,1485,1256,269,141,1149,1535,304,1434,1900}

    Returns: 1872

  56. 5

    246

    {1,4,8,11,15,18,22,25,29,32, 36,39,43,46,50,53,57,60,64,67, 71,74,78,81,85,88,92,95,99,102, 106,109,113,116,120,123,127,130,134,137, 141,144,148,151,155,158,162,165,169,172}

    {1,5,8,12,15,19,22,26,29,33, 36,40,43,47,50,54,57,61,64,68, 71,75,78,82,85,89,92,96,99,103, 106,110,113,117,120,124,127,131,134,138, 141,145,148,152,155,159,162,166,169,173}

    Returns: 0

  57. 1

    491

    {2,8,16,22,30,36,44,50,58,64, 72,78,86,92,100,106,114,120,128,134, 142,148,156,162,170,176,184,190,198,204, 212,218,226,232,240,246,254,260,268,274, 282,288,296,302,310,316,324,330,338,344}

    {2,10,16,24,30,38,44,52,58,66, 72,80,86,94,100,108,114,122,128,136, 142,150,156,164,170,178,184,192,198,206, 212,220,226,234,240,248,254,262,268,276, 282,290,296,304,310,318,324,332,338,346}

    Returns: 441

  58. 30

    129

    {95,87,37,75,7,56,7,7,74,54}

    {91,77,58,68,14,65,72,27,68,3}

    Returns: 1

  59. 540

    1240

    {631,929,703,1945,810,223,1452,925,124,1130,1287,1179,124,1537,687,1160,1416,47,831,350,1041,251,611,448,784,12,491,122,1554,634,295,1955,1420,1722,1404,1936,1343,803,1146,1601,1699,252,1997,1861,251,1948,608,157,699,1807}

    {1207,633,1896,825,380,1662,574,472,739,1591,799,1165,533,1448,316,1543,950,553,471,522,1702,713,1114,1605,1567,1724,1711,1641,163,284,1517,726,1750,86,434,1173,940,1486,121,846,1396,1455,1141,712,1686,888,536,1931,154,817}

    Returns: 1

  60. 62

    1241

    {631,929,250,1945,346,223,1452,925,124,1130,1287,1674,124,1537,687,1160,1416,47,831,350,1041,251,1248,448,784,12,491,122,258,634,295,1955,1420,1722,1404,1936,1343,803,1146,1601,1699,252,1997,1861,251,1948,608,157,699,1807}

    {1207,633,1458,825,1491,1662,574,472,739,1591,799,42,533,1448,316,1543,950,553,471,522,1702,713,1005,1605,1567,1724,1711,1641,1410,284,1517,726,1750,86,434,1173,940,1486,121,846,1396,1455,1141,712,1686,888,536,1931,154,817}

    Returns: 18

  61. 1

    2000

    {0,1999}

    {0,1}

    Returns: 1999

  62. 1

    5

    {0, 0, 0, 1, 2, 2, 3 }

    {0, 1, 2, 2, 2, 1, 1 }

    Returns: 1

  63. 10

    691

    {1, 6, 16, 29, 38, 45, 56, 66, 80, 89, 104, 109, 115, 126, 135, 149, 159, 168, 175, 187, 200, 210, 221, 226, 236, 251, 264, 265, 278, 286, 299, 314, 319, 330, 341, 354, 362, 372, 376, 389, 399, 407, 423, 429, 438, 453, 455, 472, 479, 488 }

    {4, 9, 18, 29, 39, 54, 59, 68, 78, 89, 98, 112, 117, 129, 137, 148, 164, 170, 176, 188, 195, 207, 215, 230, 236, 247, 259, 274, 281, 288, 303, 312, 323, 328, 338, 349, 359, 374, 384, 392, 398, 409, 422, 431, 443, 446, 456, 465, 481, 488 }

    Returns: 48

  64. 2000

    70

    {500, 10, 30, 40, 0, 80, 120, 180, 200, 220, 240, 260, 295, 299, 300, 320, 400, 550, 590, 620, 660, 680, 700, 740, 780, 820, 840, 880, 890, 920, 940, 960, 1000, 1100, 1150, 1200, 1400, 1500, 1600, 1690, 1730, 1780, 1820, 1840, 1890, 2000 }

    {500, 10, 30, 80, 200, 100, 600, 300, 800, 400, 900, 500, 1000, 600, 1900, 700, 1800, 800, 1700, 900, 1600, 1000, 1500, 1100, 1400, 1300, 1200, 1250, 840, 240, 260, 1850, 1740, 1790, 1840, 1900, 1400, 1200, 1250, 10, 1400, 1500, 1780, 1800, 1600, 2000 }

    Returns: -1

  65. 1

    6

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

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

    Returns: 4

  66. 3

    1600

    {0, 467, 334, 500, 1169, 1724, 1478, 1358, 962, 464, 1705, 145, 1281, 827, 1961, 491, 995, 1942, 827, 1436, 391, 604, 1902, 153, 292, 382, 1421, 716, 1718, 1895, 1447, 1726, 771, 1538, 1869, 1912, 1667, 299, 1035, 1894, 703, 1811, 1322, 333, 1673, 664, 1141, 1711, 253, 868 }

    {0, 1644, 662, 757, 37, 859, 723, 1741, 1529, 778, 316, 1035, 190, 1842, 288, 106, 1040, 942, 1264, 648, 1446, 1805, 1890, 729, 370, 1350, 1006, 1101, 393, 1548, 1629, 623, 84, 1954, 756, 1840, 966, 1376, 1931, 308, 944, 439, 626, 1323, 1537, 1538, 118, 82, 929, 967 }

    Returns: 433

  67. 1

    2000

    {0, 41, 82, 123, 164, 205, 246, 287, 328, 369, 410, 451, 492, 533, 574, 615, 656, 697, 738, 779, 820, 861, 902, 943, 984, 1025, 1066, 1107, 1148, 1189, 1230, 1271, 1312, 1353, 1394, 1435, 1476, 1517, 1558, 1599, 1640, 1681, 1722, 1763, 1804, 1845, 1886, 1927, 1968 }

    {0, 41, 82, 123, 164, 205, 246, 287, 328, 369, 410, 451, 492, 533, 574, 615, 656, 697, 738, 779, 820, 861, 902, 943, 984, 1025, 1066, 1107, 1148, 1189, 1230, 1271, 1312, 1353, 1394, 1435, 1476, 1517, 1558, 1599, 1640, 1681, 1722, 1763, 1804, 1845, 1886, 1927, 1968 }

    Returns: -1

  68. 1

    2000

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 1400 }

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 1400 }

    Returns: 1960

  69. 5

    1500

    {0, 1000 }

    {0, 1000 }

    Returns: 282

  70. 1

    16

    {2, 0, 0, 0, 2, 4, 4, 4, 2 }

    {0, 0, 2, 4, 4, 4, 6, 8, 8 }

    Returns: 6

  71. 1

    2000

    {0, 1421, 1326, 1472, 131, 1569, 909, 1189, 1149, 230, 493, 1899, 437, 429, 1838, 1758, 1166, 258, 1353, 698, 1226, 772, 191, 875, 1151, 571, 1888, 1191, 1362, 891, 22, 720, 1778, 430, 1710, 327, 353, 80, 449, 1237, 650, 1215, 900, 1935, 1035, 706, 1092, 99, 1642, 1903 }

    {1299, 542, 60, 1335, 760, 1650, 708, 147, 254, 798, 739, 141, 1264, 1661, 149, 754, 1118, 1195, 1808, 601, 1412, 209, 1908, 603, 683, 471, 1129, 1511, 458, 369, 1095, 1874, 1868, 639, 1143, 1189, 1133, 998, 362, 25, 1526, 911, 66, 316, 472, 1056, 1255, 916, 871, 1211 }

    Returns: 1904

  72. 2000

    2000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 0

  73. 1

    2000

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    Returns: 49

  74. 1

    2000

    {0, 1000 }

    {0, 0 }

    Returns: 999

  75. 1

    1400

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 1000 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 1000 }

    Returns: -1

  76. 1

    2000

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 1000 }

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 1000 }

    Returns: 1394

  77. 1

    2000

    {1967, 1986, 1938, 1976, 1992, 1961, 1923, 1914, 1936, 1994, 1953, 1960, 1974, 1906, 1915, 1901, 1947, 1984, 1988, 1907, 1993, 1939, 1997, 1931, 1919, 1992, 1968, 1957, 1965, 1968, 1986, 1973, 1939, 1944, 1911, 1919, 1948, 1946, 1973, 1917, 1949, 1926, 1990, 1915, 1969, 1954, 1998, 1948, 1940, 1914 }

    {1908, 1966, 1943, 1972, 1939, 1950, 1926, 1999, 1909, 1929, 1920, 1977, 1915, 1942, 1966, 1979, 1923, 1973, 1990, 1936, 1990, 1927, 1930, 1972, 1964, 1975, 1902, 1970, 1946, 1969, 1906, 1976, 1995, 1993, 1944, 1902, 1938, 1989, 1900, 1998, 1990, 1910, 1997, 1946, 1993, 1905, 1963, 1970, 1927, 1974 }

    Returns: 84

  78. 100

    2000

    {37, 282, 307, 734, 273, 1004, 881, 1640, 573, 1605, 938, 102, 331, 1913, 120, 616, 715, 1170, 886, 559, 1818, 605, 1676, 783, 279, 1169, 325, 483, 1123, 1424, 1182, 378, 1013, 853, 1134, 1519, 1783, 845, 1996, 86, 1920, 355, 530, 1634, 1886, 1124, 1788, 1556, 464, 1905 }

    {1677, 830, 1294, 1458, 1854, 326, 1126, 1415, 1907, 310, 404, 90, 1709, 1744, 1245, 560, 661, 782, 136, 271, 1803, 1719, 904, 1033, 1452, 462, 394, 599, 1017, 437, 168, 401, 1930, 1183, 1896, 1529, 510, 1746, 1701, 1031, 749, 1003, 1848, 271, 1709, 636, 290, 1215, 637, 1472 }

    Returns: 16

  79. 1

    2000

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

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 2000 }

    Returns: -1

  80. 1

    2000

    {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 1999 }

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

    Returns: 1951

  81. 1

    2000

    {1720, 640, 1459, 842, 881, 1825, 1864, 483, 67, 580, 1888, 108, 1261, 850, 1260, 557, 656, 1962, 895, 154, 1457, 1118, 1963, 1721, 1449, 140, 1282, 333, 44, 1675, 750, 606, 563, 1981, 1633, 1060, 1807, 1450, 417, 1216, 381, 592, 501, 483, 451, 1026, 380, 1573, 1872, 1709 }

    {1222, 1165, 114, 541, 1805, 773, 1758, 504, 1180, 611, 1286, 365, 851, 1642, 488, 292, 115, 727, 1345, 360, 782, 544, 923, 716, 384, 299, 840, 149, 1433, 866, 1270, 437, 547, 1625, 246, 1942, 819, 902, 1202, 625, 387, 439, 774, 1365, 1434, 1472, 1640, 142, 952, 1785 }

    Returns: 563

  82. 3

    5

    {0, 2, 0, 0 }

    {0, 2, 2, 4 }

    Returns: 0

  83. 2

    5

    {0, 5 }

    {0, 5 }

    Returns: -1

  84. 2

    12

    {0, 0, 4, 4, 4, 0, 0, 2 }

    {0, 4, 4, 6, 8, 6, 8, 8 }

    Returns: 1

  85. 29

    1400

    {0, 324, 342, 8, 38, 85, 348, 2, 43, 33, 22, 11, 244, 333, 23, 9, 33, 34, 63, 90, 500 }

    {0, 84, 823, 88, 90, 111, 2, 44, 39, 122, 53, 95, 44, 344, 93, 22, 2, 34, 23, 111, 256 }

    Returns: 16

  86. 1

    1899

    {0, 40, 80, 120, 160, 200, 240, 280, 320, 360, 400, 440, 480, 520, 560, 600, 640, 680, 720, 760, 800, 840, 880, 920, 960, 1000, 1040, 1080, 1120, 1160, 1200, 1240, 1280, 1320, 1360, 1400, 1440, 1480, 1520, 1560, 1600, 1640, 1680, 1720, 1760, 1800, 1840, 1880, 1920, 1133 }

    {0, 40, 80, 120, 160, 200, 240, 280, 320, 360, 400, 440, 480, 520, 560, 600, 640, 680, 720, 760, 800, 840, 880, 920, 960, 1000, 1040, 1080, 1120, 1160, 1200, 1240, 1280, 1320, 1360, 1400, 1440, 1480, 1520, 1560, 1600, 1640, 1680, 1720, 1760, 1800, 1840, 1880, 1920, 33 }

    Returns: 1133

  87. 1

    1999

    {1132, 1610, 704, 150, 44, 1845, 1324, 59, 785, 478, 1717, 333, 1844, 1106, 1482, 1212, 1625, 795, 1231, 482, 528, 1178, 182, 1244, 1091, 394, 1254, 1761, 1076, 794, 194, 710, 734, 375, 1064, 1756, 1380, 1773, 676, 1496, 276, 144, 1622, 1449, 732, 951, 1107, 1819, 1271, 390 }

    {503, 1691, 1957, 833, 1140, 904, 1682, 556, 812, 200, 1469, 1791, 411, 723, 1998, 1488, 352, 401, 456, 13, 1227, 721, 1772, 1189, 336, 49, 1594, 1452, 366, 1822, 1867, 493, 98, 1930, 1717, 1897, 1755, 779, 1909, 1249, 1702, 1120, 1486, 1914, 1127, 1505, 1049, 300, 1656, 472 }

    Returns: 742

  88. 3

    1000

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 100 }

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 100 }

    Returns: 24

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: