Statistics

Problem Statement for "Over9000Rocks"

Problem Statement

You used to have only 30 rocks, but now you have plenty of them. In fact, we will assume that you have a potentially infinite supply of rocks. You would like to show that you own over 9000 rocks. You have a set of boxes. You will choose a subset of those boxes and fill them with rocks so that the total number of rocks will be over 9000. Each box has a lower and an upper bound on the number of rocks it may contain.

You are given the int[]s lowerBound and upperBound. For each i, the values lowerBound[i] and upperBound[i] have the following meaning: If you decide to use box i, the number of rocks you may put inside the box must be between lowerBound[i] and upperBound[i], inclusive.

X is a positive integer that has two properties:
  • X is over 9000.
  • It is possible to select some of the boxes and fill them with appropriate numbers of rocks in such a way that the total number of rocks used is exactly X.
Compute and return the number of possible values of X.

Definition

Class:
Over9000Rocks
Method:
countPossibilities
Parameters:
int[], int[]
Returns:
int
Method signature:
int countPossibilities(int[] lowerBound, int[] upperBound)
(be sure your method is public)

Constraints

  • lowerBound will contain between 1 and 15, elements, inclusive.
  • upperBound will contain the same number of elements as lowerBound.
  • Each element of lowerBound will be between 1 and 1,000,000 (10^6), inclusive.
  • Each element i of upperBound will be between lowerBound[i] and 1,000,000 (10^6), inclusive.

Examples

  1. {9000}

    {9001}

    Returns: 1

    You can place 9000 or 9001 rocks in the single box. Of the allowed values, only 9001 is over 9000.

  2. {9000, 1, 10}

    {9000, 2, 20}

    Returns: 15

    You have to choose box 0 and at least one other box, otherwise you have no chance of placing over 9000 rocks. If you only choose boxes 0 and 1, you can place 9001 or 9002 rocks. If you only choose boxes 0 and 2, you can place between 9010 and 9020 rocks, inclusive. If you choose all three boxes, you can place between 9011 and 9022 rocks, inclusive. Hence all possible values of X are 9001, 9002, and everything from 9010 to 9022, inclusive.

  3. {1001, 2001, 3001, 3001}

    {1003, 2003, 3003, 3003}

    Returns: 9

  4. {9000,90000,1,10}

    {9000,90000,3,15}

    Returns: 38

  5. {1,1,1,1,1,1}

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

    Returns: 0

  6. {9001,9002,9003}

    {9001,9002,9003}

    Returns: 7

  7. {9001}

    {9001}

    Returns: 1

  8. {9000,3,11,50,100, 900007, 90007, 102, 7, 11, 307, 9007, 1, 997, 56}

    {9000,5,13,54,100, 1000000, 100007, 104, 9, 11, 309, 9013, 1000000, 1009, 57}

    Returns: 2110691

  9. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    Returns: 14991000

  10. {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    Returns: 15

  11. {177258,439976,996972,281567,782547,998375,491481,707710,146177,889410}

    {293261,559909,997946,410135,784021,998581,925665,743314,626775,943659}

    Returns: 7137090

  12. {315272,887545,64836,497408,974365,395811,835917,822205,763313,796755,541406,250512,772146}

    {661956,905285,360731,694427,999269,834462,889010,984734,976200,992732,952893,904500,853930}

    Returns: 10945294

  13. {712946}

    {871563}

    Returns: 158618

  14. {177389,865455,133264,739109,390897,157563,399400,426007,864298,612059,287649}

    {373901,975109,898401,993324,565760,949001,700614,750652,959908,874621,820179}

    Returns: 8728207

  15. {16859,287723}

    {287608,630151}

    Returns: 900787

  16. {77505,104830,58303,574406,229438}

    {658755,961848,273053,966870,779624}

    Returns: 3581848

  17. {647998,431340,617093,930533,861479,198561}

    {830560,870972,893128,997538,943907,264651}

    Returns: 4435508

  18. {729521,788949,148221,3423,231974,569820,332636}

    {951408,974213,708093,720084,459786,620622,497059}

    Returns: 4922265

  19. {650057,270366,180570,698312,338872,62431,15948,547413,828153,205852,755374,289622}

    {963292,607214,849697,707788,505320,833352,906522,861732,832867,882648,836582,514521}

    Returns: 9285588

  20. {7814,60843,695305,390426,879303,209688,58403,407967,120378,886777}

    {577125,986686,971243,392645,896113,953189,828267,946013,314552,929027}

    Returns: 7785860

  21. {80969,466757,904767,106216,562016,870595,886461,425044,224701,417318}

    {162285,598837,928929,442628,617607,928392,891079,587088,467202,759924}

    Returns: 6303003

  22. {633261,151066,677628,28480,666116,190295,443690,304836,47375,729836,264290,549776}

    {674277,707113,790488,489728,799813,473682,970799,765743,560994,965435,957783,590809}

    Returns: 8718185

  23. {82160,853398,875890,77842,932128,336944,194062,149117,933699}

    {580520,989107,966779,242532,940316,876494,953510,677091,991468}

    Returns: 7139976

  24. {409251,99538,871775,363786,43957}

    {983987,338409,938943,892886,576468}

    Returns: 3686737

  25. {784275,330854,628295,405112,317668,784207,74353,102753}

    {863846,339275,979607,645592,739902,805014,95161,211513}

    Returns: 4586974

  26. {274874,221460,292130,246617,186677,353497,485281}

    {583911,672584,730676,380829,855188,746775,507997}

    Returns: 4291284

  27. {425785,201968,869280,653990,495155,491951,711748,246375,818210,738463,679178,229828}

    {629164,617611,907753,705915,899563,649561,956880,273803,973764,965920,681190,589929}

    Returns: 8649086

  28. {976450,95080,795474,771972,285458,819403}

    {997914,307461,904666,890524,292447,858785}

    Returns: 3911579

  29. {467261,313018,599921,681293}

    {542669,408021,642233,855205}

    Returns: 1958177

  30. {926794,111826}

    {965194,529658}

    Returns: 912467

  31. {737698,711627}

    {932146,972130}

    Returns: 715456

  32. {83236,489004}

    {412666,891679}

    Returns: 1144773

  33. {483961,404107,39322,489707,50082,946144,750029,935461,921277,46459,904585,665132}

    {783504,490638,239283,931380,514006,957780,812575,986086,935428,120468,911693,903225}

    Returns: 8546745

  34. {94983,298655,833138,236480,237270,143125,68677,934715,321856,546225,915637,465282,66162}

    {132302,895307,912018,400106,901768,624079,287815,953342,378623,864415,952164,806394,348192}

    Returns: 8390364

  35. {974969,805241,739803,866190,638362}

    {992129,995480,953933,888003,865695}

    Returns: 3175327

  36. {230278,209436,439387}

    {631123,796195,583394}

    Returns: 1801277

  37. {660899,97798,199286,669088}

    {672354,310972,511562,903894}

    Returns: 2300985

  38. {789006,400519,904491,931026,622039}

    {822647,743268,927521,959138,949966}

    Returns: 3938603

  39. {704001,75987}

    {706999,182667}

    Returns: 219359

  40. {379148,378238}

    {608520,602356}

    Returns: 683774

  41. {772791,627669,413070}

    {772798,627669,413080}

    Returns: 75

  42. {508657,660261,959192,321186,533351,372883,768502,188585,447067,424727,399176}

    {508659,660264,959193,321196,533361,372888,768510,188586,447069,424736,399178}

    Returns: 55783

  43. {25545,164282,230067}

    {25555,164283,230069}

    Returns: 59

  44. {427728,715349,550924,176187}

    {427728,715358,550925,176192}

    Returns: 135

  45. {268748,131052,669187,620952}

    {268756,131061,669190,620960}

    Returns: 239

  46. {31443}

    {31445}

    Returns: 3

  47. {404765,884161,186908,888425,914964,238311,494838,228860,633161,528474,270319,305496,421562,214922}

    {404773,884169,186912,888434,914970,238312,494846,228860,633163,528481,270320,305505,421565,214929}

    Returns: 573477

  48. {747339,274438,848042,44720,394591,354897,496062,107528,769842,101271,938414,645403,264660}

    {747339,274442,848046,44720,394592,354902,496065,107537,769844,101281,938415,645409,264668}

    Returns: 212711

  49. {388348,602772,593196,488573,318390}

    {388351,602776,593200,488577,318396}

    Returns: 367

  50. {918531,249906,48102,344093,658377,535257}

    {918533,249911,48103,344095,658386,535261}

    Returns: 799

  51. {417442,583965,620401,796053,963096,345467,261271,752631,849165,198969,558585,930284,916362,902104,370229}

    {417446,583966,620402,796063,963096,345471,261274,752634,849167,198972,558589,930288,916369,902107,370239}

    Returns: 870962

  52. {341350,309044,676894,94612,118726,117772,2479,493144,445031,680505,211883,350980}

    {341358,309048,676895,94614,118728,117777,2489,493153,445039,680514,211891,350982}

    Returns: 141986

  53. {806210,870589,111298,726329,947364,77661,988113,648605,494064}

    {806217,870596,111305,726339,947374,77665,988122,648613,494066}

    Returns: 16895

  54. {335704,53128,963116,590539,205027,878578,5086,630550,422438,6316}

    {335711,53138,963119,590547,205035,878584,5095,630559,422439,6321}

    Returns: 34799

  55. {216017,506975,101724}

    {216019,506980,101728}

    Returns: 51

  56. {328033,534976,979340,960007,93448,665819,691076,952522,790719,186616,920446,746017,158026,533315}

    {328113,535018,979417,960049,93500,665898,691088,952595,790762,186678,920544,746058,158047,533401}

    Returns: 3770844

  57. {629096,972742,306995,121574,421451,503168,958158,542102,673008,92046,315040,626250,988856}

    {629132,972760,307051,121601,421533,503240,958207,542169,673030,92075,315138,626291,988944}

    Returns: 2075200

  58. {107194,81106,735120,604912,125702,966051,735850,850155,237366,190388,477449,277165,222903,384202}

    {107245,81189,735206,604982,125730,966065,735870,850166,237438,190459,477537,277190,222915,384249}

    Returns: 2748209

  59. {750007,790786,74424,216462,754449,255224,920106,901841,390459,486313,496152,917692,492513,970754,925193}

    {750082,790877,74470,216555,754472,255305,920152,901940,390548,486357,496204,917729,492584,970804,925240}

    Returns: 5227218

  60. {784819,665863,509769,377749,708171,595337,108611,661431,88909,117450,497745,904717,218610,668930}

    {784849,665928,509821,377826,708220,595415,108630,661444,88940,117534,497833,904730,218691,668950}

    Returns: 3029784

  61. {201987,89468,221660,707736,865128,27204,454373,141368,175264,241700,887798,501005,744634,728267,231239}

    {202060,89500,221739,707761,865189,27292,454461,141393,175294,241751,887808,501042,744718,728277,231281}

    Returns: 3865414

  62. {769490,612904,609247,103825,891314,900240,436228,240810,353121,497063,735053,789000,692330}

    {769524,612986,609299,103874,891408,900317,436239,240846,353155,497119,735145,789032,692355}

    Returns: 1872511

  63. {931027,168521,89715,3878,961708,542837,147691,13631,932041,1496,46369,747033,512340,409559,906490}

    {931083,168599,89805,3965,961758,542915,147755,13682,932137,1582,46441,747124,512399,409631,906585}

    Returns: 4750129

  64. {424868,429296,310382,804682,714618,19875,986172,314287,662473,154680,443408,931086,582493,86918,232398}

    {424926,429331,310429,804713,714695,19955,986186,314326,662569,154768,443458,931114,582514,86938,232421}

    Returns: 4171242

  65. {480547,799834,966873,817221,819882,422752,30367,444246,440690,90628,882833,171915,405481}

    {480610,799898,966887,817319,819968,422846,30394,444323,440771,90655,882867,171951,405570}

    Returns: 2294581

  66. {179155,499161,762544,805764,978254,506623,194452,369561,678260,615220,745440,206496,921692,721468,533158}

    {179321,499310,763214,806171,979173,507551,194953,370539,678566,615710,746101,207206,921858,721573,533486}

    Returns: 6737147

  67. {783623,997157,916082,400237,823559,284217,398651,675823,514964,502726,929379,621560,923712,23517,193249}

    {784582,997435,916647,400381,823992,284511,399223,676219,515442,503289,930348,622190,924276,23624,193615}

    Returns: 6891835

  68. {343117,407953,959207,198844,171581,66611,42199,917613,559836,244540,692942,112221,13442,66544}

    {343297,408240,959853,199606,172535,67002,43056,918132,560226,245194,693521,112676,13729,67370}

    Returns: 4369791

  69. {640356,496592,685025,63590,596841,909812,451671,227604,642752,203960,924815,786768,416312,778863}

    {640646,497500,685446,64324,597457,909972,452590,227900,643663,204230,925147,787650,416829,779405}

    Returns: 5733242

  70. {267328,609467,164970,73962,714741,250338,519122,392805,456605,524380,770443,761558,83892,954807}

    {267543,609772,165940,74091,715670,250886,519233,393052,457082,524674,771077,762488,84637,955507}

    Returns: 5163651

  71. {227669,493216,459411,720235,782007,373684,632256,961409,285364,162022,521907,648492,812599,250586,760939}

    {228373,493729,459781,721046,782727,373897,633058,961825,285509,162274,522238,649060,813573,251147,761321}

    Returns: 6337844

  72. {555799,663109,796694,91621,438209,965729,104113,618851,217010,723355,661471,68576,546056,851502}

    {556336,663591,797572,92582,438951,966422,104418,619072,217645,724173,662378,68820,546608,851929}

    Returns: 5744993

  73. {485387,14041,213524,974412,447224,854563,197466,47590,589957,550077,428419,349404,424378,209020}

    {485648,14537,213908,975000,448093,855235,198112,47810,590707,550902,429005,350383,425317,209725}

    Returns: 4779948

  74. {950878,682337,423320,370242,374986,584714,360686,829069,26174,594787,915882,366681,141636,226549}

    {951326,682480,423653,370404,375233,585699,361428,830027,26870,595483,916811,367308,141924,226716}

    Returns: 5279424

  75. {783833,108829,607906,741108,416803,690782,520143,377060,991664,87830,127999,331355,290128,677158,650237}

    {784456,109014,608632,741318,417785,690895,521118,377806,992420,88427,128176,332007,290298,677871,650576}

    Returns: 5962317

  76. {17422,29202,869368,938444,977076,418229,664521,130243,2787,32501,454656,824176,839522}

    {767176,707900,932463,953888,988458,650543,711959,621343,762857,824514,593492,997584,883706}

    Returns: 10386883

  77. {444561,610971,777845,657713,340863,21870,142267,965948,808909,908493,125533,842096,172979,354612}

    {905491,707168,832600,823539,699188,831481,508572,998744,933759,931567,733133,964699,202017,890427}

    Returns: 10940516

  78. {853707,869383,496552,752551,306931,819053,402968,239874,783257,217419,560262,890596,719666}

    {932399,883787,999024,994264,723086,900250,896250,956311,856296,672766,843452,918643,945296}

    Returns: 11304406

  79. {233469,536227,862195,446673,60772,795171,589289,27831,775819,259558,196931,946562,592829}

    {282061,927005,987936,816197,629271,932391,981509,462044,992665,982909,503236,971139,854840}

    Returns: 10295373

  80. {822059,198353,562576,123314,787664,758718,224042,390821,111373,904750,912907,502586,72090,572312,711249}

    {941980,839561,827082,590563,938497,964706,272662,667575,752787,998760,978156,704565,291270,937412,826905}

    Returns: 11460392

  81. {877065,927423,92023,918732,295910,212325,76621,333871,85651,315239,375235,169249,758977,177780}

    {998659,989799,446518,997296,415419,662550,736078,466576,512546,906836,846075,664160,776125,244282}

    Returns: 9586299

  82. {153777,629792,870364,963356,393480,926417,123336,102332,372103,475383,23309,933334,284249,675446}

    {292647,672419,922726,975874,465837,975055,715788,438615,826998,819290,887746,991758,354629,779638}

    Returns: 10095712

  83. {515995,518377,35315,472611,187648,610846,196258,744577,99018,427298,843432,190704,831209}

    {859515,717231,324465,698217,460207,685435,985142,851098,655086,619476,987107,815325,917284}

    Returns: 9540274

  84. {644764,614460,718449,545135,695991,901889,548404,890164,218201,620163,542056,736496,651017,983008,817021}

    {958996,777539,764408,832415,983391,999365,931834,916779,897808,902143,622779,935789,927826,997153,914116}

    Returns: 13144141

  85. {358630,165126,804877,46841,802425,262451,710675,235561,752869,761221,748508,929276,842134,338841,84023}

    {563457,733582,952703,652768,923335,525813,769424,776394,993198,854433,838822,987837,878780,545066,183106}

    Returns: 11131878

  86. {9000, 1, 10 }

    {9000, 2, 20 }

    Returns: 15

  87. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  88. {1, 2 }

    {60, 60 }

    Returns: 0

  89. {195989, 839442, 500900, 27466, 572588, 531327, 843043, 657612, 842158, 109927, 314065, 286080, 140263, 834620, 600238 }

    {195996, 839445, 500908, 27475, 572588, 531328, 843049, 657613, 842159, 109934, 314074, 286083, 140270, 834627, 600245 }

    Returns: 1097366

  90. {9008, 9010 }

    {9030, 9015 }

    Returns: 51

  91. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 133, 14, 15 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  92. {9000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14865014

  93. {173, 2, 1, 2, 1, 37, 11, 1, 1, 56, 1, 5, 1, 7, 124 }

    {999003, 987050, 1000000, 876666, 936111, 778222, 781333, 947439, 931678, 835000, 791000, 835147, 888789, 777456, 666123 }

    Returns: 13022017

  94. {20102, 21414, 1232, 1359, 32351, 19435, 30736, 17371, 11999, 15510, 28074, 21651, 10296, 3178, 18297 }

    {43097, 34781, 27555, 25041, 41590, 25754, 35243, 49803, 27354, 15552, 37077, 31583, 41376, 30538, 38375 }

    Returns: 495719

  95. {9005, 9030, 95000, 905300, 90040, 1000000, 22000, 94200, 94200, 90040, 90001, 90001, 9000, 9000, 900034 }

    {900900, 900000, 1000000, 1000000, 105000, 1000000, 1000000, 800000, 600000, 1000000, 1000000, 1000000, 1000000, 800000, 1000000 }

    Returns: 13096900

  96. {8986, 1, 9255, 9435, 4979, 11570, 5318, 5563, 10593, 13597, 10377, 9311, 12675, 2, 7438 }

    {723319, 9368, 545971, 387793, 938001, 839382, 525629, 518949, 202239, 437546, 306317, 400360, 604182, 973540, 730282 }

    Returns: 8133878

  97. {9000, 1000000, 888888, 111111, 222222, 333333, 444444, 555555, 123434, 1, 3546, 99999, 3, 14, 19 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 900000, 1000000, 1000000, 1000000, 1000000, 1000000, 20 }

    Returns: 13891020

  98. {1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000 }

    {2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000 }

    Returns: 126000

  99. {100, 101, 200, 301, 508, 88, 118, 182, 990, 9000, 9001, 9323, 23433, 23421, 123423 }

    {1000000, 1000000, 1000000, 9000, 1000000, 1000000, 999999, 1000000, 923422, 900122, 912345, 998733, 928332, 234444, 1000000 }

    Returns: 12897397

  100. {1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 999999, 978965, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14969964

  101. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    {999950, 999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964 }

    Returns: 14990355

  102. {9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001, 9001 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  103. {9000, 100000, 800000 }

    {90000, 200000, 900000 }

    Returns: 661002

  104. {9000, 1, 2, 3, 4, 5, 10 }

    {9000, 1, 2, 3, 4, 5, 20 }

    Returns: 35

  105. {9000, 9010, 9020, 9030, 9040, 9050, 9060, 9070, 9080, 9090, 9100, 9110, 9120, 9130, 9140 }

    {10000, 10010, 10020, 10030, 10040, 10050, 10060, 10070, 10080, 10090, 10100, 10110, 10120, 10130, 10140 }

    Returns: 109058

  106. {1 }

    {1000000 }

    Returns: 991000

  107. {14595, 41226, 93016, 116912, 122421, 176209, 249228, 252239, 357100, 536211, 540525, 628605, 868812, 987944, 994686 }

    {14865, 44665, 93241, 126111, 176208, 187652, 251378, 263717, 360304, 554034, 548001, 642144, 876927, 1000000, 997140 }

    Returns: 6027619

  108. {9000, 1, 10, 18, 1, 10, 18, 1, 10, 18, 1, 10, 18, 1, 10 }

    {9000, 5, 15, 23, 5, 15, 23, 5, 15, 23, 5, 15, 23, 5, 15 }

    Returns: 192

  109. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 999999 }

    Returns: 14990999

  110. {1, 12, 13, 14, 15, 16, 997, 98, 99, 98, 99, 99, 33, 334, 555 }

    {900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000, 900000 }

    Returns: 13491000

  111. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  112. {1, 10000 }

    {1000000, 10005 }

    Returns: 1001005

  113. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999 }

    Returns: 1490985

  114. {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, 1000000 }

    Returns: 2391000

  115. {3 }

    {9003 }

    Returns: 3

  116. {9000, 6666, 3333, 7876, 7657, 9000 }

    {9001, 9000, 9000, 9000, 9000, 9000 }

    Returns: 44004

  117. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 12, 14, 15 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  118. {9002, 9001 }

    {9002, 9001 }

    Returns: 3

  119. {1, 1, 1 }

    {1000000, 1000000, 1000000 }

    Returns: 2991000

  120. {9000, 101, 105 }

    {9000, 110, 106 }

    Returns: 21

  121. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

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

    Returns: 1490001

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

    Returns: 1491000

  123. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999 }

    Returns: 13990986

  124. {99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14900002

  125. {999967, 999667, 999790, 999224, 999862, 999758, 999668, 999800, 999465, 999862, 999173, 999868, 999266, 999125, 999148 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 69425

  126. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999 }

    Returns: 9990990

  127. {1, 1251, 2501, 5001, 7501, 10001, 125001, 250001, 500001, 625001, 750001, 875001, 900001 }

    {1250, 2500, 5000, 7500, 10000, 125000, 250000, 500000, 625000, 750000, 875000, 900000, 1000000 }

    Returns: 5042250

  128. {1066, 1055, 1062, 1073, 1080, 1064, 1064, 1089, 1019, 1092, 1054, 1061, 1034, 1027, 1032 }

    {880543, 979681, 661162, 111481, 30367, 970173, 435905, 162684, 374059, 588060, 390438, 913584, 264589, 394196, 633246 }

    Returns: 7781168

  129. {9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  130. {9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000 }

    {9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000 }

    Returns: 14

  131. {10000, 9000 }

    {10000, 11000 }

    Returns: 4001

  132. {90001 }

    {90001 }

    Returns: 1

  133. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

    {1000000, 999999, 999998, 999997, 999996, 999995, 999994, 999993, 999992, 999991, 999990, 999989, 999988, 999987, 999988 }

    Returns: 14990897

  134. {9500, 9501, 9503 }

    {9505, 9502, 9507 }

    Returns: 31

  135. {9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000, 9000 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 11991000

  136. {8900, 1, 1, 50, 50, 100, 100 }

    {9000, 100, 100, 150, 150, 200, 200 }

    Returns: 900

  137. {10, 9010, 1000000, 1000000, 1000000, 1000000 }

    {20, 9020, 1000000, 1000000, 1000000, 1000000 }

    Returns: 203

  138. {60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 245760, 491520, 983040 }

    {60, 120, 240, 480, 960, 1920, 3840, 7680, 15360, 30720, 61440, 122880, 245760, 491520, 983040 }

    Returns: 32617

  139. {9001, 9002, 10000 }

    {15000, 9003, 15000 }

    Returns: 27001

  140. {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  141. {9001, 9002, 9050 }

    {9010, 9005, 9100 }

    Returns: 197

  142. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 }

    {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 }

    Returns: 23767

  143. {80000, 90000, 110000 }

    {130000, 100000, 120000 }

    Returns: 200003

  144. {9000, 1, 1, 1, 1, 1, 300 }

    {9001, 1, 1, 1, 1, 1, 500 }

    Returns: 213

  145. {500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 500 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 14991000

  146. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 900000, 999000 }

    {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 900000, 999000 }

    Returns: 14890000

  147. {10000, 11000 }

    {15000, 12000 }

    Returns: 11002

  148. {9001, 9005 }

    {9010, 9006 }

    Returns: 21

  149. {9001, 19001, 29001, 39001, 49001, 59001, 69001, 79001, 89001, 99001, 10001, 20001, 30001, 40001, 50001 }

    {9500, 19500, 29500, 39500, 49500, 59500, 69500, 79500, 89500, 99500, 10500, 20500, 30500, 40500, 50500 }

    Returns: 539045

  150. {8995, 8991, 8991, 9005, 8997, 9001, 8992, 9002, 8991, 9008, 8997, 9001, 8999, 8997, 9005 }

    {9000, 8998, 8992, 9007, 9003, 9005, 8995, 9004, 8997, 9013, 9003, 9009, 9001, 9006, 9009 }

    Returns: 1260

  151. {661397, 450280, 69413, 622139 }

    {772690, 843467, 300873, 836437 }

    Returns: 2534649

  152. {10000, 20000 }

    {10000, 20000 }

    Returns: 3

  153. {10000, 15000 }

    {20000, 17000 }

    Returns: 22002

  154. {20, 95, 9000 }

    {100, 96, 9000 }

    Returns: 163

  155. {32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288 }

    {32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288 }

    Returns: 32486

  156. {9000, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 }

    {9000, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384 }

    Returns: 16383

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: