Statistics

Problem Statement for "StoneGame"

Problem Statement

You and your friend are playing a game. There is a number of treasure chests hidden under piles of stones. That is, the i-th chest has stones[i] stones piled on top of it. You take turns taking exactly one stone from the top of one of the chests. Whoever takes the last stone from the top of a chest takes the chest and the treasure inside. The inside of the i-th chest is worth treasure[i]. The game objective is to gather as much treasure as possible.

Unfortunately, your friend is a cyborg and always makes the best possible move (maximizing his final win). Given stones and treasure, return the maximum total amount you can get from the chests given that you move first.

Definition

Class:
StoneGame
Method:
getScore
Parameters:
int[], int[]
Returns:
int
Method signature:
int getScore(int[] treasure, int[] stones)
(be sure your method is public)

Constraints

  • stones will contain between 1 and 50 elements, inclusive.
  • stones and treasure will contain the same number of elements.
  • Each element of stones will be between 1 and 10^6, inclusive.
  • Each element of treasure will be between 1 and 10^6, inclusive.

Examples

  1. {3,2}

    {1,2}

    Returns: 5

    In your first move you take the stone from the 0-th chest and take its treasure. Then your friend must take a stone from the 1-st chest leaving you with one stone on the 1-st chest. You take the last stone in your second move and take the contents of the 1-st chest.

  2. {5,4,3,2,1}

    {1,1,1,1,1}

    Returns: 9

  3. {5,5}

    {2,2}

    Returns: 0

  4. {1}

    {10}

    Returns: 0

  5. {5,4,15,457,345,13,235,346}

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

    Returns: 1407

  6. {2,2,1,2,3,2,2,1,1,2}

    {28,60,27,1,1,37,69,1,1,31}

    Returns: 4

  7. {3,2,2,2,3,1,1,1,3,1}

    {57,43,1,1,1,85,99,16,1,27}

    Returns: 14

  8. {2,3,3,1,3,3,2,2,1,1}

    {28,6,30,58,1,1,1,1,68,65}

    Returns: 16

  9. {1,3,2,1,1,3,3,1,1,3}

    {100,1,1,69,13,87,1,96,35,68}

    Returns: 16

  10. {1,3,3,1,1,2,3,2,3,3}

    {66,45,41,1,1,98,82,10,68,98}

    Returns: 1

  11. {1,1,3,2,3,3,3,2,1,3}

    {4,71,1,16,50,1,19,47,1,56}

    Returns: 4

  12. {3,2,3,3,2,3,2,2,3,2}

    {1,88,44,1,66,1,33,38,76,75}

    Returns: 22

  13. {2,3,2,3,2,1,2,3,3,1}

    {1,1,1,5,64,39,41,19,1,1}

    Returns: 17

  14. {1,1,3,1,3,1,1,3,3,3}

    {26,91,40,87,1,43,98,1,1,49}

    Returns: 17

  15. {3,3,1,3,1,2,3,2,2,3}

    {6,62,1,6,1,45,1,1,9,83}

    Returns: 20

  16. {384,887,778,916,794,336,387,493,650,422,363,28,691,60,764,927,541,427,173,737}

    {369,430,531,124,136,803,59,168,457,43,374,920,1,199,1,371,527,981,1,863}

    Returns: 937

  17. {171,997,282,306,926,85,328,337,506,847,730,314,858,125,896,583,546,815,368,435}

    {1,751,809,1,789,1,652,400,1,1,1,1,13,587,540,571,379,602,903,493}

    Returns: 1744

  18. {653,757,302,281,287,442,866,690,445,620,441,730,32,118,98,772,482,676,710,928}

    {857,354,966,684,625,1,733,504,271,1,1,341,797,619,847,922,380,1,1,1}

    Returns: 2046

  19. {842,351,194,501,35,765,125,915,988,857,744,492,228,366,860,937,433,552,438,229}

    {408,122,396,238,794,429,12,1,777,1,764,539,841,1,129,1,918,997,1,471}

    Returns: 2160

  20. {184,491,500,773,726,645,591,506,140,955,787,670,83,543,465,198,508,356,805,349}

    {623,1,344,569,1,312,606,662,879,321,1,1,523,709,1,259,1,63,1,1}

    Returns: 2504

  21. {37,453,900,380,551,469,72,974,132,882,931,934,895,661,164,200,982,900,997,960}

    {814,1,96,467,1,1,685,1,937,446,1,419,413,1,1,10,1,343,207,714}

    Returns: 10206

  22. {373,322,256,820,600,722,905,940,812,941,668,706,229,128,151,985,659,921,225,423}

    {397,631,1,1,1,1,626,223,641,899,299,525,210,820,1,1,995,1,770,777}

    Returns: 2556

  23. {851,256,861,143,580,885,994,206,622,568,505,614,962,755,327,260,945,203,203,507}

    {1,843,1,1,873,1,499,1,1,249,334,649,755,747,1,501,789,250,304,364}

    Returns: 2206

  24. {498,254,893,687,126,153,997,976,189,158,730,437,461,415,922,461,305,29,28,51}

    {1,1,795,700,40,429,501,648,160,536,340,1,128,1,50,1,430,336,901,972}

    Returns: 7894

  25. {950,290,368,989,293,796,744,145,830,391,683,341,542,570,827,233,262,43,361,118}

    {762,310,426,1,678,691,525,615,1,359,1,101,727,917,1,530,291,971,81,594}

    Returns: 1816

  26. {289384,930887,692778,636916,747794,238336,885387,760493,516650,641422,202363,490028,368691,520060,897764,513927,180541,383427,89173,455737,5212,595369,702568,956430,465783,21531,722863,665124,174068,703136,513930,979803,634023,723059,133070,898168,961394,18457,175012,478043,176230,377374,484422,544920,413785,898538,575199,594325,798316,664371}

    {803527,268981,241874,999171,497282,420926,336328,1,750847,661314,616125,819583,898815,515435,344044,171088,1,947179,393585,502652,612400,95061,993369,210013,698587,297540,480571,960379,66602,612903,570493,260757,560281,209442,429690,346620,1,958032,738098,834482,120710,704568,1,872354,276966,964684,28625,1,805733,409504}

    Returns: 25251366

  27. {530020,258271,363369,959709,486716,226341,518150,747797,700724,142619,2246,122847,493452,892922,243556,192380,597489,537765,888229,469842,792351,165194,441501,757035,87765,470125,324915,936988,275857,373744,346492,322228,148366,709860,281937,151433,452552,316438,899229,153276,975408,901475,276122,468859,794396,36030,661238,908236,573794,65819}

    {366144,335929,318777,964444,114614,118607,1,1,235129,1,67918,466997,987744,512184,295500,206726,755591,268140,469787,338083,388465,939508,228805,278612,127829,887344,35569,755423,613811,321802,473731,811306,1,1,248627,503466,473417,213259,167638,305625,1,433453,419380,947469,900974,903882,808934,158661,657200,548900}

    Returns: 1833634

  28. {252997,152960,713774,272814,739669,187191,681096,952927,116467,365085,911341,422091,327685,443377,855543,755937,379108,517446,219757,669180,418419,706888,89413,103349,32173,451660,262010,402337,625211,166343,467588,878207,319302,697714,667373,575322,401256,864820,44600,517722,229905,955940,939812,73941,915668,311706,346229,811128,829151,565985}

    {763921,1,867270,54082,740085,811973,1,647626,741223,306641,783899,352299,280525,688210,288820,1,371156,218005,614770,981777,247256,348143,445885,223206,679568,1,801962,31327,518945,613203,936785,222843,789529,608873,849959,448037,1,686249,33334,321649,999755,251747,1,514501,473789,66250,273304,505364,910254,247687}

    Returns: 2022164

  29. {519126,761153,613997,245976,209189,649158,703730,895437,32461,253415,543922,870461,26305,60029,388028,278051,266749,707557,308903,504795,697698,858700,571044,301040,132003,90429,806404,144501,682,617648,908539,36160,895152,522536,282135,104340,171693,502216,516128,720505,755630,60050,590965,298286,636430,495344,576336,903178,202901,885239}

    {416950,495368,392293,40744,1,658391,655341,570,174233,956043,1,228024,82,903191,618997,214678,730691,764525,349615,1,390359,1,565101,602727,204917,1,893530,532291,756971,819081,218594,418628,1,439215,193513,14413,909611,966190,806356,356621,198988,1,524567,27285,1,300607,125850,107206,35218,34946}

    Returns: 21450493

  30. {990784,436874,228459,710874,967638,804290,620484,826608,770479,772758,149315,334472,645730,591101,533460,723619,89439,58026,211389,633075,631234,518158,933682,3494,160359,550271,110700,633418,101840,275570,668364,92623,228795,413174,319848,196432,217463,456683,539391,504293,745792,205058,355116,391522,796158,888575,631492,401948,462952,359232}

    {610538,485055,554099,241082,653517,372232,261797,582339,519219,513971,784813,894978,31537,1,1,279208,984858,1,469912,663951,777561,675106,740050,588712,519935,77376,593615,343769,544919,376883,876983,124031,311575,186594,550254,803075,734714,138378,415776,1,935711,110295,400347,871138,305154,122574,1,449292,894019,836837}

    Returns: 1222978

  31. {596964,575056,387091,963859,378131,714905,698572,372662,369634,689686,304790,613074,722605,756852,419806,349251,767869,336504,109486,639007,82196,414640,62950,721121,80968,880227,686764,387678,290597,963982,740866,887561,539037,127956,367771,433519,359212,66343,322533,245197,272380,627322,858271,994985,384173,794428,344235,152041,647284,970073}

    {245831,370348,982031,653715,57523,626925,189436,1,622955,411899,875641,89160,679263,561042,1,208325,1,454155,335822,909366,591172,1,725219,621704,209934,53960,1,515798,1,121309,742699,76377,252716,825172,771560,554011,1,1,816540,1,58110,955082,671339,59427,785148,776788,696533,591282,884851,576591}

    Returns: 1917277

  32. {202255,215351,311132,973814,967858,381495,199182,146082,554604,15721,152434,887983,590182,97488,359416,79297,768826,765405,138723,796893,550552,230298,90033,399135,443182,898507,990416,767058,299709,380596,860000,501963,112298,687484,475777,80155,68978,191310,742588,139933,723383,895022,544267,313564,508861,903683,909212,277686,669087,564286}

    {735991,197315,754117,641893,395529,897526,651137,1,247644,80929,826622,917956,1,426816,543438,460009,811784,418658,363828,621270,726652,60911,1,228399,1,992394,433891,1,754553,126088,360100,448567,1,72642,89369,918185,696777,975267,588955,1,19594,322198,289673,806446,1,560998,648413,598383,914694,942440}

    Returns: 22559834

  33. {987335,88422,548160,994986,522958,1355,691762,578763,492973,631542,167717,561853,711851,703663,375483,550400,76218,665155,801174,399016,486507,839852,476365,724791,488264,942492,323173,570038,373538,18860,28829,360872,107281,576988,355857,146591,578342,563971,725353,587666,195512,893070,149518,907362,113084,41352,974113,189301,706507,291639}

    {709365,581033,136105,273680,413413,734970,916171,162845,1,726815,994315,713887,346040,701536,1,924394,637290,259632,584265,774549,101878,666834,994950,665156,678469,400961,98824,213172,185678,493246,572762,150324,84101,461076,322043,1,423920,225845,451239,474977,520020,526344,1,365982,953667,788968,1,1,380903,88132}

    Returns: 1499114

  34. {465003,683175,549208,649719,5217,301184,692378,945488,757473,434574,238958,725063,276126,713934,366798,312497,293419,893142,848154,971727,775475,596981,925394,843486,385949,372306,450031,264030,269560,206899,352161,734563,406425,417720,384281,411642,718903,593011,873481,992727,27584,628790,234141,303709,342724,600939,132558,152494,10432,980711}

    {785906,49614,963639,79422,207830,96181,209096,843025,1,952387,258233,155711,800031,609664,167280,429650,922352,857465,487331,147516,519916,843882,675635,854388,623288,339644,786743,890245,510140,552064,636354,1,558706,342734,992735,774316,691088,100670,916488,556838,598090,585206,1,1,402558,623404,1,300822,303606,646580}

    Returns: 1193740

  35. {325362,161529,273379,834448,332701,564046,574883,23788,804900,675552,242590,721387,650354,799427,966949,764795,163037,68507,277108,346093,665418,679665,115922,288821,98481,954167,105995,186355,774124,408438,832934,99485,86318,106313,933932,419018,186710,25166,959157,991609,217070,201746,712996,867423,1172,196296,148570,680560,264802,425677}

    {446572,658926,720173,874090,903567,255813,885197,453334,65187,263371,695569,286142,982640,744264,263591,206203,791632,1,511805,352347,898139,190496,36422,387227,134159,120357,1,585473,673340,475884,747662,587543,1,379175,1,407331,829295,260758,48861,533293,1,390280,963954,959296,96108,714938,944977,444585,720084,1}

    Returns: 1237320

  36. {11978, 22438, 27564, 12219, 8026, 10376, 8844, 23241, 19047, 20734, 8595, 5297, 5874, 7890, 14073, 3105, 27907, 15807, 29720, 3924, 6904, 22391, 23912, 19510, 9500, 29931, 22189, 23497, 13179, 1222, 8047, 7367, 4597, 11066, 29611, 8585, 30354, 16128, 9416, 13607, 533, 6042, 16076, 15329, 11988, 4316, 3536, 29373, 8646, 26538 }

    {1, 1, 1, 1, 1, 1, 29470, 4936, 10542, 1, 17647, 7845, 18916, 3313, 27553, 13687, 1, 27512, 17201, 15258, 25172, 21048, 23170, 27953, 22572, 32023, 12277, 30957, 26108, 16606, 7226, 3980, 2327, 14050, 24422, 3231, 7002, 19429, 1093, 7313, 28951, 13879, 3569, 997, 4946, 5920, 9123, 27583, 27184, 19331 }

    Returns: 72940

  37. {344670, 395122, 701417, 824426, 889874, 662168, 357861, 758063, 141266, 579279, 301876, 934548, 404649, 263866, 634159, 282485, 486755, 631222, 438853, 178102, 736633, 677583, 751510, 790366, 391271, 878330, 288072, 360078, 535500, 351194, 282066, 379309, 397881, 794116, 220348, 243532, 932954, 748125, 537761, 553807, 140396, 38801, 267780, 70481, 404391, 728522, 23837, 305591, 414504, 50727 }

    {344670, 395122, 701417, 824426, 889874, 662168, 357861, 758063, 141266, 579279, 301876, 934548, 404649, 263866, 634159, 282485, 486755, 631222, 438853, 178102, 736633, 677583, 751510, 790366, 391271, 878330, 288072, 360078, 535500, 351194, 282066, 379309, 397881, 794116, 220348, 243532, 932954, 748125, 537761, 553807, 140396, 38801, 267780, 70481, 404391, 728522, 23837, 305591, 414504, 50727 }

    Returns: 23506127

  38. {2000, 1500, 1000, 700, 600, 500, 400, 300, 200, 100 }

    {5, 3, 2, 41, 1, 1, 4, 8, 7, 12 }

    Returns: 600

  39. {104300, 107600, 4334, 10000, 100, 104320, 103200, 1000, 103320, 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, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 97531, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 319534

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

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

    Returns: 42

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

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

    Returns: 51

  42. {999199, 999299, 999299, 999399, 999499, 999599, 999699, 999799, 999679, 999954, 999993, 999992, 999999, 939999, 949999, 949999, 994999, 999599, 999969, 999299, 999219, 999919, 999999, 999399, 999499, 999939, 999299, 999999, 999299, 999299, 993999, 999999, 991999, 991999, 991999, 999919, 999919, 999919, 999199, 991999, 999199, 999199, 999119, 999119, 999199, 999199, 999999, 999129, 999199, 999129 }

    {999191, 999299, 999243, 999399, 999493, 999594, 999695, 999797, 1, 999954, 999993, 999692, 2, 939895, 1, 949992, 994991, 999592, 999963, 999294, 999215, 999916, 999991, 2, 999492, 999933, 1, 999991, 999291, 999291, 993991, 3, 991992, 991992, 991992, 999911, 999911, 999911, 999191, 991992, 999192, 999192, 999113, 999113, 999193, 999194, 999994, 999124, 999195, 999126 }

    Returns: 1949678

  43. {36245, 301980, 337680, 587703, 127304, 182157, 37791, 458402, 701628, 8521, 196267, 648709, 966050, 511284, 694396, 466193, 714032, 685831, 399480, 449263, 397137, 337577, 826634, 363687, 545130, 369994, 516416, 778215, 81596, 550177, 800143, 578678, 331934, 736318, 874780, 29940, 770609, 801474, 359281, 245074, 804538, 738000, 754240, 171142, 139488, 677020, 476743, 450948, 526348, 807307 }

    {1, 31380, 861049, 202581, 272922, 671655, 318692, 161796, 372239, 425674, 82013, 474795, 70570, 840855, 59725, 293297, 917285, 367907, 774665, 327926, 697675, 844171, 717983, 306642, 162626, 329497, 466021, 246654, 825677, 279030, 481767, 149185, 874336, 287295, 772754, 976460, 492528, 887937, 827277, 20297, 141057, 143505, 500808, 21676, 592935, 9649, 774479, 650658, 770489, 708107 }

    Returns: 36245

  44. {1, 65, 43, 623, 45, 6, 4, 342, 54 }

    {1, 1, 1, 4999, 4999, 4999, 5000, 5000, 5 }

    Returns: 1140

  45. {15312, 1, 4132, 531, 43 }

    {542, 1, 652, 1, 763 }

    Returns: 20018

  46. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 999999, 999999, 999999, 999999, 999999 }

    {10, 9, 8, 7, 6, 1, 2, 3, 4, 5, 10, 9, 9, 1, 100, 1, 2, 3, 4, 5, 10, 9, 9, 1, 100, 1000000, 1000000, 100000, 1000000, 100000, 1000000, 1000000, 1000000, 100000, 1000000, 1000000, 1000000, 100000, 1000000, 1000000, 1000000, 100000, 1000000, 1000000, 1000000, 999999, 999999, 9999, 99999, 99999 }

    Returns: 25000018

  47. {3, 3, 3 }

    {3, 3, 3 }

    Returns: 9

  48. {5, 3 }

    {3, 1 }

    Returns: 3

  49. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

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

    Returns: 50

  50. {100, 1000, 100, 1, 20, 2345, 645, 1325, 123, 75472, 124, 12351, 125, 6346, 246 }

    {2, 4, 2, 2, 301, 45, 100000, 100003, 1, 100005, 1, 100000, 1, 100000, 100000 }

    Returns: 100199

  51. {3, 4, 5 }

    {3, 3, 3 }

    Returns: 12

  52. {1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999, 1000000, 999999 }

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

    Returns: 49999975

  53. {1234, 234, 52, 351, 23, 345, 1, 1, 1, 1 }

    {1, 10000, 100000, 9954, 997, 12345, 54321, 9876, 98765, 56432 }

    Returns: 2243

  54. {99, 86, 33, 21 }

    {3, 3, 3, 3 }

    Returns: 0

  55. {100000, 100000, 999, 9959, 595656, 945645, 4546, 445, 46, 4564, 454645 }

    {1243, 454, 21, 78845, 21, 21, 84, 21, 2454, 121, 4854 }

    Returns: 2216505

  56. {400, 200, 300, 1000000, 1000000, 1000000 }

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

    Returns: 600

  57. {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: 1275

  58. {2, 1, 5 }

    {3, 1, 1 }

    Returns: 7

  59. {999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999 }

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

    Returns: 0

  60. {1, 1, 1 }

    {3, 3, 2 }

    Returns: 0

  61. {1, 31380, 861049, 202581, 272922, 671655, 318692, 161796, 372239, 425674, 82013, 474795, 70570, 840855, 59725, 293297, 917285, 367907, 774665, 327926, 697675, 844171, 717983, 306642, 162626, 329497, 466021, 246654, 825677, 279030, 481767, 149185, 874336, 287295, 772754, 976460, 492528, 887937, 827277, 20297, 141057, 143505, 500808, 21676, 592935, 9649, 774479, 650658, 770489, 708107 }

    {557508, 206031, 681086, 592852, 955457, 644056, 998372, 243781, 676166, 295696, 85891, 772322, 495279, 881684, 509967, 573323, 953194, 684834, 338712, 7608, 705351, 988938, 774046, 749573, 197708, 143648, 913599, 1, 589281, 864710, 689372, 287834, 93644, 628921, 280026, 1, 161235, 273189, 543686, 960793, 174365, 1, 268122, 177458, 576796, 498156, 285190, 155945, 609766, 739690 }

    Returns: 1119965

  62. {100, 100 }

    {3, 3 }

    Returns: 0

  63. {1, 1 }

    {3, 3 }

    Returns: 0

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

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

    Returns: 50000000

  65. {5, 5, 5 }

    {101, 101, 101 }

    Returns: 15

  66. {5, 4, 3, 2 }

    {3, 1, 1, 1 }

    Returns: 6

  67. {4, 4, 5, 6, 7 }

    {3, 3, 1, 2, 1 }

    Returns: 7

  68. {10, 10 }

    {3, 3 }

    Returns: 0

  69. {5, 5, 5, 5, 6, 6 }

    {5, 5, 5, 5, 6, 6 }

    Returns: 0

  70. {2, 3, 2, 3, 4, 5, 6, 5, 4, 5, 6 }

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

    Returns: 0

  71. {1, 1, 1, 1 }

    {1, 1, 1, 1 }

    Returns: 2

  72. {999992, 999991, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999991, 999999, 999999, 999999, 999999, 999999, 999949, 999999, 99991, 999993, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 7456 }

    {999994, 999992, 999991, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999991, 999999, 999999, 999999, 999999, 999999, 999949, 999999, 99991, 999993, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 456456 }

    Returns: 48107320

  73. {10, 7, 5, 100 }

    {3, 1, 1, 1 }

    Returns: 105

  74. {3, 3, 3, 3 }

    {3, 3, 3, 3 }

    Returns: 0

  75. {3, 3 }

    {3, 3 }

    Returns: 0

  76. {1234, 234, 52, 351, 23, 345, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1, 10000, 100000, 9954, 997, 12345, 54321, 9876, 98765, 56432, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 33333, 44445, 44445, 44445, 44445, 44445, 44445, 44445, 44445 }

    Returns: 2283

  77. {5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1 }

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

    Returns: 5

  78. {5, 1 }

    {3, 1 }

    Returns: 1

  79. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

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

    Returns: 0

  80. {622233, 999999, 216292, 778910, 15092, 471331, 417298, 792749, 569067, 215672, 315578, 297788, 241178, 584697, 939402, 168707, 188096, 242268, 724290, 893715, 147466, 574720, 57541, 668014, 452433, 847888, 162278, 287051, 119208, 336874, 412481, 299127, 55927, 915022, 910848, 584082, 818650, 375525, 283730, 66405, 958735, 947963, 409267, 870928, 757958, 390523, 304209, 358518, 983858, 555590 }

    {987987, 4, 603004, 427560, 1, 879983, 132401, 745934, 3, 936375, 414048, 909754, 635708, 1, 88341, 2, 49968, 221912, 1, 841408, 481247, 9822, 459104, 380864, 125266, 1, 52433, 427832, 562336, 464493, 1, 355496, 305912, 301384, 564212, 559085, 1, 714768, 653976, 2, 761089, 119051, 846900, 1, 646281, 748594, 999574, 251837, 1, 679064 }

    Returns: 2968517

  81. {1, 2 }

    {1, 1 }

    Returns: 2

  82. {5, 5, 5, 5, 5 }

    {3, 3, 3, 3, 3 }

    Returns: 25

  83. {9, 5, 4, 2, 10, 1, 5, 9, 8, 1, 8, 8, 10 }

    {8, 6, 5, 2, 1, 9, 1, 5, 5, 1, 1, 6, 2 }

    Returns: 15

  84. {28422, 6453, 12353, 22022, 24807, 21732, 24450, 24217, 19569, 10691, 9388, 9477, 5037, 28617, 15785, 24093, 3193, 2158, 7395, 11827, 5930, 10942, 21767, 30161, 2166, 13740, 29193, 22186, 27282, 31912, 25448, 1231, 22935, 17012, 23475, 14374, 32554, 22067, 18764, 21017, 29020, 1731, 19564, 2955, 30927, 24652, 20071, 16144, 539, 26649 }

    {7729, 9053, 15983, 19111, 13857, 2557, 14204, 12284, 3830, 30278, 23182, 10810, 9240, 8332, 16124, 29300, 3360, 14740, 11203, 26560, 20633, 587, 8302, 1166, 21512, 3000, 25913, 15928, 3371, 13104, 26229, 730, 22655, 11977, 24366, 18787, 6404, 15889, 5900, 26604, 1348, 21247, 14199, 9289, 17810, 18217, 31742, 13022, 18320, 28984 }

    Returns: 0

  85. {10, 100, 5, 2, 1 }

    {3, 3, 1, 1, 1 }

    Returns: 116

  86. {3, 1 }

    {3, 1 }

    Returns: 1

  87. {10, 10, 10 }

    {2, 3, 3 }

    Returns: 0

  88. {4, 6 }

    {1, 1 }

    Returns: 6

  89. {1, 2, 3 }

    {1, 2, 3 }

    Returns: 1

  90. {2, 2, 2, 3 }

    {1, 1, 1, 2 }

    Returns: 7

  91. {423, 423, 5345, 543, 123, 432, 23, 423, 423, 534, 423, 645, 312, 65, 87, 56, 5, 34, 756, 345, 645, 75, 45, 345, 5347, 567, 534, 423, 645, 765, 5345, 23, 6546, 45, 423, 4324, 5345, 23454, 534, 534, 534, 423, 4324, 234, 564, 56756, 7567, 56, 432, 423 }

    {4324, 645, 7987, 876, 876, 76, 76, 43, 534, 435, 65, 67, 657, 567, 234, 234, 234, 6, 76, 456, 456, 76, 645, 423, 4, 646, 64, 5435, 5345, 1233, 6, 456, 45, 6, 78, 3123, 34, 34, 3, 4, 56, 76, 78, 45, 342, 76, 34, 76, 6645, 7 }

    Returns: 138697

  92. {5, 5, 5 }

    {3, 3, 3 }

    Returns: 15

  93. {1, 1, 1, 1, 1 }

    {2, 2, 3, 3, 3 }

    Returns: 5

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

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

    Returns: 61

  95. {5, 3, 2, 2, 4 }

    {1, 1, 2, 2, 3 }

    Returns: 13

  96. {5, 5, 5, 5, 5, 5 }

    {3, 3, 3, 2, 2, 2 }

    Returns: 30

  97. {3, 3, 3 }

    {5, 5, 4 }

    Returns: 0

  98. {3, 5 }

    {1, 3 }

    Returns: 3

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

    Returns: 0

  100. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000 }

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

    Returns: 0

  101. {900001, 800001 }

    {900001, 800001 }

    Returns: 0

  102. {15, 15, 10, 100 }

    {2, 1, 1, 4 }

    Returns: 15

  103. {456, 789, 789, 45, 64, 567, 89, 789, 78, 9, 789, 78, 9, 78, 9, 78, 123, 48, 678, 6, 789, 789, 78, 9, 78, 978, 6, 7, 869, 78, 69, 32, 789, 789, 789, 78, 9, 789, 78, 9, 789, 78, 7, 456, 100000, 100001, 789, 456, 78, 789 }

    {56, 54, 48, 798, 7, 89, 789, 78, 45, 3, 45, 56, 45, 6, 78, 9, 7, 345, 3, 4, 789, 4563, 789, 456, 4523, 4, 56, 78, 69, 78, 9, 789, 78, 9, 78, 97, 8, 978, 9, 75, 786, 3462, 1435, 687, 8907, 68475, 675, 8765, 87, 6875 }

    Returns: 0

  104. {104300, 107600, 4334, 10000, 100, 104320, 103200, 1000, 103320, 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, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {1, 1, 1, 1, 1, 1, 2, 1, 1, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 999999, 97531, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    Returns: 41326100

  105. {9, 5, 6, 5, 8 }

    {1, 1, 5, 5, 5 }

    Returns: 28

  106. {2, 3, 4, 5 }

    {1, 1, 1, 1 }

    Returns: 8

  107. {1, 2, 3 }

    {3, 1, 3 }

    Returns: 6

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

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

    Returns: 1225

  109. {7, 7, 7, 7 }

    {3, 3, 3, 3 }

    Returns: 0

  110. {15, 14, 13, 12, 11, 154, 35, 365, 34, 565, 6745, 345, 65, 34, 65, 35, 345, 675, 345, 435, 6, 45, 865, 56, 68, 265, 4875, 546, 87, 345, 67, 345, 46, 67, 456, 3456, 47, 456, 67, 45, 67, 45, 67, 45, 76, 45, 76, 367, 45 }

    {1, 1, 1, 1, 1, 82, 62, 98, 100, 1500, 7216, 544, 542, 954, 85732, 76, 74, 72, 111, 33, 55, 77, 99, 121, 513, 747, 767, 757, 747, 7377, 73487, 4983, 765, 987, 543, 765, 765, 321, 54321, 87, 65, 45, 43, 23, 21, 67, 69, 65, 63 }

    Returns: 39

  111. {5, 6 }

    {1, 1 }

    Returns: 6

  112. {1, 1 }

    {1, 1 }

    Returns: 1

  113. {10, 10, 10 }

    {3, 3, 2 }

    Returns: 0

  114. {10, 7, 5, 100, 100 }

    {3, 1, 1, 1, 3 }

    Returns: 215

  115. {1, 2, 3, 4, 5, 6 }

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

    Returns: 12

  116. {5, 4, 3, 2 }

    {1, 1, 1, 1 }

    Returns: 8

  117. {1000000, 1000000, 1000000, 1000000, 1000000, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997 }

    {999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999997, 999996 }

    Returns: 49999865

  118. {2, 2 }

    {3, 3 }

    Returns: 0

  119. {1, 2, 4 }

    {1, 1, 3 }

    Returns: 6

  120. {1, 1, 1, 1 }

    {3, 3, 3, 3 }

    Returns: 0

  121. {10, 1 }

    {3, 1 }

    Returns: 1

  122. {16, 19, 98, 50 }

    {10, 3, 5, 4 }

    Returns: 0

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

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

    Returns: 3

  124. {2, 3 }

    {3, 3 }

    Returns: 0

  125. {3, 1 }

    {3, 3 }

    Returns: 0

  126. {1, 2, 4 }

    {3, 1, 1 }

    Returns: 5

  127. {10, 10, 10, 5, 4, 3, 2 }

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

    Returns: 38

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: