Problem Statement
Mary has a collection of N stones. The stones are numbered from 0 to N-1.
For each i, the weight W[i] of stone number i is a positive integer.
For each i, stone number i weighs more than all stones with smaller numbers together.
Mary sometimes uses her collection of stones when weighing an object on balance scales: she places the object onto one plate, some stones on the other plate, and if the two plates are in a balance, she knows that the object weighs the same as the collection of stones.
Of course, not all objects can be weighed using the above method: sometimes there is no combination of stones that weighs the same as the object.
A weight x >= 0 is called admissible if we can balance an object of weight x with some (possibly empty) collection of Mary's stones.
For example, if Mary's stones have weights 4 and 7, the admissible weights are 0, 4, 7, and 11.
Consider the strictly increasing sequence of all distinct admissible weights. Return the element at (1-based) index K in this sequence, or -1 if no such element exists.
Definition
- Class:
- SpecialWeights
- Method:
- solve
- Parameters:
- int, long[], long
- Returns:
- long
- Method signature:
- long solve(int N, long[] W, long K)
- (be sure your method is public)
Notes
- As 0 is the weight of an empty collection of stones, the weight 0 is always the smallest admissible weight.
- The answer always fits into a signed 64-bit integer variable. (Note that the largest possible answer is the sum of all weights given in the input.)
Constraints
- N will be between 1 and 50, inclusive.
- W will have exactly N elements.
- All elements of W will be positive.
- For each i, W[i] will be greater than the sum of all W[j] where j < i.
- The sum of W will not exceed 10^18.
- K will be between 1 and 10^18, inclusive.
Examples
2
{4, 7}
1
Returns: 0
As we already mentioned above, for these stones the sequence of admissible weights is {0, 4, 7, 11}. As K = 1, we want the first (i.e., smallest) one.
2
{4, 7}
4
Returns: 11
This time we return the largest admissible weight: 11.
2
{4, 7}
5
Returns: -1
There are only four distinct admissible weights. Thus, there is no admissible weight with index 5 and therefore we have to return -1.
5
{1, 3, 7, 13, 30}
10
Returns: 14
Sorted list of all distinct admissible weights for these stones: 0, 1, 3, 4, 7, 8, 10, 11, 13, 14, 16, 17, 20, 21, 23, 24, 30, 31, 33, 34, 37, 38, 40, 41, 43, 44, 46, 47, 50, 51, 53, 54. On (1-based) position 10 in this list we see the number 14, so that is the correct return value.
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
1
Returns: 0
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
16
Returns: 40
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
17
Returns: 81
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
274877906944
Returns: 675425858836496044
50
{4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248}
1125899906842624
Returns: 4503599627370492
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
274877906945
Returns: -1
38
{1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987, 22876792454961, 68630377364883, 205891132094649, 617673396283947, 1853020188851841, 5559060566555523, 16677181699666569, 50031545098999707, 150094635296999121, 450283905890997363}
174877906945
Returns: 501028398489270717
50
{4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248}
125899906842624
Returns: 503599627370492
47
{18, 35, 73, 152, 344, 1144, 2650, 4417, 9291, 27213, 45348, 111559, 206297, 502526, 956636, 1905059, 4640512, 12619945, 22084900, 45274043, 108722367, 201056821, 406134788, 804306150, 1978593130, 4412262686, 14399042603, 22398510728, 80634638597, 188147490064, 319850733114, 950144824821, 2850434474481, 5453831294504, 14831760715539, 44495282146613, 124586790010534, 203491757017199, 488670919351311, 885964349718228, 1860525134408282, 6538416900920523, 10679414271503526, 37530513011283808, 71808381561589680, 195283769368713408, 358020243842641280}
124941239459541
Returns: 628068037126974968
50
{1, 2, 4, 14, 23, 55, 150, 375, 1125, 2152, 3980, 8670, 16883, 34103, 67538, 202614, 415358, 753048, 1656705, 4744201, 8697702, 17434939, 35741625, 71176893, 211437241, 359443310, 875561615, 1952502402, 5309854093, 9026751958, 21988105799, 59796921868, 122583689829, 333367839414, 611174372259, 1166787437949, 2450253619692, 5884109049575, 10881296296068, 26505557624716, 59107393503117, 131809487511951, 250920256105067, 489891928586084, 1077762242889384, 2160423405064629, 5188102491305203, 9406071996431384, 20693358392149048, 71109904293021272}
149052400379667
Returns: 9876746226012133
48
{9, 24, 59, 136, 298, 658, 1478, 3275, 7311, 16307, 36363, 81098, 180833, 403259, 899286, 2005404, 4472046, 9972660, 22239028, 49593028, 110592469, 246621197, 549965271, 1226422556, 2734922290, 6098876705, 13600495066, 30329103982, 67633901901, 150823601218, 336336630725, 750030686514, 1672568430927, 3729827600970, 8317515550170, 18548059676863, 41362173079425, 92237645967096, 205689950506640, 458688589629808, 1022875554874472, 2281012487370066, 5086657846835241, 11343246998442588, 25295440806526984, 56408832998555176, 125791697586778016, 280515485618515008}
12986068944384
Returns: 15344581646410760
36
{68, 192, 522, 1472, 4102, 11446, 32065, 89769, 251393, 703879, 1970856, 5518422, 15451551, 43264335, 121140174, 339192487, 949738973, 2659269114, 7445953490, 20848669804, 58376275416, 163453571202, 457669999382, 1281475998226, 3588132795069, 10046771826188, 28130961113285, 78766691117248, 220546735128271, 617530858359145, 1729086403405629, 4841441929535724, 13556037402700076, 37956904727560176, 106279333237168528, 297582133064071872}
28536057233
Returns: 149725245653336005
42
{30, 57, 136, 352, 886, 2238, 5587, 13953, 34894, 87210, 218022, 545058, 1362652, 3406627, 8516569, 21291423, 53228550, 133071405, 332678508, 831696276, 2079240672, 5198101692, 12995254204, 32488135533, 81220338805, 203050847022, 507627117550, 1269067793898, 3172669484755, 7931673711880, 19829184279708, 49572960699271, 123932401748175, 309831004370445, 774577510926084, 1936443777315196, 4841109443288026, 12102773608220068, 30256934020550136, 75642335051375360, 189105837628438368, 472764594071095936}
1050190021177
Returns: 123667817832288053
50
{9, 16, 36, 75, 144, 292, 1056, 2008, 3647, 8975, 24388, 42684, 85005, 171707, 357047, 711038, 1731997, 5652244, 15826271, 30280939, 57644564, 112544149, 405158936, 661759602, 1421207517, 2713214358, 6674507320, 18151404058, 33277574094, 66706409892, 130236324082, 260472648157, 531364202246, 1157540448414, 2718115434771, 5174363650837, 18184192258653, 42429781936851, 77787933550902, 267307626202169, 415811862981158, 873204912260425, 1738925210987191, 3512628926194138, 7652021052944478, 26295126891027380, 42948707255344720, 83852237974720650, 206276505417812800, 373980981367254095}
1060622299516471
Returns: 709107819014039330
50
{12, 24, 46, 104, 211, 438, 924, 1936, 4068, 8554, 17958, 37713, 79187, 166302, 349225, 733386, 1540101, 3234213, 6791854, 14262891, 29952062, 62899335, 132088611, 277386071, 582510757, 1223272589, 2568872442, 5394632128, 11328727461, 23790327671, 49959688103, 104915345022, 220322224542, 462676671536, 971621010235, 2040404121494, 4284848655131, 8998182175780, 18896182569130, 39681983395179, 83332165129876, 174997546772739, 367494848222758, 771739181267782, 1620652280662352, 3403369789390940, 7147076557720969, 15008860771214038, 31518607619549476, 66189076001053912}
89219678118860
Returns: 8861264371464159
48
{57, 63, 129, 283, 973, 1874, 4189, 9348, 20853, 67987, 107906, 262816, 486015, 981762, 2391471, 7804364, 13354121, 28043664, 65851601, 119389504, 429802221, 735439350, 1474221603, 3540237874, 11553264086, 19768918552, 37740662700, 79255391644, 170210388739, 324947105756, 799369880154, 1521727296265, 4456487081941, 13369461245775, 20796939715657, 43673573402873, 104878966986032, 342263555676412, 585650973046298, 1140422167513788, 2371407271859558, 5092879426707893, 9917225210916648, 24157193881415204, 45987048352303816, 98762660985185856, 197974243156668000, 475421003923369856}
115936379340851
Returns: 324304380814476655
47
{26, 68, 146, 376, 1132, 1927, 4065, 9563, 17320, 34632, 124718, 291016, 727504, 1273158, 2734224, 5480906, 11235828, 24130296, 69100410, 117470680, 244269935, 715361926, 1466491926, 4785771279, 7593423741, 16541752505, 56843476767, 90191649834, 182187132643, 378842066997, 739644035567, 1508873832540, 5378691426611, 10291229596244, 19031244585072, 41458260262745, 87062346551761, 249314901489189, 423835332531589, 923296185181574, 1797909480599036, 6409018501429480, 9969584335556970, 29908753006670952, 74771882516677344, 153282359159188544, 341819660924990464}
33427351784464
Returns: 121764438601837769
50
{1, 2, 9, 18, 37, 75, 159, 337, 708, 1485, 3119, 6546, 13750, 28872, 60635, 127331, 267396, 561530, 1179217, 2476356, 5200344, 10920726, 22933523, 48160395, 101136830, 212387342, 446013423, 936628188, 1966919194, 4130530309, 8674113646, 18215638656, 38252841180, 80330966478, 168695029604, 354259562169, 743945080552, 1562284669158, 3280797805236, 6889675390994, 14468318321084, 30383468474279, 63805283795986, 133991095971572, 281381301540302, 590900733234632, 1240891539792730, 2605872233564730, 5472331690485933, 11491896550020458}
575178049484828
Returns: 11672127225516000
50
{19, 36, 82, 164, 330, 701, 1400, 2869, 5901, 12114, 24832, 50901, 104320, 213858, 438412, 898763, 1842449, 3777011, 7742900, 15872950, 32539550, 66706076, 136747456, 280332288, 574681162, 1178096388, 2415097600, 4950950096, 10149447693, 20806367755, 42653053897, 87438760507, 179249459019, 367461390991, 753295851530, 1544256495630, 3165725816062, 6489737922903, 13303962741983, 27273123621042, 55909903423129, 114615302017425, 234961369135715, 481670806728229, 987425153792856, 2024221565275356, 4149654208814472, 8506791128069698, 17438921812542888, 35749789715712916}
231200725990652
Returns: 13773016117801594
49
{6, 21, 32, 69, 177, 381, 1243, 1985, 7059, 13509, 25721, 90367, 147605, 432264, 792489, 1588591, 3163564, 6265095, 18795279, 34458021, 67099153, 135540285, 273791385, 666923606, 1813706875, 4534267186, 11335667956, 19837418928, 38730198870, 85206437505, 165920171941, 591456612929, 938444492505, 2285940378512, 7459971284032, 12184619763913, 29260494033045, 95489124429805, 148538638001912, 365405049484715, 814853260350920, 1625069144423407, 3412645203289164, 9772574900328068, 16613377330557714, 40468232662258520, 110053852240044528, 225610397092091264, 429485158366773760}
490224896072439
Returns: 726736104110899374
50
{4, 5, 18, 50, 149, 258, 512, 1047, 3066, 5214, 12704, 24180, 70822, 123935, 435546, 691061, 2463436, 4215212, 12070831, 24745207, 45760529, 95154979, 228507887, 745715979, 1183202689, 2390069431, 5206602228, 10436870833, 20784282775, 61741545886, 104960628005, 207863204483, 511343483025, 1668725805589, 4672432255644, 7268227953221, 21804683859673, 37067962561439, 73409102327556, 161500025120626, 323734141264525, 632052371040265, 1327309979184557, 2591414721265083, 5441970914656678, 13068504439339820, 29142764899727796, 53892791090179552, 131276498767313840, 428409647196746112}
512378061021057
Returns: 220386715408596367
37
{28, 93, 268, 754, 2129, 5895, 16549, 46315, 129659, 363114, 1016656, 2846651, 7970623, 22317723, 62489680, 174971048, 489918997, 1371773183, 3840964893, 10754701741, 30113164872, 84316861612, 236087212496, 661044194969, 1850923745931, 5182586488639, 14511242168184, 40631478070910, 113768138598548, 318550788075936, 891942206612574, 2497438178515267, 6992826899842750, 19579915319559648, 54823762894767080, 153506536105347840, 429818301094973888}
60871365524316380
Returns: -1
42
{18, 63, 177, 441, 1062, 2652, 6655, 16608, 41532, 103839, 259578, 648990, 1622446, 4056136, 10140346, 25350840, 63377109, 158442763, 396106936, 990267339, 2475668340, 6189170850, 15472927116, 38682317775, 96705794427, 241764486094, 604411215219, 1511028038077, 3777570095197, 9443925237973, 23609813094951, 59024532737341, 147561331843359, 368903329608420, 922258324021009, 2305645810052565, 5764114525131387, 14410286312828502, 36025715782071248, 90064289455178112, 225160723637945280, 562901809094863232}
3942132640171
Returns: 885048798844457208
49
{8, 19, 41, 97, 206, 464, 1028, 2292, 5122, 11413, 25458, 56773, 126603, 282316, 629570, 1403944, 3130787, 6981666, 15569109, 34719107, 77423620, 172654670, 385019907, 858594397, 1914665500, 4269704065, 9521440077, 21232811363, 47349169339, 105588647634, 235462684216, 525081785808, 1170932382343, 2611179212635, 5822929644177, 12985133106504, 28956846827511, 64573768425341, 143999503588520, 321118893002395, 716095131395341, 1596892143011608, 3561069478915890, 7941184937982441, 17708842411700840, 39490718578092864, 88064302429147104, 196383394416998048, 437934969549905600}
21330418615850
Returns: 20239178141528097
43
{9, 15, 39, 105, 262, 648, 1620, 4053, 10128, 25326, 63316, 158283, 395710, 989280, 2473200, 6182995, 15457486, 38643718, 96609295, 241523239, 603808092, 1509520237, 3773800591, 9434501478, 23586253695, 58965634240, 147414085593, 368535213984, 921338034957, 2303345087392, 5758362718480, 14395906796203, 35989766990509, 89974417476271, 224936043690678, 562340109226701, 1405850273066749, 3514625682666874, 8786564206667184, 21966410516667964, 54916026291669904, 137290065729174768, 343225164322936896}
7345509090391
Returns: 506879340158110020
50
{3, 24, 33, 80, 154, 320, 927, 1901, 4252, 8484, 16994, 34862, 71458, 153450, 322242, 756693, 1509072, 2880960, 5761937, 11754325, 23278180, 47487509, 103448262, 355485875, 564037577, 1117015597, 2234031190, 4691465489, 11266219257, 21447034474, 75371006867, 123105977876, 240349766348, 504734509308, 1083977446197, 2545376130476, 6922181427996, 14190471927394, 26241989793554, 54567902305981, 117191066380951, 275185931329097, 523860047322815, 1534161567159673, 4602484701479050, 7159420646745170, 14318841293490359, 30069566716329748, 105673048745958816, 180818327854196224}
127006179003389
Returns: 26528424312216225
36
{68, 181, 486, 1339, 3747, 10504, 29406, 82387, 230634, 645768, 1808173, 5062849, 14176056, 39692939, 111140188, 311192506, 871339075, 2439749386, 6831298312, 19127635284, 53557378785, 149960660574, 419889849593, 1175691578857, 3291936420855, 9217421978360, 25808781539442, 72264588310436, 202340847269167, 566554372353684, 1586352242590277, 4441786279252790, 12437001581907836, 34823604429341916, 97506092402157360, 273017058726040640}
60852610132
Returns: 405998157474490909
50
{6, 10, 25, 69, 123, 234, 495, 985, 1949, 4797, 9129, 17824, 36363, 75614, 162389, 341017, 651031, 1328103, 2761676, 9705319, 15852018, 46423765, 139271295, 220977122, 446373786, 883995147, 1803350097, 4392748679, 7964089070, 23892267210, 41811467618, 146937443340, 251426291939, 489595561210, 1192597187633, 2162188397089, 4410864330063, 15723434023633, 26904542662662, 51363217810535, 126353515813919, 233661550463690, 832934703417624, 1360460015582122, 3984204331347640, 9960510828369104, 18260936518676688, 62751218218725352, 97613006118017213, 204987312847836160}
999552523916741
Returns: 367677454424528559
49
{7, 18, 32, 63, 161, 289, 572, 1205, 3526, 6167, 12646, 25183, 50872, 102762, 366307, 854718, 1453028, 3539406, 7058664, 14149415, 30387553, 104422683, 199795394, 652015209, 1115670479, 2619797132, 5224684846, 10473118261, 20856466939, 61955975319, 127009749397, 253296679086, 870419497231, 1353985884576, 4874349184471, 9326254772953, 30435436307840, 48290892275102, 95634904309520, 286904712928558, 588154661503540, 1172962101356244, 2351255848627747, 4682358075695830, 13909357813096440, 28514183516847696, 51696446538675094, 155089339616025280, 317933146212851776}
517356774870199
Returns: 542448995883483915
48
{14, 37, 57, 152, 299, 690, 2260, 4356, 14200, 33138, 57987, 118860, 255294, 731029, 1498647, 3341946, 6361934, 12420939, 27326049, 64166551, 127967926, 439744323, 1026070075, 2103443667, 5720340646, 10010596149, 21498946966, 73878199608, 172382465736, 293050191738, 1044637742338, 1787491248005, 3412483291635, 7507463241583, 17628888684570, 47941977764142, 143825933292444, 275186952366187, 898049127477929, 1718267330574436, 3115232639984551, 6541988543967570, 14049699206330336, 27358596090872380, 66642321419001464, 123239531950943680, 244062602491084558, 497887709081812480}
28228639437044
Returns: 99176790801473178
49
{8, 21, 61, 113, 237, 813, 1281, 2537, 5075, 10351, 25227, 68602, 116619, 346431, 635121, 1212510, 2982762, 5515937, 13436170, 24359887, 51155753, 104869301, 225219313, 472960550, 920983181, 1860386023, 4531681488, 8380294890, 29873286495, 51116512438, 120030865125, 267668829217, 727928645320, 1237478697039, 2450693105897, 8822495181243, 16880374113447, 45906383259730, 78040851541547, 154551490307771, 340013278677094, 662098584478486, 1311214843771120, 2674878281293079, 7945961953252977, 14567596914297118, 34207366208754060, 111632819481251072, 213590794607460352}
189016296113717
Returns: 130165124914307930
50
{21, 49, 79, 176, 374, 772, 1566, 3224, 6597, 13514, 27732, 56811, 116494, 238810, 489567, 1003604, 2057402, 4217675, 8646197, 17724711, 36335677, 74488124, 152700660, 313036349, 641724507, 1315535239, 2696847239, 5528536861, 11333500573, 23233676145, 47629036113, 97639524027, 200161024259, 410330099713, 841176704405, 1724412244042, 3535045100284, 7246842455616, 14856027033976, 30454855419660, 62432453610288, 127986529901093, 262372386297265, 537863391909378, 1102619953414251, 2260370904499184, 4633760354223356, 9499208726157848, 19473377888623604, 39920424671678408}
904355968154006
Returns: 63177958283690291
49
{10, 28, 49, 92, 223, 420, 878, 2559, 6414, 11755, 22434, 67320, 112187, 246816, 848158, 1451296, 3047721, 7156600, 15959210, 35589040, 65813688, 160314389, 290651298, 639432851, 1245150157, 3698828392, 6288008267, 22414900064, 36611003444, 107217938661, 187631392644, 402960752786, 1384719677733, 3231012581403, 5385020968988, 16155062906965, 33117878959281, 60042983804225, 147705740158393, 482025073980342, 764813117382125, 1862994775929052, 3546505908811294, 7616543642256619, 14540674226126288, 35770058596270668, 79767230669683600, 151849569604117184, 302397571468770496}
560826448197956
Returns: 597386098862166656
50
{12, 13, 36, 64, 162, 308, 627, 2208, 3781, 8874, 16897, 34638, 83178, 271449, 519371, 1035780, 2016950, 4913055, 9085553, 18892605, 66394024, 108443566, 222309309, 477435710, 1640642715, 3139096393, 5805031424, 11496238707, 23452326965, 83600647882, 130045452264, 286099994976, 819286349254, 1365477248756, 4096431746269, 7510124868155, 15054386667531, 29391897779466, 59959471470106, 124680430380490, 243423697409531, 598822295627445, 1628504535669756, 4071261339174393, 8346085745307501, 22697281965897228, 46529428030089312, 92794054437243168, 265728428615741824, 544743278662270656}
348290341121056
Returns: 302660682907632739
37
{28, 73, 207, 577, 1603, 4507, 12607, 35305, 98856, 276784, 774988, 2169966, 6075928, 17012575, 47635230, 133378635, 373460178, 1045688486, 2927927777, 8198197765, 22954953760, 64273870526, 179966837471, 503907144919, 1410940005771, 3950632016164, 11061769645245, 30972955006677, 86724274018710, 242827967252376, 679918308306678, 1903771263258676, 5330559537124305, 14925566703948042, 41791586771054544, 117016442958952720, 327646040285067648}
107236100661
Returns: 447592835576347400
50
{9, 32, 55, 110, 233, 455, 913, 1847, 3738, 7564, 15269, 30859, 62333, 125904, 254339, 513748, 1037767, 2096310, 4234525, 8553742, 17278572, 34902698, 70503472, 142417007, 287682345, 581118349, 1173859046, 2371195290, 4789814489, 9675425242, 19544359018, 39479605198, 79748802496, 161092581037, 325407013693, 657322167668, 1327790778705, 2682137372974, 5417917493414, 10944193336687, 22107270540117, 44656686491017, 90206506711881, 182217143557994, 368078629987138, 743518832574024, 1501908041799517, 3033854244435027, 6128385573758750, 12379338858992694}
899357187827912
Returns: 19662277918678293
41
{43, 78, 201, 502, 1275, 3174, 7942, 19861, 49656, 124107, 310279, 775693, 1939225, 4848067, 12120196, 30300456, 75751140, 189377853, 473444659, 1183611654, 2959029111, 7397572798, 18493931961, 46234829911, 115587074785, 288967686943, 722419217395, 1806048043449, 4515120108622, 11287800271581, 28219500678963, 70548751697379, 176371879243453, 440929698108661, 1102324245271626, 2755810613179087, 6889526532947702, 17223816332369238, 43059540830923120, 107648852077307776, 269122130193269440}
1760643749130
Returns: 386705612499713887
50
{1, 5, 8, 22, 39, 85, 246, 427, 1255, 2300, 4391, 8783, 21604, 48179, 87347, 192162, 374193, 911491, 1685592, 5007201, 8512241, 17700453, 42506373, 138715923, 226569339, 442349661, 928934289, 1994996973, 4189493644, 9837692801, 26753725548, 66884313868, 122621242090, 351142647802, 877856619507, 1609403802428, 4608747252409, 8065307691715, 15746553112398, 31493106224794, 77473041312993, 154505179138841, 362806252468752, 986656028055264, 1677315247693946, 3388176800341773, 6709918761461157, 13688234273380762, 33342928309452784, 61660020107870984}
730072996486005
Returns: 77683263088700846
48
{15, 28, 70, 167, 367, 813, 1803, 4041, 8993, 20052, 44737, 99737, 222418, 496012, 1106082, 2466587, 5500466, 12266050, 27353304, 60997874, 136025235, 303336295, 676439923, 1508461023, 3363868090, 7501425831, 16728179609, 37303840519, 83187564381, 185508268572, 413683438915, 922514068755, 2057206373332, 4587570212529, 10230281573936, 22813527909884, 50874167239039, 113449392943073, 252992146263026, 564172486166548, 1258104644151413, 2805573356457645, 6256428584900546, 13951835744328230, 31112593709851956, 69381083972969872, 154719817259722784, 345025192489181824}
192048356585667
Returns: 438126390021006074
43
{6, 10, 48, 120, 303, 739, 1867, 4656, 11643, 29115, 72772, 181941, 454857, 1137142, 2842833, 7107079, 17767708, 44419264, 111048174, 277620442, 694051086, 1735127725, 4337819310, 10844548285, 27111370708, 67778426757, 169446066886, 423615167220, 1059037918057, 2647594795155, 6618986987865, 16547467469664, 41368668674158, 103421671685419, 258554179213536, 646385448033847, 1615963620084619, 4039909050211540, 10099772625528856, 25249431563822128, 63123578909555328, 157808947273888320, 394522368184720768}
4180997653532
Returns: 257238618451089965
48
{17, 47, 91, 214, 484, 1075, 2403, 5365, 11944, 26651, 59405, 132501, 295444, 658864, 1469262, 3276435, 7306449, 16293401, 36334287, 81025448, 180686767, 402931466, 898537197, 2003737918, 4468335564, 9964388318, 22220585956, 49551906666, 110500751873, 246416676691, 549509189004, 1225405491475, 2732654245989, 6093818968556, 13589216299896, 30303952348767, 67577813737762, 150698524635194, 336057709936481, 749408693158334, 1671181385743120, 3726734490207158, 8310617913161931, 18532677946351120, 41327871820363016, 92161154159409520, 205519373775483200, 458308203519327552}
649537095064773617
Returns: -1
50
{2, 3, 6, 14, 30, 59, 118, 240, 485, 980, 1978, 3994, 8069, 16302, 32930, 66517, 134364, 271416, 548260, 1107485, 2237118, 4518978, 9128338, 18439243, 37247271, 75239488, 151983766, 307007206, 620154558, 1252712205, 2530478653, 5111566881, 10325365099, 20857237501, 42131619752, 85105871900, 171913861235, 347265999693, 701477319382, 1416984185154, 2862308054007, 5781862269098, 11679361783578, 23592310802827, 47656467821711, 96266064999855, 194457451299707, 392804051625410, 793464184283324, 1602797652252317}
303510074579776
Returns: 852910462075629
50
{36, 40, 110, 222, 454, 910, 1810, 3689, 7442, 15026, 30336, 61280, 123789, 250082, 505167, 1020423, 2061262, 4163749, 8410771, 16989732, 34319271, 69324934, 140036378, 282873479, 571404420, 1154236931, 2331558612, 4709748365, 9513691727, 19217657261, 38819667691, 78415728720, 158399772005, 319967539480, 646334429739, 1305595548062, 2637303007087, 5327352074311, 10761251190125, 21737727404052, 43910209356188, 88698622899504, 179171218256985, 361925860879101, 731090238975781, 1476802282731087, 2983140611116796, 6025944034455918, 12172406949600968, 24588262038193940}
71658220672966
Returns: 3034365141528059
49
{4, 23, 45, 76, 156, 483, 827, 1676, 3372, 7021, 24665, 69040, 193311, 300728, 601439, 1263021, 2465909, 4931828, 10850004, 22785009, 78297584, 127886035, 249682281, 898856204, 2516797357, 4815472274, 8905100187, 19399149650, 66662532396, 103697272611, 207394545245, 435528544986, 1045890691621, 2332336242334, 5201109820379, 10372619828760, 21782501640400, 62377163788435, 109160036629753, 223778075091008, 655350077052234, 1638375192630601, 3358669144892704, 6698223912538062, 12787518378481739, 31457295211065116, 62735565164831464, 119767897132860068, 263489373692292160}
66899487027304
Returns: 54667007427743712
50
{17, 39, 68, 159, 303, 603, 1206, 2528, 4927, 12131, 23096, 67632, 169068, 295878, 589211, 1225218, 2439940, 4832038, 14496112, 26576209, 62405768, 124456373, 292246201, 794767090, 1986917743, 4967294347, 8278823918, 18213412616, 36509613473, 72706287393, 151186309374, 531311887240, 1487673284279, 3471237663300, 6363935716052, 14943678140523, 27093009962074, 81279029886229, 138174350806587, 279112188629315, 552751589246289, 1105503178492575, 2255226484124861, 4555557497932219, 9202226145823076, 18224016484865300, 37176993629125224, 75097527130832960, 151697004804282592, 369516056996784832}
933608753460283
Returns: 568194097596133261
49
{9, 22, 35, 71, 175, 355, 1002, 1675, 3512, 6864, 14410, 30952, 60267, 179038, 367029, 998137, 1696833, 3528414, 10333215, 17222025, 36166246, 74140805, 178043844, 484192404, 847336719, 1819756477, 3474080538, 7642977192, 14882961032, 32421509233, 61895608542, 152263197010, 496897945371, 950731402133, 1758157436829, 3655933258348, 7137774456773, 21413323370308, 64239970110930, 122912476145583, 245125450394403, 477326104313456, 964198730713181, 2100440764357540, 4410925605150843, 15157544352245624, 35367603488573112, 72503587151574880, 236609267338554144}
533679717374615510
Returns: -1
48
{23, 25, 111, 173, 357, 1261, 2151, 4526, 10619, 19644, 47843, 95421, 185810, 452601, 1230850, 2256564, 4523395, 9272947, 19914756, 39920035, 116908680, 239662796, 534448038, 988337809, 1996442370, 3953738822, 14233459741, 27233352968, 51843004863, 103241641104, 251484491666, 501537770775, 1723466157741, 4825705241694, 8257317858016, 23645955684319, 40198124663333, 143294491446931, 274170126968476, 611399383139707, 1130641493406144, 2463024900341618, 4796181215028877, 11682933183196802, 26052940998528856, 49595903535004336, 106513107115652176, 366017768088332032}
102341952083228
Returns: 150224584318422143
50
{34, 75, 138, 257, 545, 1084, 2156, 4317, 8637, 17255, 34525, 69038, 138097, 276163, 552359, 1104697, 2209401, 4418796, 8837609, 17675208, 35350423, 70700844, 141401674, 282803356, 565606702, 1131213415, 2262426837, 4524853667, 9049707349, 18099414697, 36198829375, 72397658745, 144795317503, 289590634993, 579181269985, 1158362539992, 2316725079954, 4633450159915, 9266900319822, 18533800639658, 37067601279326, 74135202558634, 148270405117282, 296540810234563, 593081620469131, 1186163240938256, 2372326481876525, 4744652963753019, 9489305927506065, 18978611855012139}
1082268465976506
Returns: 36486286238868178
42
{28, 48, 148, 397, 996, 2466, 6183, 15447, 38598, 96499, 241233, 603084, 1507729, 3769294, 9423238, 23558149, 58895338, 147238378, 368095899, 920239729, 2300599332, 5751498330, 14378745859, 35946864604, 89867161513, 224667903786, 561669759478, 1404174398701, 3510435996771, 8776089991908, 21940224979764, 54850562449441, 137126406123621, 342816015309021, 857040038272573, 2142600095681440, 5356500239203545, 13391250598008878, 33478126495022208, 83695316237555488, 209238290593888768, 523095726484721856}
509068411620
Returns: 53481423510047160
49
{8, 11, 24, 54, 126, 248, 486, 962, 2112, 4038, 8073, 29068, 46119, 137004, 251168, 479506, 1054908, 3625057, 5751755, 11390732, 28021203, 55882935, 112019881, 393669874, 642994123, 1255369481, 4519330129, 10545103629, 21617462444, 43111898680, 148148160913, 230452694759, 566913629107, 1264217392905, 2406638232103, 7048011965443, 14448424529159, 26719013360998, 55559830724193, 195253119402165, 373584301789472, 690857603943357, 1395532359965585, 2901886407340201, 8498381621496302, 14872167837618530, 43554205810168552, 130662617430505648, 365855328805415872}
133490045975010
Returns: 70289806672953968
50
{5, 38, 62, 120, 236, 477, 1180, 2170, 4510, 9002, 26733, 46794, 100491, 235970, 470599, 1105036, 2464223, 6701491, 11392546, 27750910, 51318854, 125006704, 226638163, 815897379, 1561083649, 2830257373, 6226566209, 13075789026, 27459156947, 94359648470, 154120759162, 370109994471, 825345287700, 1645993488399, 3142351205114, 6598937530728, 14172003935040, 40583465814009, 68991891883794, 136631001573798, 336112263871549, 749530348433569, 1671452677006837, 3030357292459546, 6666786043411014, 19091250942495168, 35000626727907804, 82187835307441680, 151987357878298272, 307014462914162496}
638546287949526
Returns: 343893092120240040
42
{6, 31, 76, 231, 534, 1348, 3342, 8370, 20946, 52354, 130881, 327195, 818011, 2045035, 5112553, 12781441, 31953546, 79883869, 199709677, 499274239, 1248185599, 3120463945, 7801159882, 19502899738, 48757249318, 121893123264, 304732808161, 761832020427, 1904580051067, 4761450127674, 11903625319159, 29759063297916, 74397658244824, 185994145612054, 464985364030113, 1162463410075252, 2906158525188171, 7265396312970387, 18163490782425960, 45408726956064904, 113521817390162304, 283804543475405760}
1573770316951
Returns: 140781879282794354
44
{3, 12, 27, 67, 171, 430, 1071, 2682, 6700, 16746, 41871, 104680, 261693, 654235, 1635592, 4088971, 10222431, 25556080, 63890203, 159725503, 399313756, 998284387, 2495710977, 6239277433, 15598193583, 38995483960, 97488709899, 243721774752, 609304436880, 1523261092203, 3808152730506, 9520381826260, 23800954565650, 59502386414124, 148755966035316, 371889915088285, 929724787720710, 2324311969301779, 5810779923254446, 14526949808136120, 36317374520340304, 90793436300850752, 226983590752126912, 567458976880317184}
11834408889654
Returns: 678679044854353282
47
{9, 11, 30, 55, 119, 433, 990, 2984, 8343, 13249, 47203, 132193, 370128, 633341, 1813645, 5440944, 8463695, 16927389, 34531864, 102579951, 174385911, 518028756, 906550310, 2177015824, 5920421091, 14801052714, 27135263307, 52839758183, 115107786944, 230738791098, 495539022792, 1419043565283, 3547608913207, 10642826739609, 20363275161776, 38764722594561, 83251856619742, 166882130769574, 586471488133087, 1368433472310529, 2394758576543433, 8415865854709776, 13353173822806182, 26973411122068476, 58759725012976632, 201919782317319680, 565375390488495168}
79465479585216
Returns: 592961547964152703
50
{1, 2, 4, 8, 16, 32, 65, 131, 265, 535, 1081, 2183, 4410, 8908, 17994, 36348, 73423, 148315, 299596, 605184, 1222472, 2469393, 4988174, 10076111, 20353745, 41114564, 83051420, 167763868, 338883013, 684543687, 1382778247, 2793212059, 5642288360, 11397422487, 23022793424, 46506042716, 93942206286, 189763256698, 383321778530, 774309992631, 1564106185114, 3159494493931, 6382178877740, 12892001333035, 26041842692731, 52604522239316, 106261134923419, 214647492545306, 433587934941518, 875847628581867}
622759709986387774
Returns: -1
37
{36, 73, 212, 581, 1636, 4572, 12814, 35865, 100452, 281242, 787492, 2204967, 6173915, 17286962, 48403477, 135529767, 379483327, 1062553320, 2975149281, 8330417996, 23325170396, 65310477111, 182869335892, 512034140529, 1433695593477, 4014347661714, 11240173452816, 31472485667868, 88122959870054, 246744287636153, 690884005381210, 1934475215067396, 5416530602188691, 15166285686128362, 42465599921159408, 118903679779246336, 332930303381889728}
43666684601
Returns: 134352808723215253
50
{18, 30, 60, 119, 244, 491, 994, 2006, 4049, 8182, 16530, 33394, 67449, 136245, 275219, 555931, 1122997, 2268448, 4582265, 9256166, 18697474, 37768886, 76293144, 154112151, 311306550, 628839236, 1270255247, 2565915615, 5183149541, 10469962072, 21149323370, 42721633224, 86297699094, 174321352177, 352129131398, 711300845419, 1436827707750, 2902391969668, 5862831778717, 11842920193020, 23922698789895, 48323851555592, 97614180142295, 197180643887438, 398304900652610, 804575899318284, 1625243316622928, 3282991499578308, 6631642829148192, 13395918514879340}
799887268548719
Returns: 18883781339321939
50
{11, 16, 40, 75, 170, 356, 745, 1563, 3285, 6890, 14473, 30396, 63827, 134037, 281482, 591108, 1241331, 2606795, 5474274, 11495962, 24141531, 50697214, 106464150, 223574714, 469506900, 985964492, 2070525433, 4348103411, 9131017161, 19175136029, 40267785663, 84562349898, 177580934785, 372919963039, 783131922390, 1644577037020, 3453611777738, 7252584733245, 15230427939819, 31983898673624, 67166187214613, 141048993150685, 296202885616441, 622026059794523, 1306254725568490, 2743134923693829, 5760583339757048, 12097225013489798, 25404172528328576, 53348762309490016}
491855319641818
Returns: 42697231696724237
5
{100000000000, 300000000000, 700000000000, 1300000000000, 3000000000000}
10
Returns: 1400000000000
Watch out for integer overflow.
40
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888 }
4000000000
Returns: 3999999999
50
{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624 }
123
Returns: 244
5
{100000000000, 300000000000, 700000000000, 1300000000000, 3000000000000 }
10
Returns: 1400000000000
50
{2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624 }
1234
Returns: 2466