Statistics

Problem Statement for "RangeGame"

Problem Statement

Imagine a game consisting of two billion doors (numbered starting at 1), behind some of which lie fabulous cash prizes. There are a limited number of patterns to the placement of the prizes, which the contestant knows in advance. All doors initially begin closed. Before the game begins, the host secretly selects one of the patterns from the list at random (all with equal probability), and puts prizes behind the doors specified by the pattern. For example, if the host chose the pattern "3-4 9 12-15", he would put prizes behind doors 3, 4, 9, 12, 13, 14, and 15 (and nowhere else).

Two things happen every turn. First, the contestant decides which door is currently most likely to contain a prize, and secretly records this choice. (If two or more doors both have the greatest likelihood of containing a prize, he chooses the door with the lowest number.) The second part of a turn consists of the host opening one or more doors, all of which are revealed to be empty. For example, if the host gave the hint "2 7-10", this would indicate that he opened doors 2, 7, 8, 9, and 10 and there were no prizes behind any of them.

In specific, the following grammar is used for this problem:

<doors> ::= <range> | <range><sp><doors>
<range> ::= <num> | <num><to><num> (the first num must be strictly less than the second num)
<num> ::= integer between 1 and 2000000000, inclusive, with no leading zeroes
<sp> ::= ' '
<to> ::= '-'

Given a String[] possible, containing the possible placements of prizes, and a String[] hints, the N hints given during the course of the game, your method should return a int[] containing N+1 elements. Each element should describe the most likely position of a prize at that point in the game. The first element represents your guess before any hints are given; the last element represents your guess taking every hint into account. Remember to break ties by choosing the lowest numbered door, if multiple doors are all the most likely.

Definition

Class:
RangeGame
Method:
bestDoors
Parameters:
String[], String[]
Returns:
int[]
Method signature:
int[] bestDoors(String[] possible, String[] hints)
(be sure your method is public)

Notes

  • Each element of possible has an equal chance of being the pattern that is chosen by the host. This means that if one pattern appears on the list twice, it is twice as likely of being chosen as a pattern which appears on the same list only once.

Constraints

  • possible will contain between 2 and 50 elements, inclusive.
  • Each element of possible will contain between 1 and 50 characters, inclusive.
  • Each element of possible will conform to the rules of , as specified in the grammar above.
  • For each element of possible, the ranges contained therein will be non-overlapping and in ascending order.
  • hints will contain between 0 and 50 elements, inclusive.
  • Each element of hints will contain between 2 and 50 characters, inclusive.
  • Each element of hints will conform to the rules of , as specified in the grammar above.
  • For each element of hints, the ranges contained therein will be non-overlapping and in ascending order.
  • The information given in hints will always be consistent with at least one pattern in possible.

Examples

  1. {"1-100","100-200","200-300"}

    {"50-75","250-1000"}

    Returns: { 100, 200, 100 }

    There are three possible patterns of prizes: doors 1-100, doors 100-200, or doors 200-300. Before any hints are given, you know that doors 100 and 200 are more likely than the rest; the odds of a prize being in either of them are 2/3, whereas the odds of a prize being in any other door 1-300 is only 1/3. Doors 100 and 200 are the most likely, so your first guess should be 100 (since it is smaller). Then the host reveals that there are no prizes behind doors 50-75. Pattern "1-100" is now no longer an option. You now know for sure that there is a prize in door 200, whereas the odds for any other door 100-300 is only 1/2. Therefore, 200 is the second element of the return list. Finally, the host opens doors 250-1000 and shows them all to be empty. You now know the pattern must be "100-200", so you choose the smallest door of this group, 100, to be your final answer.

  2. {"100-900 1111","200-800 2222","300-700 3333","4444"}

    {"2000-4000","500"}

    Returns: { 300, 100, 4444 }

    Before any hints are given, doors 300-700 are the most likely to contain prizes. The first hint tells you that doors 2222 and 3333 are empty, leaving only the first and last patterns as options. The second hint eliminates the first pattern, so the only prize must be in room 4444.

  3. {"346591240","858005279","1321831520","1453846384","1972718383","530431653-1848872872"}

    {"1400000000-2000000000","400000000-600000000"}

    Returns: { 858005279, 346591240, 346591240 }

    Beware of large numbers and ranges!

  4. {"132447405 503544040-715973485 870200752-956544119", "440049267 841256627 1241586057", "143874572-187537992", "932502012-1085870188", "1708889038-1991574143", "911181254", "548114547 866929779 1668234563-1978195718", "467794707", "551581396 1148184404", "237081393-380066752 830822133-1024839262", "77696488-217679535 1278558658 1776485780", "597956231-779614167", "80727418-172687869 500179896 1521697244 1895196968", "229976197-344997820", "1087891781 1288379708-1334482037 1965935685", "300141226-382907261 1218123340 1931738268", "520690996 1696041786", "534278455-556098837 1545131273 1721738340", "229536304 643356527 822238152-901711165 1239153872", "411794115-565530322 1736054227-1780499136", "1249293313-1425652429 1612552532", "458805831-524707218 1214632828-1421293305", "297795447-314646881 445588509-595896973 1720780033", "201826750-316108869 450664772 1528814748", "19567648-33895381 578571750-767131664 1006672000", "25972710 1071542579 1538710581 1787738190", "156037887-277290566 1804132015", "660515267 1493049654", "371295219 1465967224 1618792601-1749577437", "566394086 1041682040-1177307168"}

    {"263517117 539336844-549676969 851117406 1498595346", "15272923-170480950 635191484-799829499", "1128715543", "531444683-667303543 1858056624-1978483140", "71123728-159755693 575537168 1549705716 1986536228", "1521265477-1570928024 1810696046", "484383335-734836289 910114111-976923180 1933996364", "6466685 706868993 1510388152-1555366471 1915824408", "180650469 510149509 1554480570-1562156387", "37278659", "1540197963 1985794262"}

    Returns: { 300141226, 143874572, 1288379708, 1288379708, 467794707, 467794707, 467794707, 371295219, 371295219, 371295219, 371295219, 371295219 }

  5. {"107034898", "1435222368", "1610706092-1697663808 1871122314 1976839809", "1226794060 1927190387-1964483670 1987884603", "861922579-1336337207", "142748363", "1546075400-1748036115 1955500686-1974232656", "1736945528 1743643105-1864443183", "406917722 1469388991 1674485521-1699512544", "1345731396", "411781688-1308033034", "306942452", "284066323 330387048-903698718", "1238389562 1588857617 1598204195-1730338367", "1222145365 1251330405 1737637452 1932383881", "1182878989 1991733477", "1379845270", "97462325-1869043704", "122785453-470030750 1388087012-1472126209", "567959290-1062178801 1313923490", "1604936321 1910270373", "284954044", "490398145 697778577-1390967710", "762724135-1857573006", "1355396212", "158447965", "57540788 579470392", "1451893787 1887627601", "148093489 338484798 1916176499", "1931587615 1975565077", "1047868305-1457264130 1678787372-1691714456", "1431865467 1494054738 1957664580 1996432579", "1160697241 1298672632 1515023722-1863250323", "252737264 443527480-897862342", "291338892", "218849644-948481786 1299116802 1852333175", "375015845 1183622525 1470627680-1609496410", "1346409743 1810586929 1878299307-1995444290", "1124773126-1783012154 1910459538-1953802626", "1040343157-1274638734 1525460811 1580706663", "45922830-114162556 178888101-522462530", "1085305598-1314003765", "1641550247", "1182877954", "1924495436 1928524460-1963872423 1996026506", "87785117", "1443095146", "367156410-961032268"}

    {"213048876 346861597-1265215573", "1095111572", "95233077", "550268949 1044392523", "450959885-1678393446 1772844450-1889281952", "1420165907 1514317577-1938341283 1993341096", "877538323 1167682166", "943532736-1001933205 1471248256-1918251137", "1372800765 1603057441-1842145371", "1132314788 1929779652", "702294813-1451506939", "1556428629 1812896460-1935221730 1964342541", "1281427157-1735021131", "1359184198-1669113915", "846474777 1029907910", "1853256721", "740095137-766015924 1244079649-1763094483", "133352737-426664696 1514211039", "1206931840", "654398657 1517923766", "347012854", "1336563216-1643536101", "570686880-1233701422", "821154312-1668460811", "407500886 993868475-1806116539"}

    Returns: { 861922579, 1957664580, 1957664580, 1957664580, 1957664580, 1931587615, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117 }

  6. {"388864994-1508204788 1835663951 1988988647", "1431010301-1745175407 1894031927", "1972990680-1990063234 1991855764", "763986626 1647426014 1732817206-1780477657", "57151958 720866691", "1205773909-1723903249", "46940922-1012042677 1609424663 1707453706", "16528565-1369260656", "589504053 778054929 1127568382-1226559383", "128031000-219499649 1759913303", "969704444 1956920351 1966351255-1976529219", "473338415", "1324638818-1443392315 1566398341 1972251204", "568494855-1186667023 1692494025 1818504620", "614360668 1598042111", "620310691 762579014-1134009649", "653346094 1066137647-1415204247", "321602799", "1111992269-1874165245", "1828816854 1886631121 1920635132-1961315073", "663850445", "1373251866 1926148369", "1952585724 1983618251 1989764328-1992504616", "1855921174 1887118831", "898245882 1891932757", "1079953638-1917478265 1988010487", "1157602953", "411537206 715475272", "92979876-112118485 355161898-1577054531 1820736548", "1529301174", "1349213786", "217303803-725933959 1716858456", "300214880-719084147 1085058091-1154193383", "400475675 1488170472 1631978192-1636626495", "270634502-487028002 936347440", "1544559153 1969193962 1996208370 1999255228", "1359825509-1565196781 1727887610-1970890163", "665564647", "1326001963 1611566516", "1924331376 1974413424-1993197160 1996250524", "1111411368-1466669302 1732139127 1940359490", "1376908359-1618629061", "1552679543 1895216458", "1300817137 1356750855-1941960083 1962662595", "1657773364 1728629907 1901226306-1977841987"}

    {"1325696840-1465585919 1946611542-1969755306", "139350349", "890880618", "454014064-1705584036 1940678557 1982899394", "212502750-1387982526", "123811991", "1537046046 1869149678"}

    Returns: { 1127568382, 321602799, 321602799, 321602799, 321602799, 1855921174, 1855921174, 1855921174 }

  7. {"1301664474 1614714476 1723797059", "1003043993 1091435459 1436162531", "34626790 1036119202", "743575176", "1228395360 1852034662 1943689312", "364520942", "1266585117", "459272532", "1274059274 1644091001 1778850548-1975012771", "701495047-1056547294 1325493899 1502721062", "566373265-1584352469", "399406180 1422335072 1450906961-1868563126", "1698797262", "179906057-439187177 607083832-1089686350", "1713139113 1886289129-1998795355", "1367924494 1511380786 1536621802", "142123336-725128218", "19815250 1287237613 1499218066-1552181054", "217845728", "1008774737-1969377682 1998115038 1999113083", "709090988 1546202761-1775206338", "1237611716 1793190079-1800645488 1946181340", "1880806354", "116186511 528732695 704990655-1394935192", "1953444421 1998353016-1999412129 1999804452", "390798639-1825118413 1832878244", "244114124 1394023132-1495577483 1689952604", "890049721-1514112623 1745310564 1976045210", "1555834629", "1114638327", "1181101307 1335160238-1371534774 1793166203", "570338450", "224843158", "1231864813", "923729359-1172229245", "688429504 1835475002", "1996448055", "632954658 1973413566", "43888822-1930296477", "1936485724", "239016307 577976495", "1111456564-1803515158", "1099920288 1636167252-1681381203", "80907880", "1538229146"}

    {"63210093-84309673", "1819396426 1921579740-1976503624 1992789736", "1384061474", "1210546252 1416405412-1935076360 1937711105", "734544867 1315998838 1549173707 1727038303", "1415116391-1419412014", "1346882009 1445844942 1770879469 1948887293", "1919317158 1927236854", "1185922405", "1896692654", "733621177 1947968109 1971898845 1997013167", "369222621-1152432329", "327858435-412682723", "519328523 611019647-1697400586 1743902419", "1064774873", "536300748-896646592", "1193642804 1416782646"}

    Returns: { 1036119202, 1036119202, 709090988, 709090988, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728, 217845728 }

  8. {"1862416943", "1346661676 1969046527", "1247078589-1258447518 1774951517 1877641941", "149046958 1934956216 1941754715-1967629401", "1065397040 1292898778", "850939512 1825933663 1918481230", "880937019", "1691832056-1922430834", "558311587-1693558258 1952817074 1963310598", "552714181 1829718687 1985688617", "350944307-612103621 1673488705 1991421358", "902422712-1572385401", "1521145306 1818437536 1899449308-1959060531", "744978194 1547096886", "683949478 1371449349 1554399381 1842405487", "391096940-904100672", "121414851-820311314", "1037438763", "409289352-1378321932", "169990448-1747335313 1751652893-1893809201", "1932028218", "1649016845", "724446432-1190866485", "676899371 762407380-1185404008 1228576327", "396208480 794382745-1623590398", "579266259-1714032325 1732578584", "1629865025 1887183338-1936430009 1960843985", "1280381054-1310751682 1633872069", "520239481-1613933195 1626295701-1691370343", "919261395", "1789892426 1922365687", "1196814958-1249565664", "1486538297 1586471752 1952313162", "603877559-654510669", "1789378410 1957232174", "63767579 1376710819 1698007252-1979210175", "1037849118", "900492070-1400789412 1663827161", "1592322323 1839597154-1847131804 1864177590", "1070642746", "66830841-785587789", "795911130 1349780789-1821619134 1874982995", "1270883220", "1246291939 1589171864", "314218211-1509365864", "264214235 986106043-1193621323", "1542400453 1620519789-1918875330"}

    {"990007835", "68819827-883235162 1716367666-1983853550", "380632656 1318861366-1693521237 1859087702", "725635773", "1467239170", "1893172663 1927298873 1929998768", "1556220750-1973801947 1994284662 1995695875", "411203791"}

    Returns: { 1037438763, 1918481230, 1246291939, 919261395, 919261395, 919261395, 919261395, 919261395, 919261395 }

  9. {"525083845-1722183494 1954480741 1977430776", "663021243", "1362510562 1870336511", "806766300-1058753297 1081990426-1942940033", "1425140080 1801179283-1826445127 1894514403", "710250750-966196861 1200004564 1355795460", "140043669-282224801 909585870 1326078846", "719017790-1107976572 1889250296-1932653247", "549187277-1025992524 1500138177 1748552538", "1491354023-1685312143", "886999233 1276271672 1488256632 1721776104", "17520261-565131627 889546049", "1609302235", "1903325098 1971534295-1983390798 1995955207", "435640323 1506779942", "1747794419 1983274011 1988602638 1995194674", "409371728-500751874 1877258347", "355722526-536214103 1141895899-1384110688", "800763959-984259001", "213595622-671066526", "1482619501-1736457142 1880223515", "1137886134 1252341271-1582682047", "1317604991 1735006911 1778859839 1845809060", "181369410 854088734 1867700400-1952658340", "647388479 1057817576-1573693532 1915105062", "1035125387", "1533348103 1956529935-1963793668 1998281811", "12725744 1697858066", "1293467011", "1518106083 1843843375 1846036183", "132414638-1956678891 1961998803-1989317919", "283829207", "682786775 1347901993-1467816956 1470888784", "1321007861 1842238617 1863938556", "775081525 1373670989 1438037273", "52267497 1636316708 1697947371 1933416160", "1057004938 1058084524 1200351252 1319872235", "509399906 1049949580 1501209539-1888407210", "701389062 1148772677", "218584372 1788365162 1956731033 1981947052", "1042465326-1763545687", "41293305-1320764384 1557566600-1681911333", "490499853", "652857529 728442074-755404491", "451013849 1999376175 1999637189", "345492639"}

    {"689340044 1717793255-1889555313", "1299473344 1538485154-1801722983", "1356493760 1423321735 1883262156 1913030334", "566227460-1999947591 1999969708-1999981235", "653232386 1658096167-1886376502 1961353908", "249762536", "1169950031 1389924727 1443428703-1997260529", "592051741-1439893940 1578367608-1804292812", "1837602244", "1071507286 1157918572-1996527570 1999618586", "1425031968 1565913501 1951210804 1974327895", "296637666 1439071972 1785269614-1787516192", "405968699-1104029696"}

    Returns: { 1506779942, 1355795460, 213595622, 213595622, 283829207, 283829207, 283829207, 283829207, 283829207, 283829207, 283829207, 283829207, 283829207, 283829207 }

  10. {"937221226", "1533177053 1678355223-1789977157 1803131841", "1582791610 1992597599", "824626777-1006109202 1099182586-1826575614", "525903493-1867016974", "983224814 1981020597 1984358761 1987655625", "756676176", "785013560", "1114075446", "1428641470 1513002179 1519962831", "1428554514", "1183063215-1511408294", "899606238 1614466196-1775700989", "1875724899 1924277165 1953925875-1985171588", "119829621-1578873239 1708073252-1941727212", "1606375844 1687826381-1756498011 1770177958", "191094162-1666963404 1691576911 1926137206", "1981912955", "1568818872 1729229044", "332825563 996757642", "1167707616", "758499358-1194608038 1341446446", "507495988 1363632357-1573508785", "936290233 1766207021-1887268468", "995170327-1321266126", "1565054130 1943732174 1998747968", "291197410 1304807676 1872540280 1918327919", "1966171441 1967726382-1989888414 1990271833", "579566183-1113828654 1195719261-1476770074", "1074258375", "1330404647-1699588910 1835180898 1973008559", "221188457-1860936933", "349233731 405480136 1283203498", "1833999543 1946558526", "799484784", "925201645-1206760422", "313666967 1576892381 1595131903 1908144512", "878609943-1397153523 1723454219 1892979813", "401701661 454729884", "291968448 572182825 1264455630 1568706134", "69120510 726865951 889396516 1080989822-1950343008", "90053754-479635065 670873416", "1517248164-1626988396 1753819315-1765502315", "1687714360", "873893388 1815289899 1893569746 1995334359", "865311165 1909380257 1964339543 1994590675", "1431412393-1464856379 1671702288-1722900033", "1738354550 1976249520"}

    {"1597184912 1891756780 1911796898-1962998683", "1057860385", "395593000-1961150869", "326689864", "842835276", "663445889", "1628060311 1965701689", "1270853403 1967631768 1981968779-1987105076", "437147425-751761711", "1384136114 1683183233 1781922676", "1108631359-1580505945 1641962292 1906035736", "23000359-1769133350"}

    Returns: { 996757642, 996757642, 1687714360, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955, 1981912955 }

  11. {"333725790-1703628731 1905741402 1945199648", "715366115", "666362384 1359070882 1881335655-1998024202", "527894387", "1368603202 1643880115", "643559490 939850372-1828387246 1829135533", "1228732524 1767375100 1872131265-1969489320", "165358200", "1293635753", "1937650497 1941600185", "768995730-1568814587", "114667274-609777311 1470921784", "779267373 1991751671 1993200844-1996353959", "1376859367-1553297942", "1301747926-1459213360", "1720470803 1894196548 1997245471 1999978595", "851866798 1643350213-1773877234 1866604910", "497760683-1513449975", "889894050 1473182270", "819015783-929108166", "76203880-91905278 248757512 1752740094", "86309515 1801515608 1967232065", "1320649223-1783447730 1953326765 1981686370", "363839657-1553867183", "448039716", "1059069291-1287702039", "1342105754-1859652341", "793039271-1773238027 1852370033 1993167334", "298944738-1938487955", "173110368 1153052256-1915951846", "1309460181", "700356762-1111454346 1193333783-1876357122", "1350561260 1711854499-1896622392 1988995241", "314827867 593221469", "1539118747", "1895543178-1922559838 1927488012 1929611152", "1640511206 1828937994", "1377650576-1785872145", "355869042", "152673936-1988366998", "1386831209 1429877592-1437035848", "1195583330 1302733334-1842940308 1998027142", "79049882-392539087 426301732-1131616665 1868506732", "166073757-462842990", "698070215 1085991235-1274022985", "647271643-1344355342 1453288040-1613493164", "1278328786 1901593096 1977591159", "1365999084 1394029834 1914285376 1963670973", "298530342 734030205 928459328", "1583378477 1982359745 1989984880"}

    {"528615424 1059200575-1625129106 1763654121", "1195055843 1337929601-1942601393", "338428299 414164245 913638120-1325258066", "68585754 1428351258 1899355818 1920613563", "1708108857 1828274371 1858353516-1876394560", "785828082-1776762309", "704745491-1635293890 1936930213", "489931729-936733951", "1906523165 1923750138", "1733930282", "305768419 722104634", "696245509", "166411356-1508832532", "236884913-1009669298 1644822673-1688389518", "340361718-1555934759 1939728607", "952354951", "706413028 892771909 1340395581", "996940879 1174323466-1304741248 1620025776", "317525956 1400776769-1844900239"}

    Returns: { 1386831209, 86309515, 298530342, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200, 165358200 }

  12. {"843831843 1056638543", "759262523 1870454836 1911879877-1977907125", "179120656 725602877-997821160 1857064106", "3388320 632517477", "1093494210 1732108146", "187739884-734674775", "234956246-1549525598 1741901437", "836011060", "212680851 424265533", "390407440-687002806 855660287 974465739 1236954164", "757627026", "1096763685 1559317831 1754158997", "464134166 1552726091 1982237450 1998441792", "89489326-581160065 1020405659", "1066602266 1391475478-1765576607 1933929458", "335038846-1730522553", "1307456704", "365122160 612027216-615298010", "1300890230 1339767001-1968933189 1984670661", "916419204 1152093334-1939413323 1955624482", "367158120-1018960603 1164426547-1793672073", "227217877", "9000388 1181263896", "1187583642 1356417773 1407950246", "1758539389", "95448493-166890910 233724207-1783391618", "555455871 1334068936 1404676856 1847280600", "293150249 562892059-1799638097", "543783302 1648311651 1713290162 1777876416", "1569431977-1613134074", "318953199", "1676375395-1858554414 1925577056-1976871183", "162753917", "1945611092", "1401316672 1795776975", "1051669334", "1147342736", "1385853380-1606846655 1614341287 1765106648", "1350442456", "823892825-1408761545", "1683483314", "1320720136 1935501272", "64104393"}

    {"747464076 1802229564", "503468162", "358309261", "1573005218 1671199923", "990043846 1317183820 1636338823-1806480913", "1434216174", "519909610-1988406427 1996711133 1998569885", "1344933746-1716062286", "1193705507 1669647798", "1451806832 1947832907 1967266102", "1975281952", "160760874", "580213935 660514665"}

    Returns: { 1401316672, 424265533, 1401316672, 1401316672, 836011060, 1935501272, 1935501272, 64104393, 64104393, 64104393, 64104393, 64104393, 64104393, 64104393 }

  13. {"1883606228", "790375042", "1204128046 1447783535-1624821395", "1862377777 1867152923-1896574865 1994852259", "186977139-1646720313", "1391124259", "128941087-733305145 1281487616-1286896796", "1217000041 1462174054", "1830112069 1852805390 1867356608-1989055168", "1305619255 1922736246 1997659077", "1073892592", "1331389444 1407429526 1878605488-1955744335", "704162198", "653854865-1882852337", "61433122-1722770254 1726961723", "739778618-934560518 1280435068-1896457514", "1464386681-1856482275 1941102787", "211801813", "296637163-1403177086", "404996704", "1826776169 1940722646 1948473104-1998128487", "1631304090 1696262936 1786151058", "288791341-1101417037", "909996322-1369580143 1433369070-1734340409", "1767039044 1774656504 1799659682-1919969516", "1237999396-1561598761", "1770754823", "715204450 1915290587", "372045407 1036383923-1927267652", "1390724946 1825180326", "1938187920 1985659495 1988880277 1988995878", "1529858429 1697973489", "352811377", "124125153", "1175124430 1267250476-1934706490", "1867660953 1935891590 1944092716-1963310117", "1248950435", "660219717 914720081-1117247468 1737719880", "810697865 1408525911", "1522260989-1944535125 1998170381 1999958871", "944849184 1735969705 1884752533-1985402884", "1191590702 1802830688-1921882800 1940726399", "1123008947 1309888791-1509273496", "1688193954 1962471533 1976758459 1981326130", "395108209-907032902 1227555047-1303267670"}

    {"701957959", "314733890", "126472365-488111666 1337591010-1396447449", "618890945", "1459679293 1558476941-1740121304 1967223681", "789932099-1248783376 1696651023-1814251312", "593075186", "968972557", "116777400-1111326584 1346057128-1904539247", "56169754-1327077338", "614601470", "837089723 916965436", "687782011-1013653556 1143170496 1541902373", "1909621559", "1793638550 1996658386", "724023859"}

    Returns: { 1529858429, 1883606228, 1883606228, 1883606228, 1883606228, 1883606228, 1883606228, 1883606228, 1883606228, 1248950435, 1938187920, 1938187920, 1938187920, 1938187920, 1938187920, 1938187920, 1938187920 }

  14. {"352111574-553255188 570851830-1130087254", "279252743 1864759062 1992603857", "2355147 646984883-1482909152", "75254561", "1007499040", "368351667-973225505 1286471870 1326493068", "1680566759 1681347052 1781616503", "541780560-873290044", "104696485-443338182 1963098101 1972843740", "1937005747 1978963339 1994809172", "1564510640 1610514104 1638547208-1749543250", "570093852-1997398402", "137868797", "230522719-927430307", "226898474-1592528661 1692633580", "638158326 1563862413 1828089355 1984543089", "672944739-1727677772 1999502262 1999830223", "694713435-960265781 1058307736-1824764247", "746600147 1840306398 1951429296-1956786425", "1497871527", "232191131-1006107937 1941959868", "2690668-285546820 1109898513", "627199683-684974173 766396587 768682615-1080305452", "324183158 1051234451-1108698941 1554393929", "206809472 1791075251", "34249617-1806546342 1911729311-1912850231", "816754216-1019442506 1252779858-1735996400", "1679423245 1846540976 1934888394", "1396030731-1784474848 1891289166 1956023743", "503013381", "562938452 813196620 1354032401-1549271626", "1256100904", "563249850 1369082627", "152437642 1127113354 1226626926", "140003023-887909985", "411913500-1391644797", "925749784 929394125 1951673682", "974847843-1975654364 1986785505", "237155960 1407437555 1920796189 1967538180", "731984787-1227033387", "1922695031"}

    {"449676618 1918090070", "185898375-1517371833 1527568645-1958731658", "771232029-1360461652 1712575437 1769532319", "563870078 1038796331", "1638862225-1716575585", "1919515872 1983450321 1985716594 1998908653", "1890453615 1909346651-1959759399", "382281930 1111815236 1764160975", "75840002-192879488"}

    Returns: { 813196620, 813196620, 75254561, 75254561, 75254561, 75254561, 75254561, 75254561, 75254561, 75254561 }

  15. {"54290120-1227751966", "1307777629", "231379326-778358482 1212011456-1792330756", "359055613 905594723 1330271849 1961994710", "504936515-647308863 1188183179", "447245639-1057026440", "70135925 1669348146-1775539473 1916055357", "1237576720 1959211727 1966427716 1996565238", "1816951747", "695569565 1208976809-1982304848 1988542632", "269320538-939248259 1522259506", "404776334", "599209412", "1062933208 1381940397 1899944150", "544286263", "1499696540 1798324370", "573025105", "406232331", "297482693", "360112839 483199043 1186010518 1913006026", "1952706607 1999879284 1999927498", "784836406-1678152776 1868465699 1971196345", "1291055104 1993867332", "1114826105-1977858856 1986238482 1989623150", "840314218-1098611075", "249479515 1098648123-1405372337", "616794164 857327661-924567267 1251871044", "801871155-1202460277 1634371638", "1103791531 1283239099-1704195633 1722913289", "1062358367-1413201549 1885656583 1940970542", "1003955753 1142096506-1862596910 1989176115", "985005950 1483440193", "448270773 1066469112 1070946626 1181279363", "1423469708 1921244568", "348487210 424668459 657141752 1371939539", "1156903667 1375248197 1606491522 1759203982", "487462241-804977838", "1670676990 1782014250", "1749132442 1868859494 1941592462-1993000547", "155778838-1531776954 1578406015-1687368015", "1955774068", "847882403-1609789568 1610374335-1889607889", "1796229434 1963783482", "946947520-1529441488", "510733416", "42209728 783407631 1516495735-1679858137"}

    {"1841385319 1855174726 1972144811 1973157335", "119463567-398361266", "729975492 1774915178", "1011141744-1229860550 1335430178", "1319221693-1802976510", "127691886-1056654562 1300053824-1729439785", "1651014133 1919460792 1968996728", "296686818-1259559879 1370877688-1617313112", "1141735153-1238835108", "1968941222 1971708216-1982007097 1986132944"}

    Returns: { 1291055104, 905594723, 985005950, 1062933208, 1670676990, 404776334, 1237576720, 1237576720, 1291055104, 1291055104, 1291055104 }

  16. {"960641349 1366036300 1917010661 1951756139", "442349350", "1722174596", "1464868511", "209078912-1410878835 1697138074", "1555586550", "1326253720-1707833689 1710801379-1972230856", "1470681437 1799769594 1835126889 1896970266", "1705367711 1824625448-1835122179 1911720800", "916391661 973516083", "537364108", "1923709777 1959303394 1995495614", "478167412-1803431221", "500661877 1451620493", "853142698-1018901703 1562022666-1930733989", "1143889014 1921370378 1929799646-1978536451", "30689855-1405977044 1923986399 1992975888", "288306781-1238510849 1254470097-1450788776", "987404528-1710418382", "212177601 1345685964 1573364909 1966559870", "1012715642 1268512679-1866763648", "204379972 1102315338 1547920681-1785979506", "478371135 803741274-1783776062 1936992904", "69961870 566296387 761564195-979491813 1321454868", "1030693121", "519691812 672974842 1442065359 1464462803", "40739009 1901209772 1913483643", "340869124 1891558850", "595696293 1080078923 1201241138-1651667152", "413997838-1571086323", "620966203 1898861609", "669516991 1302184386-1938686469 1998705813", "1891942272 1943691554", "1952692660", "1508052842-1756169722", "1724998998", "1684510266", "389885675", "159748517-753872535 876643477-1413743392", "770845954-1750379870 1991691130 1999953832", "1913037562 1951829126 1964334238-1991228502", "897787375 1412766359 1530962571", "556682178-1126153973", "108311282", "654128086", "1572681611 1926430916 1955124491", "330416880", "422126774-1070567251 1403343556 1599614114"}

    {"1415752219 1670483326 1724550816-1994963827", "279983593", "812039929-1669403100 1748040075-1949627005", "1164376046", "659471327-1706309745 1946422989-1993044283", "285480963 1931682737", "344376256 383519678 1200310747-1856910181", "1505300311 1579666650", "179520134-339247344", "550105929 1408966668-1636322938 1928786475", "838772351 1358733131 1480945374-1709468372", "1716866141 1977840928 1994251954", "1438987093-1501100785 1520434741-1938111171", "681771723-1160158995 1806948765 1850692541", "196668107 303968860-1364211197 1986835520", "559719513-1446163487 1478021371-1540309773", "613712267-1725340270", "1535910192", "681200708-1879736778 1981021299 1997265854", "145439809-1996396189"}

    Returns: { 1345685964, 897787375, 897787375, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282, 108311282 }

  17. {"263724749-1586919263 1993462119", "976932562-1816676273", "1944724978", "379831600 1087175961-1963108721 1992226645", "141502846 1784990343", "476914677-1071444792", "1916602545 1998899933 1999969493 1999987424", "284395664", "1023778553-1555997369 1955416367", "1680338097", "502882278", "1143377572 1436343020", "981785928 1997544593 1998692644", "1132716934 1579867464 1739784146", "1524088275 1622844040", "609411289 1267062250-1801059997 1906344948", "930996266-1453075821", "1190779622 1311984872 1895842562 1982948144", "194861257-1043214698", "1328454759-1959157820 1987997384", "698263583 733207822 1383132088", "175842497", "1335690666 1602693379", "1970822580 1976687556 1999125957 1999638710", "399118780-1235767737 1496689679", "556577040 1268395856", "1715686839", "760848536-794582978 870349759 893533260", "452863991 631188531 1497509732", "130502813 1222962429", "1391924688 1432208428-1449725994 1750102819", "1424491117 1780612530 1958911825", "739205571-1983319097", "801047835 1861445439 1880336216 1890136324", "1634522500 1766205766-1957419104", "530139727 1043704028 1282700758-1477857888", "270709617-1112443220 1575944082", "568591595-1087060042", "283860175", "336779772 955759121-1202845652 1498542905", "1890444645 1894081223", "1755178629 1836377066 1907013584-1981334912", "904354256", "2000807-905386744 1153185640-1310975221 1686028744", "118281678-1766008949 1766667601-1856851743", "630056964-772030961", "1109427235"}

    {"1604038465", "710255875 1568367765 1590066476 1836303232", "1071566759", "19937345 1024872929 1503338721-1935137857", "1269302621 1754254906 1997182585 1998467621", "668294535 1377961002-1909815120", "1824613352", "308452952 1172067661 1572475485", "328516399 1450577814 1470131989-1496424611", "1649682937 1875464151", "1425995768", "1106235759 1491303338-1830353564 1893437257", "1980165725 1984576412 1987822730 1992870601", "1337153355", "1841771102"}

    Returns: { 981785928, 631188531, 1436343020, 1436343020, 1383132088, 1383132088, 130502813, 130502813, 130502813, 130502813, 130502813, 130502813, 130502813, 130502813, 130502813, 130502813 }

  18. {"692187565", "1436268498-1498490945 1959857563", "371239311-450808335", "1993245503", "1339604616 1389574384", "678616449-987535896", "195490119-584302711 1322135695-1656128988", "1340306911-1854549472", "802133119-1158418707", "1993198691 1999500476 1999665849-1999666417", "1825632870 1924560749 1967888129-1981479173", "777653836 1213711283 1441511671-1828708176", "83380681 1201080653-1329334271 1371291237", "568335174", "1161577639", "795129953-875366860", "1282635501", "1457604260 1945484992", "1274024726 1458985817-1828711909 1945992283", "457518682 1440349014 1753651924 1936592086", "494312820 1122234285-1520050632", "476288918 666442294-875817776", "1827736239", "1042943597-1043675268", "1590320015 1780411882 1906392059", "482879880-1396439781", "883479930 1791491398 1858185082-1862540823", "352337408-1979597514 1993652427-1994539902", "742704348-966550931 1719196630 1850640154", "1845935909 1974605635", "894600543-950298551", "688096495-1037747068 1085430214", "45983817 301836397 759843414", "712084583 790165801 1595085906", "35809121-844330969", "577538881-1711573094 1844665553 1887133661", "1392664865 1566627546", "455919199-887598469 1239000988-1995570709", "472233036-1331543498 1704644267-1821511204", "307093761 1448819675-1953521231 1975069317", "3085186 330309393-1910594206", "486654795", "313226826-882299843", "1389089208"}

    {"1265227690-1433000810 1492241000-1769716975", "616850603-700970102", "1574623680", "842269941 1141663451-1992754905 1998976317", "114471778-1436074311 1933400104-1968513308", "3274541 441248575 1033146767-1746744690 1927015472", "1814617631 1816786861 1847060353", "282272366-1499036188 1771870726-1796263983", "1674389898 1923433346 1956282308 1981673640", "1489719438-1608500809", "538254067-911070904", "709521406", "594205155 835703917", "1487179825", "47159900 48697563-1033199998 1687223031 1786109668", "1578148691 1748187362", "1560230175", "1463199217 1847167486"}

    Returns: { 802133119, 802133119, 802133119, 802133119, 45983817, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691, 1993198691 }

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: