Statistics

Problem Statement for "ChristmasCandySplit"

Problem Statement

The modern Santa Claus figure is based on traditions that can be traced back to a real person, Saint Nicholas of Myra, who died in the fourth century. There are also some other adaptations of this historical figure in other cultures. For example, in a part of Europe Saint Nicholas (often assisted by an angel and a devil) comes to award well-behaved children and punish naughty children a few weeks before Christmas. Nice children are usually awarded various sweets.

Thomas is going to play Saint Nicholas this year. He has already purchased some small bags of different brands of candy. The sizes of these bags are given in the int[] bags.

Different brands of candy have different popularity among the kids. The popularity is consistent across the whole population of kids. Sadly, Thomas has no idea about which candies are more popular than others.

Kids care about fairness, but only in a limited way. If a group of kids get some candy, they compare two things: First, the total number of candies everyone got must be the same. Second, the total number of the best candies everyone got must also be the same. As long as these two conditions are satisfied, the kids will be happy that the split was fair.

As Thomas has no idea about popularity, his approach when giving out the candies is as follows:

  1. He shows all candy types he has to the kids and they tell him which candies are the best ones.
  2. He divides all the candy he has into equal-sized piles, each containing exactly one of the best candies and as many other candies as possible. (Note that some non-best candies can be left over.)
  3. He hands out the piles to kids until he runs out of candy. (The number of kids who want candy is potentially infinite, so this always happens, sooner or later.)

Thomas hates to waste candy, because doing so makes little Greta cry. He is now sad, because he realized that in step 2 of the above process he can have some leftovers, depending on which candy type is the most popular one. Thomas would like to avoid this situation at (nearly) any cost.

For each brand of candy, all bags have the same size. The bags for different brands have different sizes. For each positive integer i, there is a brand whose bags contain exactly i candies.

Thomas went to a wholesale store to purchase more bags of candy. He thinks that having multiple bags of the same brand is boring, therefore he is only willing to purchase brands he does not already have, and he is only willing to purchase one bag of each new brand.

Advise Thomas what sizes of bags he should purchase to make sure that he won't have any leftovers, regardless of which candy type is the most popular one. Return a long[] with the bag sizes (each representing a different new brand of candies).

Constraints your answer must satisfy:

  • The number of new bags Thomas will purchase must not exceed 100.
  • The total number of candies in all the bags (the ones he already has plus the ones you tell him to buy) must not exceed 10^18.
  • All bag sizes (considering both the ones he already has and the ones you tell him to buy) must be distinct.

There is always a solution that matches the above constraints, and any such solution will be accepted.

Definition

Class:
ChristmasCandySplit
Method:
buyMoreBags
Parameters:
int[]
Returns:
long[]
Method signature:
long[] buyMoreBags(int[] bags)
(be sure your method is public)

Constraints

  • bags will have between 1 and 22 elements, inclusive.
  • Each element of bags will be between 1 and 22, inclusive.
  • Elements of bags will be distinct.

Examples

  1. {2, 6, 4}

    Returns: {24, 36, 72, 144 }

    If candy from bag 0 is the best candy, Thomas will make two piles, each containing one best candy and 5 other candies. If candy from bag 1 is the best candy, Thomas will make six piles, each containing one best candy and 1 other candy. If candy from bag 2 is the best candy, Thomas will make four piles, each containing one best candy and 2 other candies. Thus, there are never any leftovers and Thomas does not have to purchase any other candies. Hence, {} is a valid solution. The example output shows another valid solution.

  2. {2, 4}

    Returns: {6 }

    Thomas can purchase a single new bag with 6 candies and obtain a solution essentially identical to Example #0. Note that {2} is not a valid answer, as he already has a bag with 2 candies and he won't purchase another one.

  3. {10, 12}

    Returns: {2, 30, 6 }

    After the purchase recommended by the example answer, Thomas will have a total of 60 candies and there will be no leftovers, regardless of which of his five bags of candy happens to be the most popular one.

  4. {1}

    Returns: {2, 3 }

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

    Returns: {506, 1012, 2024, 4048, 129536, 33161216, 66322432, 132644864, 265289728, 1061158912, 2122317824, 3681032355, 7362064710, 14724129420, 29448258840, 58896517680, 117793035360, 235586070720, 471172141440, 942344282880, 1884688565760, 3769377131520, 7538754263040, 15077508526080, 30155017052160, 60310034104320, 120620068208640, 241240136417280, 482480272834560, 964960545669120, 1929921091338240, 3859842182676480, 7719684365352960, 15439368730705920, 30878737461411840 }

  6. {16}

    Returns: {32, 48 }

  7. {21}

    Returns: {42, 63 }

  8. {22}

    Returns: {44, 66 }

  9. {17}

    Returns: {34, 51 }

  10. {2}

    Returns: {4, 6 }

  11. {9, 6}

    Returns: {120, 135, 270, 540, 1080 }

  12. {7, 12}

    Returns: {76, 304, 399, 798, 1596, 3192, 6384 }

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

    Returns: {496, 992, 1984, 3968, 126976, 32505856, 65011712, 130023424, 260046848, 1040187392, 2080374784, 3608284680, 7216569360, 14433138720, 28866277440, 57732554880, 115465109760, 230930219520, 461860439040, 923720878080, 1847441756160, 3694883512320, 7389767024640, 14779534049280, 29559068098560, 59118136197120, 118236272394240, 236472544788480, 472945089576960, 945890179153920, 1891780358307840, 3783560716615680, 7567121433231360, 15134242866462720, 30268485732925440 }

  14. {17, 1}

    Returns: {288, 306, 612, 1224, 2448, 4896 }

  15. {20, 21, 15, 11, 12}

    Returns: {158, 10112, 80896, 91245, 182490, 364980, 729960, 1459920, 2919840, 5839680, 11679360, 23358720, 46717440, 93434880 }

  16. {5, 2}

    Returns: {28, 35, 70, 140 }

  17. {11, 21, 16, 15, 4, 14, 6, 3, 20, 12, 10, 2, 8, 17, 13, 9, 5, 18, 1, 19}

    Returns: {448, 896, 1792, 3584, 114688, 29360128, 58720256, 117440512, 234881024, 939524096, 1879048192, 3259095840, 6518191680, 13036383360, 26072766720, 52145533440, 104291066880, 208582133760, 417164267520, 834328535040, 1668657070080, 3337314140160, 6674628280320, 13349256560640, 26698513121280, 53397026242560, 106794052485120, 213588104970240, 427176209940480, 854352419880960, 1708704839761920, 3417409679523840, 6834819359047680, 13669638718095360, 27339277436190720 }

  18. {6, 7}

    Returns: {52, 208, 273, 546, 1092, 2184, 4368 }

  19. {7, 2, 14, 17, 22, 18, 11, 10, 3, 16, 15, 12, 19, 20, 8, 6, 21}

    Returns: {442, 1768, 3536, 14144, 28288, 56576, 113152, 905216, 14483456, 231735296, 247342095, 494684190, 989368380, 1978736760, 3957473520, 7914947040, 15829894080, 31659788160, 63319576320, 126639152640, 253278305280, 506556610560, 1013113221120, 2026226442240, 4052452884480, 8104905768960, 16209811537920, 32419623075840, 64839246151680, 129678492303360, 259356984606720 }

  20. {18, 5}

    Returns: {92, 184, 736, 1035, 2070, 4140, 8280, 16560, 33120 }

  21. {21, 20, 16, 4, 14, 10, 12, 17, 2, 3, 6, 8, 5, 11, 13, 18, 19, 22, 1}

    Returns: {444, 888, 1776, 3552, 113664, 29097984, 58195968, 116391936, 232783872, 931135488, 1862270976, 3229996770, 6459993540, 12919987080, 25839974160, 51679948320, 103359896640, 206719793280, 413439586560, 826879173120, 1653758346240, 3307516692480, 6615033384960, 13230066769920, 26460133539840, 52920267079680, 105840534159360, 211681068318720, 423362136637440, 846724273274880, 1693448546549760, 3386897093099520, 6773794186199040, 13547588372398080, 27095176744796160 }

  22. {10, 18}

    Returns: {112, 224, 896, 1260, 2520, 5040, 10080, 20160, 40320 }

  23. {1, 4, 18, 15, 22, 17, 2, 19, 13, 16}

    Returns: {1016, 4064, 32512, 65024, 130048, 520192, 1040384, 4161536, 8323072, 16646144, 33292288, 66584576, 133169152, 263970135, 527940270, 1055880540, 2111761080, 4223522160, 8447044320, 16894088640, 33788177280, 67576354560, 135152709120, 270305418240, 540610836480, 1081221672960, 2162443345920, 4324886691840, 8649773383680, 17299546767360, 34599093534720, 69198187069440, 138396374138880, 276792748277760 }

  24. {7, 19}

    Returns: {104, 3328, 3458, 6916, 13832, 27664, 55328, 110656, 221312, 442624 }

  25. {5, 22, 9, 19, 8, 15, 4, 20, 11, 13, 7}

    Returns: {266, 532, 1064, 4256, 34048, 68096, 136192, 272384, 8716288, 34865152, 69730304, 113828715, 227657430, 455314860, 910629720, 1821259440, 3642518880, 7285037760, 14570075520, 29140151040, 58280302080, 116560604160, 233121208320, 466242416640, 932484833280, 1864969666560, 3729939333120, 7459878666240, 14919757332480, 29839514664960, 59679029329920 }

  26. {5, 17, 10, 4, 8, 19, 12, 7, 16}

    Returns: {196, 784, 1568, 3136, 6272, 100352, 3211264, 3323670, 6647340, 13294680, 26589360, 53178720, 106357440, 212714880, 425429760, 850859520, 1701719040, 3403438080, 6806876160, 13613752320, 27227504640, 54455009280, 108910018560 }

  27. {11, 5}

    Returns: {32, 64, 256, 512, 880, 1760, 3520, 7040, 14080, 28160 }

  28. {15, 14}

    Returns: {232, 928, 1856, 3045, 6090, 12180, 24360, 48720, 97440, 194880 }

  29. {21, 5}

    Returns: {208, 832, 1664, 2730, 5460, 10920, 21840, 43680, 87360, 174720 }

  30. {15, 18, 11, 4, 3, 16, 10, 13, 6, 17, 9, 20, 12, 22}

    Returns: {352, 2816, 11264, 45056, 90112, 360448, 1441792, 5767168, 11534336, 19253520, 38507040, 77014080, 154028160, 308056320, 616112640, 1232225280, 2464450560, 4928901120, 9857802240, 19715604480, 39431208960, 78862417920, 157724835840, 315449671680, 630899343360, 1261798686720 }

  31. {11, 21}

    Returns: {64, 128, 1024, 2048, 4096, 7392, 14784, 29568, 59136, 118272, 236544, 473088, 946176 }

  32. {7, 22}

    Returns: {116, 232, 1856, 2233, 4466, 8932, 17864, 35728, 71456, 142912 }

  33. {16, 19}

    Returns: {70, 560, 665, 1330, 2660, 5320, 10640 }

  34. {6, 11, 9, 22, 18, 16, 7, 8}

    Returns: {388, 1552, 3104, 12416, 49664, 67221, 134442, 268884, 537768, 1075536, 2151072, 4302144, 8604288, 17208576, 34417152 }

  35. {13, 7, 15, 2, 1, 16, 14, 12, 22, 18, 8, 6, 19, 11, 4, 21, 5, 3, 9}

    Returns: {412, 824, 1648, 6592, 52736, 105472, 210944, 421888, 13500416, 54001664, 108003328, 176306130, 352612260, 705224520, 1410449040, 2820898080, 5641796160, 11283592320, 22567184640, 45134369280, 90268738560, 180537477120, 361074954240, 722149908480, 1444299816960, 2888599633920, 5777199267840, 11554398535680, 23108797071360, 46217594142720, 92435188285440 }

  36. {12, 1}

    Returns: {26, 39, 78, 156 }

  37. {2, 1, 3, 11, 21, 20, 7, 14, 9, 16}

    Returns: {832, 13312, 26624, 106496, 212992, 360360, 720720, 1441440, 2882880, 5765760, 11531520, 23063040, 46126080, 92252160, 184504320, 369008640, 738017280 }

  38. {2, 11}

    Returns: {26, 104, 143, 286, 572, 1144 }

  39. {14, 10}

    Returns: {48, 768, 840, 1680, 3360, 6720, 13440, 26880 }

  40. {14, 21}

    Returns: {140, 560, 735, 1470, 2940, 5880, 11760 }

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

    Returns: {474, 948, 1896, 3792, 121344, 31064064, 62128128, 124256256, 248512512, 994050048, 1988100096, 3448239795, 6896479590, 13792959180, 27585918360, 55171836720, 110343673440, 220687346880, 441374693760, 882749387520, 1765498775040, 3530997550080, 7061995100160, 14123990200320, 28247980400640, 56495960801280, 112991921602560, 225983843205120, 451967686410240, 903935372820480, 1807870745640960, 3615741491281920, 7231482982563840, 14462965965127680, 28925931930255360 }

  42. {12, 19, 13, 2, 21, 15}

    Returns: {164, 328, 656, 5248, 20992, 83968, 671744, 1343488, 2126670, 4253340, 8506680, 17013360, 34026720, 68053440, 136106880, 272213760, 544427520, 1088855040, 2177710080, 4355420160, 8710840320, 17421680640, 34843361280 }

  43. {15, 11}

    Returns: {104, 832, 3328, 4290, 8580, 17160, 34320, 68640, 137280, 274560, 549120 }

  44. {19, 9}

    Returns: {56, 224, 896, 3584, 4788, 9576, 19152, 38304, 76608, 153216, 306432, 612864 }

  45. {16, 15}

    Returns: {62, 124, 248, 465, 930, 1860, 3720, 7440 }

  46. {8, 7}

    Returns: {30, 60, 105, 210, 420, 840 }

  47. {16, 6}

    Returns: {44, 66, 132, 264, 528, 1056 }

  48. {22, 15, 14, 18, 9, 17, 10, 4, 20, 21, 19, 8, 6, 12, 1, 11, 7}

    Returns: {428, 1712, 3424, 13696, 27392, 54784, 109568, 876544, 14024704, 224395264, 239507730, 479015460, 958030920, 1916061840, 3832123680, 7664247360, 15328494720, 30656989440, 61313978880, 122627957760, 245255915520, 490511831040, 981023662080, 1962047324160, 3924094648320, 7848189296640, 15696378593280, 31392757186560, 62785514373120, 125571028746240, 251142057492480 }

  49. {17, 5, 14, 12, 20, 11}

    Returns: {158, 1264, 2528, 10112, 80896, 161792, 1294336, 1551165, 3102330, 6204660, 12409320, 24818640, 49637280, 99274560, 198549120, 397098240, 794196480, 1588392960, 3176785920, 6353571840, 12707143680, 25414287360 }

  50. {2, 18}

    Returns: {160, 180, 360, 720, 1440 }

  51. {8, 6, 11, 12, 15, 21, 7, 18, 16, 20, 19, 17, 13, 1, 2}

    Returns: {372, 744, 1488, 2976, 95232, 24379392, 48758784, 97517568, 195035136, 780140544, 1560281088, 2706213510, 5412427020, 10824854040, 21649708080, 43299416160, 86598832320, 173197664640, 346395329280, 692790658560, 1385581317120, 2771162634240, 5542325268480, 11084650536960, 22169301073920, 44338602147840, 88677204295680, 177354408591360, 354708817182720, 709417634365440, 1418835268730880, 2837670537461760, 5675341074923520, 11350682149847040, 22701364299694080 }

  52. {3, 11}

    Returns: {448, 462, 924, 1848, 3696, 7392, 14784 }

  53. {9, 8}

    Returns: {136, 153, 306, 612, 1224 }

  54. {4, 22, 9, 11}

    Returns: {92, 1472, 2944, 4554, 9108, 18216, 36432, 72864, 145728, 291456 }

  55. {20, 17, 4, 16, 2, 1, 6, 19, 18, 21, 15, 11, 8, 22, 7, 14}

    Returns: {402, 1608, 3216, 12864, 25728, 51456, 102912, 823296, 13172736, 210763776, 224958195, 449916390, 899832780, 1799665560, 3599331120, 7198662240, 14397324480, 28794648960, 57589297920, 115178595840, 230357191680, 460714383360, 921428766720, 1842857533440, 3685715066880, 7371430133760, 14742860267520, 29485720535040, 58971441070080, 117942882140160, 235885764280320 }

  56. {5, 7, 11, 3, 9, 19, 1, 16, 14, 6, 20, 12, 15, 2, 13, 10, 4, 8}

    Returns: {350, 700, 1400, 5600, 44800, 89600, 179200, 358400, 11468800, 45875200, 91750400, 149774625, 299549250, 599098500, 1198197000, 2396394000, 4792788000, 9585576000, 19171152000, 38342304000, 76684608000, 153369216000, 306738432000, 613476864000, 1226953728000, 2453907456000, 4907814912000, 9815629824000, 19631259648000, 39262519296000, 78525038592000 }

  57. {17, 3}

    Returns: {40, 320, 640, 1020, 2040, 4080, 8160, 16320, 32640 }

  58. {21, 20}

    Returns: {328, 1312, 2624, 4305, 8610, 17220, 34440, 68880, 137760, 275520 }

  59. {14, 19, 20, 5, 13, 10, 22, 21, 16, 15, 18, 9, 12, 2}

    Returns: {392, 784, 1568, 6272, 50176, 100352, 200704, 401408, 12845056, 51380224, 102760448, 167747580, 335495160, 670990320, 1341980640, 2683961280, 5367922560, 10735845120, 21471690240, 42943380480, 85886760960, 171773521920, 343547043840, 687094087680, 1374188175360, 2748376350720, 5496752701440, 10993505402880, 21987010805760, 43974021611520, 87948043223040 }

  60. {19, 5, 14, 13, 1}

    Returns: {208, 3328, 6656, 13312, 425984, 449540, 899080, 1798160, 3596320, 7192640, 14385280, 28770560, 57541120, 115082240, 230164480, 460328960, 920657920, 1841315840, 3682631680 }

  61. {1, 10}

    Returns: {44, 55, 110, 220 }

  62. {11, 2, 14, 9, 5}

    Returns: {328, 5248, 10496, 41984, 83968, 142065, 284130, 568260, 1136520, 2273040, 4546080, 9092160, 18184320, 36368640, 72737280, 145474560, 290949120 }

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

    Returns: {504, 1008, 2016, 4032, 129024, 33030144, 66060288, 132120576, 264241152, 1056964608, 2113929216, 3666482820, 7332965640, 14665931280, 29331862560, 58663725120, 117327450240, 234654900480, 469309800960, 938619601920, 1877239203840, 3754478407680, 7508956815360, 15017913630720, 30035827261440, 60071654522880, 120143309045760, 240286618091520, 480573236183040, 961146472366080, 1922292944732160, 3844585889464320, 7689171778928640, 15378343557857280, 30756687115714560 }

  64. {11, 12, 1, 16, 2, 18, 22, 14, 13, 21, 8, 9, 6, 10, 4, 5, 15, 7, 19, 3}

    Returns: {432, 864, 1728, 6912, 55296, 110592, 221184, 442368, 14155776, 56623104, 113246208, 184864680, 369729360, 739458720, 1478917440, 2957834880, 5915669760, 11831339520, 23662679040, 47325358080, 94650716160, 189301432320, 378602864640, 757205729280, 1514411458560, 3028822917120, 6057645834240, 12115291668480, 24230583336960, 48461166673920, 96922333347840 }

  65. {6, 21, 4, 22, 13, 2, 10, 14, 5, 7, 20, 8, 17, 19, 9, 11, 16}

    Returns: {408, 816, 1632, 3264, 104448, 26738688, 53477376, 106954752, 213909504, 855638016, 1711276032, 2968105140, 5936210280, 11872420560, 23744841120, 47489682240, 94979364480, 189958728960, 379917457920, 759834915840, 1519669831680, 3039339663360, 6078679326720, 12157358653440, 24314717306880, 48629434613760, 97258869227520, 194517738455040, 389035476910080, 778070953820160, 1556141907640320, 3112283815280640, 6224567630561280, 12449135261122560, 24898270522245120 }

  66. {10, 19}

    Returns: {58, 116, 232, 464, 1856, 2755, 5510, 11020, 22040, 44080, 88160, 176320 }

  67. {22, 17}

    Returns: {78, 312, 624, 1248, 4992, 7293, 14586, 29172, 58344, 116688, 233376, 466752, 933504 }

  68. {12, 10, 17, 3, 15, 14, 18, 22, 11, 5, 2, 1, 6, 4, 7, 8, 20, 13, 9}

    Returns: {788, 12608, 50432, 100864, 201728, 403456, 1613824, 6455296, 12910592, 25821184, 103284736, 150855705, 301711410, 603422820, 1206845640, 2413691280, 4827382560, 9654765120, 19309530240, 38619060480, 77238120960, 154476241920, 308952483840, 617904967680, 1235809935360, 2471619870720, 4943239741440, 9886479482880, 19772958965760, 39545917931520, 79091835863040 }

  69. {7, 21, 20, 10, 1, 17, 6, 12, 11, 3, 9, 13, 16, 15, 8, 2, 14}

    Returns: {740, 11840, 47360, 94720, 189440, 378880, 1515520, 6062080, 12124160, 24248320, 96993280, 141666525, 283333050, 566666100, 1133332200, 2266664400, 4533328800, 9066657600, 18133315200, 36266630400, 72533260800, 145066521600, 290133043200, 580266086400, 1160532172800, 2321064345600, 4642128691200, 9284257382400, 18568514764800, 37137029529600, 74274059059200 }

  70. {19, 13}

    Returns: {64, 128, 512, 1024, 2048, 4096, 7904, 15808, 31616, 63232, 126464, 252928, 505856, 1011712 }

  71. {18, 21}

    Returns: {78, 156, 312, 624, 1248, 2457, 4914, 9828, 19656, 39312, 78624 }

  72. {6, 7, 18, 2, 16, 3}

    Returns: {104, 208, 416, 832, 1664, 3276, 6552, 13104, 26208, 52416, 104832 }

  73. {4, 6}

    Returns: {20, 30, 60, 120 }

  74. {8, 22}

    Returns: {60, 240, 330, 660, 1320, 2640 }

  75. {1, 5, 17, 3, 14, 11, 18, 7, 12, 13, 22, 15}

    Returns: {552, 8832, 35328, 70656, 141312, 282624, 1130496, 4521984, 9043968, 18087936, 72351744, 105675570, 211351140, 422702280, 845404560, 1690809120, 3381618240, 6763236480, 13526472960, 27052945920, 54105891840, 108211783680, 216423567360, 432847134720, 865694269440, 1731388538880, 3462777077760, 6925554155520, 13851108311040, 27702216622080, 55404433244160 }

  76. {11, 20}

    Returns: {62, 124, 496, 992, 1705, 3410, 6820, 13640, 27280, 54560 }

  77. {22, 13}

    Returns: {70, 140, 280, 4480, 5005, 10010, 20020, 40040, 80080, 160160, 320320, 640640 }

  78. {1, 3}

    Returns: {8, 12, 24 }

  79. {4, 8}

    Returns: {12, 24, 48, 96 }

  80. {3, 18, 12, 15, 6, 2, 7, 16, 19}

    Returns: {3136, 6272, 25088, 50176, 100352, 401408, 586530, 1173060, 2346120, 4692240, 9384480, 18768960, 37537920, 75075840, 150151680, 300303360, 600606720, 1201213440, 2402426880 }

  81. {21, 16, 17, 20, 4, 11, 12, 6, 2, 8, 19, 15, 18, 7, 22, 5, 3, 10, 9}

    Returns: {450, 1800, 3600, 14400, 28800, 57600, 115200, 921600, 14745600, 235929600, 251818875, 503637750, 1007275500, 2014551000, 4029102000, 8058204000, 16116408000, 32232816000, 64465632000, 128931264000, 257862528000, 515725056000, 1031450112000, 2062900224000, 4125800448000, 8251600896000, 16503201792000, 33006403584000, 66012807168000, 132025614336000, 264051228672000 }

  82. {3, 12, 10, 2, 11, 20, 18, 15, 4, 1, 7, 5, 16, 21, 6, 9, 22, 14}

    Returns: {1568, 25088, 50176, 200704, 401408, 679140, 1358280, 2716560, 5433120, 10866240, 21732480, 43464960, 86929920, 173859840, 347719680, 695439360, 1390878720 }

  83. {15, 1, 16, 7, 14, 20, 13, 21, 8, 22, 9, 17, 12, 6, 3, 19, 2, 4, 18, 10}

    Returns: {474, 948, 1896, 3792, 121344, 31064064, 62128128, 124256256, 248512512, 994050048, 1988100096, 3448239795, 6896479590, 13792959180, 27585918360, 55171836720, 110343673440, 220687346880, 441374693760, 882749387520, 1765498775040, 3530997550080, 7061995100160, 14123990200320, 28247980400640, 56495960801280, 112991921602560, 225983843205120, 451967686410240, 903935372820480, 1807870745640960, 3615741491281920, 7231482982563840, 14462965965127680, 28925931930255360 }

  84. {7, 14, 18, 16, 20, 4, 1, 19, 10, 9}

    Returns: {3776, 7552, 30208, 60416, 120832, 483328, 706230, 1412460, 2824920, 5649840, 11299680, 22599360, 45198720, 90397440, 180794880, 361589760, 723179520, 1446359040, 2892718080 }

  85. {11, 14}

    Returns: {100, 200, 1600, 1925, 3850, 7700, 15400, 30800, 61600, 123200 }

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

    Returns: {506, 1012, 2024, 4048, 129536, 33161216, 66322432, 132644864, 265289728, 1061158912, 2122317824, 3681032355, 7362064710, 14724129420, 29448258840, 58896517680, 117793035360, 235586070720, 471172141440, 942344282880, 1884688565760, 3769377131520, 7538754263040, 15077508526080, 30155017052160, 60310034104320, 120620068208640, 241240136417280, 482480272834560, 964960545669120, 1929921091338240, 3859842182676480, 7719684365352960, 15439368730705920, 30878737461411840 }

  87. {18, 9}

    Returns: {216, 243, 486, 972, 1944 }

  88. {11, 7}

    Returns: {72, 144, 1152, 1386, 2772, 5544, 11088, 22176, 44352, 88704 }

  89. {17, 6}

    Returns: {46, 368, 736, 1173, 2346, 4692, 9384, 18768, 37536 }

  90. {1, 14}

    Returns: {30, 60, 105, 210, 420 }

  91. {12, 8, 2, 19, 20, 17, 4, 3, 6, 18, 9, 13, 22, 5}

    Returns: {1264, 5056, 40448, 80896, 161792, 647168, 1294336, 5177344, 10354688, 20709376, 41418752, 82837504, 165675008, 328403790, 656807580, 1313615160, 2627230320, 5254460640, 10508921280, 21017842560, 42035685120, 84071370240, 168142740480, 336285480960, 672570961920, 1345141923840, 2690283847680, 5380567695360, 10761135390720, 21522270781440, 43044541562880, 86089083125760, 172178166251520, 344356332503040 }

  92. {11, 19, 20, 7, 10}

    Returns: {134, 1072, 8576, 68608, 137216, 274432, 490105, 980210, 1960420, 3920840, 7841680, 15683360, 31366720, 62733440, 125466880, 250933760, 501867520, 1003735040, 2007470080 }

  93. {16, 8}

    Returns: {24, 48, 96, 192, 384 }

  94. {4, 17, 22}

    Returns: {86, 344, 688, 1376, 5504, 8041, 16082, 32164, 64328, 128656, 257312, 514624, 1029248 }

  95. {14, 7}

    Returns: {42, 84, 147, 294, 588 }

  96. {3, 7, 19, 22, 9, 13}

    Returns: {146, 2336, 9344, 74752, 149504, 299008, 2392064, 9568256, 12495483, 24990966, 49981932, 99963864, 199927728, 399855456, 799710912, 1599421824, 3198843648, 6397687296, 12795374592, 25590749184, 51181498368, 102362996736, 204725993472, 409451986944, 818903973888, 1637807947776 }

  97. {12, 14}

    Returns: {104, 416, 546, 1092, 2184, 4368, 8736 }

  98. {7, 16, 11, 12, 13, 2, 18, 22, 21}

    Returns: {1952, 3904, 31232, 62464, 999424, 1099098, 2198196, 4396392, 8792784, 17585568, 35171136, 70342272, 140684544, 281369088, 562738176, 1125476352, 2250952704, 4501905408, 9003810816 }

  99. {2, 14}

    Returns: {32, 64, 112, 224, 448 }

  100. {2, 11, 6, 12, 13, 7, 8, 22, 1}

    Returns: {164, 656, 1312, 2624, 10496, 20992, 41984, 167936, 246246, 492492, 984984, 1969968, 3939936, 7879872, 15759744, 31519488, 63038976, 126077952, 252155904, 504311808 }

  101. {4, 3}

    Returns: {14, 21, 42, 84 }

  102. {12, 9}

    Returns: {168, 189, 378, 756, 1512 }

  103. {13, 2, 6, 16, 18, 22, 7, 11, 20}

    Returns: {460, 1840, 3680, 7360, 14720, 29440, 58880, 117760, 235520, 942080, 3768320, 5180175, 10360350, 20720700, 41441400, 82882800, 165765600, 331531200, 663062400, 1326124800, 2652249600, 5304499200, 10608998400, 21217996800, 42435993600, 84871987200, 169743974400 }

  104. {10, 11}

    Returns: {42, 84, 336, 672, 1155, 2310, 4620, 9240, 18480, 36960 }

  105. {6, 4, 8, 18, 3, 14, 22, 15, 17, 7, 13, 21, 11, 9, 1, 12, 5, 10, 20, 16}

    Returns: {928, 14848, 59392, 118784, 237568, 475136, 1900544, 7602176, 15204352, 30408704, 121634816, 177657480, 355314960, 710629920, 1421259840, 2842519680, 5685039360, 11370078720, 22740157440, 45480314880, 90960629760, 181921259520, 363842519040, 727685038080, 1455370076160, 2910740152320, 5821480304640, 11642960609280, 23285921218560, 46571842437120, 93143684874240 }

  106. {18, 4}

    Returns: {176, 198, 396, 792, 1584 }

  107. {6, 21}

    Returns: {108, 432, 567, 1134, 2268, 4536, 9072 }

  108. {19, 5}

    Returns: {48, 96, 192, 384, 1536, 2280, 4560, 9120, 18240, 36480, 72960, 145920 }

  109. {12, 16}

    Returns: {56, 84, 168, 336, 672, 1344 }

  110. {3, 15, 2, 18, 22, 17, 12, 4, 7, 11, 21, 5, 14, 19}

    Returns: {340, 1360, 2720, 10880, 21760, 43520, 87040, 696320, 11141120, 178257920, 190263150, 380526300, 761052600, 1522105200, 3044210400, 6088420800, 12176841600, 24353683200, 48707366400, 97414732800, 194829465600, 389658931200, 779317862400, 1558635724800, 3117271449600, 6234542899200, 12469085798400, 24938171596800, 49876343193600, 99752686387200, 199505372774400 }

  111. {18, 8, 9, 5, 2, 17, 21, 14, 15, 10, 3, 6, 1, 13}

    Returns: {284, 568, 1136, 4544, 9088, 18176, 36352, 72704, 145408, 290816, 9306112, 9885330, 19770660, 39541320, 79082640, 158165280, 316330560, 632661120, 1265322240, 2530644480, 5061288960, 10122577920, 20245155840, 40490311680, 80980623360, 161961246720, 323922493440, 647844986880 }

  112. {6, 13, 15, 18, 2, 10, 22, 19, 3, 8, 20, 16}

    Returns: {1216, 2432, 19456, 38912, 155648, 311296, 622592, 2490368, 4980736, 9961472, 18584280, 37168560, 74337120, 148674240, 297348480, 594696960, 1189393920, 2378787840, 4757575680, 9515151360, 19030302720, 38060605440, 76121210880, 152242421760, 304484843520, 608969687040, 1217939374080 }

  113. {5, 4, 3, 15, 6, 10, 22, 8, 17, 2}

    Returns: {368, 1472, 2944, 5888, 11776, 47104, 188416, 258060, 516120, 1032240, 2064480, 4128960, 8257920, 16515840, 33031680, 66063360, 132126720, 264253440, 528506880 }

  114. {7, 17, 19, 9, 5, 4, 11, 6, 10, 13, 16}

    Returns: {234, 468, 936, 1872, 59904, 15335424, 30670848, 61341696, 122683392, 490733568, 981467136, 1702295595, 3404591190, 6809182380, 13618364760, 27236729520, 54473459040, 108946918080, 217893836160, 435787672320, 871575344640, 1743150689280, 3486301378560, 6972602757120, 13945205514240, 27890411028480, 55780822056960, 111561644113920, 223123288227840, 446246576455680, 892493152911360, 1784986305822720, 3569972611645440, 7139945223290880, 14279890446581760 }

  115. {9, 4}

    Returns: {104, 117, 234, 468, 936 }

  116. {20, 8, 10, 17, 1, 11, 2, 7, 9}

    Returns: {680, 1360, 43520, 87040, 696320, 1392640, 2785280, 5006925, 10013850, 20027700, 40055400, 80110800, 160221600, 320443200, 640886400, 1281772800, 2563545600, 5127091200, 10254182400, 20508364800, 41016729600, 82033459200, 164066918400 }

  117. {8, 20}

    Returns: {112, 140, 280, 560, 1120 }

  118. {7, 10}

    Returns: {34, 544, 595, 1190, 2380, 4760, 9520, 19040 }

  119. {13, 15, 1, 12, 20, 2, 9, 17, 4, 6, 19, 22, 21, 5, 11}

    Returns: {354, 708, 1416, 2832, 90624, 23199744, 46399488, 92798976, 185597952, 742391808, 1484783616, 2575267695, 5150535390, 10301070780, 20602141560, 41204283120, 82408566240, 164817132480, 329634264960, 659268529920, 1318537059840, 2637074119680, 5274148239360, 10548296478720, 21096592957440, 42193185914880, 84386371829760, 168772743659520, 337545487319040, 675090974638080, 1350181949276160, 2700363898552320, 5400727797104640, 10801455594209280, 21602911188418560 }

  120. {21, 10, 16, 2, 12, 17, 11, 14, 5, 9, 6, 19, 18, 15, 20, 22, 7, 1}

    Returns: {450, 1800, 3600, 14400, 28800, 57600, 115200, 921600, 14745600, 235929600, 251818875, 503637750, 1007275500, 2014551000, 4029102000, 8058204000, 16116408000, 32232816000, 64465632000, 128931264000, 257862528000, 515725056000, 1031450112000, 2062900224000, 4125800448000, 8251600896000, 16503201792000, 33006403584000, 66012807168000, 132025614336000, 264051228672000 }

  121. {17, 19}

    Returns: {72, 2304, 9216, 11628, 23256, 46512, 93024, 186048, 372096, 744192, 1488384, 2976768 }

  122. {17, 18, 14, 10, 22, 19, 1, 9, 21, 12, 11, 6, 8}

    Returns: {336, 1344, 2688, 10752, 21504, 43008, 86016, 688128, 11010048, 176160768, 188024760, 376049520, 752099040, 1504198080, 3008396160, 6016792320, 12033584640, 24067169280, 48134338560, 96268677120, 192537354240, 385074708480, 770149416960, 1540298833920, 3080597667840, 6161195335680, 12322390671360, 24644781342720, 49289562685440, 98579125370880, 197158250741760 }

  123. {1, 13}

    Returns: {56, 112, 182, 364, 728, 1456 }

  124. {4, 14}

    Returns: {36, 72, 126, 252, 504 }

  125. {5, 15}

    Returns: {40, 80, 160, 300, 600, 1200, 2400 }

  126. {7, 16, 6, 3, 9}

    Returns: {82, 164, 328, 656, 1312, 2583, 5166, 10332, 20664, 41328, 82656 }

  127. {8, 17}

    Returns: {400, 425, 850, 1700, 3400, 6800 }

  128. {21, 22}

    Returns: {86, 172, 1376, 2752, 5504, 9933, 19866, 39732, 79464, 158928, 317856, 635712, 1271424 }

  129. {13, 6, 2, 16, 17, 22, 20, 12, 10, 9, 8, 3, 7, 4}

    Returns: {596, 9536, 38144, 76288, 152576, 305152, 1220608, 4882432, 9764864, 19529728, 78118912, 114098985, 228197970, 456395940, 912791880, 1825583760, 3651167520, 7302335040, 14604670080, 29209340160, 58418680320, 116837360640, 233674721280, 467349442560, 934698885120, 1869397770240, 3738795540480, 7477591080960, 14955182161920, 29910364323840, 59820728647680 }

  130. {2, 8, 19, 14, 16, 1, 17, 13, 9, 12, 7}

    Returns: {944, 1888, 7552, 30208, 241664, 30932992, 31215366, 62430732, 124861464, 249722928, 499445856, 998891712, 1997783424, 3995566848, 7991133696, 15982267392, 31964534784, 63929069568, 127858139136, 255716278272, 511432556544, 1022865113088, 2045730226176, 4091460452352, 8182920904704 }

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

    Returns: {506, 1012, 2024, 4048, 129536, 33161216, 66322432, 132644864, 265289728, 1061158912, 2122317824, 3681032355, 7362064710, 14724129420, 29448258840, 58896517680, 117793035360, 235586070720, 471172141440, 942344282880, 1884688565760, 3769377131520, 7538754263040, 15077508526080, 30155017052160, 60310034104320, 120620068208640, 241240136417280, 482480272834560, 964960545669120, 1929921091338240, 3859842182676480, 7719684365352960, 15439368730705920, 30878737461411840 }

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

    Returns: {484, 968, 1936, 3872, 123904, 31719424, 63438848, 126877696, 253755392, 1015021568, 2030043136, 3520987470, 7041974940, 14083949880, 28167899760, 56335799520, 112671599040, 225343198080, 450686396160, 901372792320, 1802745584640, 3605491169280, 7210982338560, 14421964677120, 28843929354240, 57687858708480, 115375717416960, 230751434833920, 461502869667840, 923005739335680, 1846011478671360, 3692022957342720, 7384045914685440, 14768091829370880, 29536183658741760 }

  133. {1 }

    Returns: {2, 3 }

  134. {1, 4, 5, 6, 7, 9, 10, 13, 16 }

    Returns: {142, 284, 568, 1136, 2272, 4544, 9088, 18176, 36352, 72704, 145408, 290745, 581490, 1162980, 2325960, 4651920, 9303840, 18607680, 37215360, 74430720, 148861440, 297722880, 595445760 }

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: