Statistics

Problem Statement for "ColorfulCoins"

Problem Statement

The currency system in Colorland consists of various types of coins. The coin denominations follow these simple rules:
  • The denominations are distinct positive integers.
  • There is a coin type with denomination 1.
  • For each pair of different coin types, the denomination of one coin type divides the denomination of the other one.
You are given a long[] values containing all the available denominations in ascending order.

Coins of different denominations look exactly the same except that they have different colors. Each coin in Colorland has exactly one color. The coin colors follow these even simpler rules:
  • All coins of the same type are of the same color.
  • No two coins of different types are of the same color.
You know all coin denominations used in Colorland, but you don't know their colors. You don't even know the set of colors used on the coins.

For each denomination, you'd like to know the color of coins of this denomination. To accomplish this, you've got a credit card with an infinite amount of money. You can perform queries to an ATM which can also provide you with an infinite amount of money. Each query is described by a positive integer X, which means that you want to receive exactly X units of money from the ATM. The ATM will provide you with the requested amount. You also know that the requested amount will be paid using the smallest possible number of coins. (Note that this rule always uniquely determines the set of coins chosen to make the payment.)

Return the smallest number of queries you need to determine the corresponding color for each of the denominations. (Note that this can always be done in a finite number of queries.)

Definition

Class:
ColorfulCoins
Method:
minQueries
Parameters:
long[]
Returns:
int
Method signature:
int minQueries(long[] values)
(be sure your method is public)

Constraints

  • values will contain between 1 and 60 elements, inclusive.
  • Each element of values will be between 1 and 10^18, inclusive.
  • values will be sorted in strictly ascending order. Note that this also implies that all the elements of values will be distinct.
  • For each pair of different elements in values, the smaller one will be a divisor of the larger one.
  • values[0] will be 1.

Examples

  1. {1}

    Returns: 1

    There is just one coin type. We have to make a query to learn the color of coins.

  2. {1, 3}

    Returns: 1

    Just one query with X = 5 is one possible solution. As the ATM gives the smallest number of coins, it will give one coin of denomination 3 and two coins of denomination 1. That means, for example, that if you get one red coin and two blue coins, you'll understand that coins of denomination 3 are red, and coins of denomination 1 are blue.

  3. {1, 2, 4}

    Returns: 2

    One optimal solution is to make two queries, first X = 5 and then X = 6. After the first query you'll receive one coin from each of denominations 1 and 4, and after the second query you'll receive one coin from each of denominations 2 and 4. Now you can uniquely determine the color of each denomination. For example, coins of denomination 4 have the color which appears twice among the received coins.

  4. {1, 2, 4, 8, 16}

    Returns: 3

  5. {1, 2, 6, 30, 90, 270, 810, 2430, 7290, 29160, 87480, 262440, 787320, 3149280, 9447840, 28343520, 56687040, 170061120, 510183360, 1530550080, 3061100160, 9183300480, 27549901440, 82649704320, 247949112960, 1239745564800, 3719236694400, 14876946777600, 44630840332800, 223154201664000, 669462604992000, 2008387814976000, 6025163444928000, 12050326889856000, 24100653779712000, 72301961339136000, 289207845356544000, 867623536069632000}

    Returns: 4

  6. {1, 10, 80, 240, 1680, 13440, 67200, 201600, 1008000, 5040000}

    Returns: 2

  7. {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, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488}

    Returns: 6

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

    Returns: 4

  9. {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656, 1125899906842624, 4503599627370496, 18014398509481984, 72057594037927936, 288230376151711744}

    Returns: 3

  10. {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625, 19073486328125, 95367431640625, 476837158203125, 2384185791015625, 11920928955078125, 59604644775390625, 298023223876953125}

    Returns: 3

  11. {1, 6, 36, 216, 1296, 7776, 46656, 279936, 1679616, 10077696, 60466176, 362797056, 2176782336, 13060694016, 78364164096, 470184984576, 2821109907456, 16926659444736, 101559956668416, 609359740010496, 3656158440062976, 21936950640377856, 131621703842267136, 789730223053602816}

    Returns: 2

  12. {1, 7, 49, 343, 2401, 16807, 117649, 823543, 5764801, 40353607, 282475249, 1977326743, 13841287201, 96889010407, 678223072849, 4747561509943, 33232930569601, 232630513987207, 1628413597910449, 11398895185373143, 79792266297612001, 558545864083284007}

    Returns: 2

  13. {1, 8, 64, 512, 4096, 32768, 262144, 2097152, 16777216, 134217728, 1073741824, 8589934592, 68719476736, 549755813888, 4398046511104, 35184372088832, 281474976710656, 2251799813685248, 18014398509481984, 144115188075855872}

    Returns: 2

  14. {1, 9, 81, 729, 6561, 59049, 531441, 4782969, 43046721, 387420489, 3486784401, 31381059609, 282429536481, 2541865828329, 22876792454961, 205891132094649, 1853020188851841, 16677181699666569, 150094635296999121}

    Returns: 2

  15. {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000}

    Returns: 2

  16. {1, 11, 121, 1331, 14641, 161051, 1771561, 19487171, 214358881, 2357947691, 25937424601, 285311670611, 3138428376721, 34522712143931, 379749833583241, 4177248169415651, 45949729863572161, 505447028499293771}

    Returns: 2

  17. {1, 12, 144, 1728, 20736, 248832, 2985984, 35831808, 429981696, 5159780352, 61917364224, 743008370688, 8916100448256, 106993205379072, 1283918464548864, 15407021574586368, 184884258895036416}

    Returns: 2

  18. {1, 13, 169, 2197, 28561, 371293, 4826809, 62748517, 815730721, 10604499373, 137858491849, 1792160394037, 23298085122481, 302875106592253, 3937376385699289, 51185893014090757, 665416609183179841}

    Returns: 2

  19. {1, 14, 196, 2744, 38416, 537824, 7529536, 105413504, 1475789056, 20661046784, 289254654976, 4049565169664, 56693912375296, 793714773254144, 11112006825558016, 155568095557812224}

    Returns: 2

  20. {1, 15, 225, 3375, 50625, 759375, 11390625, 170859375, 2562890625, 38443359375, 576650390625, 8649755859375, 129746337890625, 1946195068359375, 29192926025390625, 437893890380859375}

    Returns: 2

  21. {1, 16, 256, 4096, 65536, 1048576, 16777216, 268435456, 4294967296, 68719476736, 1099511627776, 17592186044416, 281474976710656, 4503599627370496, 72057594037927936}

    Returns: 1

  22. {1, 17, 289, 4913, 83521, 1419857, 24137569, 410338673, 6975757441, 118587876497, 2015993900449, 34271896307633, 582622237229761, 9904578032905937, 168377826559400929}

    Returns: 1

  23. {1, 18, 324, 5832, 104976, 1889568, 34012224, 612220032, 11019960576, 198359290368, 3570467226624, 64268410079232, 1156831381426176, 20822964865671168, 374813367582081024}

    Returns: 1

  24. {1, 19, 361, 6859, 130321, 2476099, 47045881, 893871739, 16983563041, 322687697779, 6131066257801, 116490258898219, 2213314919066161, 42052983462257059, 799006685782884121}

    Returns: 1

  25. {1, 20, 400, 8000, 160000, 3200000, 64000000, 1280000000, 25600000000, 512000000000, 10240000000000, 204800000000000, 4096000000000000, 81920000000000000}

    Returns: 1

  26. {1, 68719476736, 549755813888, 1649267441664, 11544872091648, 92358976733184, 461794883665920, 1385384650997760, 6926923254988800, 34634616274944000, 346346162749440000}

    Returns: 2

  27. {1, 2, 576460752303423492}

    Returns: 1

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

    Returns: 5

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

    Returns: 6

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

    Returns: 3

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

    Returns: 4

  32. {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824}

    Returns: 2

  33. {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296}

    Returns: 3

  34. {1, 16, 32, 224, 2464, 12320, 36960, 369600, 6652800, 79833600, 479001600, 7185024000, 122145408000, 1587890304000, 14291012736000, 200074178304000, 800296713216000, 15205637551104000, 121645100408832000}

    Returns: 1

  35. {1, 7, 77, 616, 5544, 16632, 266112, 1064448, 10644480, 159667200, 1916006400, 36404121600, 72808243200, 1310548377600, 6552741888000, 91738386432000, 550430318592000, 4403442548736000, 74858523328512000, 973160803270656000}

    Returns: 2

  36. {1, 3, 48, 624, 5616, 95472, 1718496, 24058944, 288707328, 1732243968, 13857951744, 124721565696, 2244988182528, 8979952730112, 35919810920448, 574716974727168, 6896603696726016, 62069433270534144, 806902632516943872}

    Returns: 2

  37. {1, 6, 78, 1014, 3042, 27378, 328536, 3942432, 70963776, 1348311744, 22921299648, 91685198592, 1466963177472, 13202668597248, 118824017375232, 1663536243253248, 26616579892051968, 212932639136415744, 851730556545662976}

    Returns: 1

  38. {1, 3, 15, 75, 375, 1500, 3000, 6000, 12000, 36000, 180000, 540000, 2700000, 16200000, 97200000, 388800000, 1944000000, 5832000000, 29160000000, 174960000000, 699840000000, 4199040000000, 16796160000000, 50388480000000, 302330880000000, 1209323520000000, 4837294080000000, 24186470400000000, 96745881600000000, 483729408000000000}

    Returns: 2

  39. {1, 6, 30, 90, 360, 1440, 7200, 36000, 108000, 216000, 864000, 1728000, 3456000, 17280000, 69120000, 345600000, 1382400000, 5529600000, 16588800000, 82944000000, 497664000000, 2985984000000, 14929920000000, 44789760000000, 223948800000000, 895795200000000, 4478976000000000, 26873856000000000, 134369280000000000, 403107840000000000}

    Returns: 3

  40. {1, 2, 6, 18, 36, 108, 324, 972, 2916, 5832, 11664, 34992, 104976, 314928, 944784, 1889568, 3779136, 7558272, 22674816, 68024448, 204073344, 408146688, 816293376, 2448880128, 7346640384, 22039921152, 44079842304, 132239526912, 264479053824, 528958107648, 1586874322944, 4760622968832, 14281868906496, 28563737812992, 85691213438976, 171382426877952, 342764853755904, 685529707511808, 2056589122535424, 4113178245070848, 12339534735212544, 24679069470425088, 49358138940850176, 148074416822550528, 296148833645101056, 592297667290202112}

    Returns: 5

  41. {1, 3, 9, 18, 36, 144, 288, 864, 2592, 5184, 15552, 62208, 186624, 559872, 2239488, 8957952, 26873856, 107495424, 214990848, 429981696, 1289945088, 3869835264, 7739670528, 23219011584, 69657034752, 139314069504, 278628139008, 1114512556032, 2229025112064, 6687075336192, 20061226008576, 40122452017152, 120367356051456, 361102068154368, 1444408272617472, 5777633090469888, 23110532361879552, 46221064723759104, 138663194171277312, 554652776685109248}

    Returns: 4

  42. {1, 5, 25, 50, 100, 400, 1600, 8000, 16000, 32000, 64000, 128000, 384000, 768000, 1536000, 4608000, 13824000, 69120000, 276480000, 1105920000, 3317760000, 13271040000, 53084160000, 159252480000, 318504960000, 637009920000, 3185049600000, 6370099200000, 19110297600000, 95551488000000, 382205952000000, 1528823808000000, 7644119040000000, 15288238080000000, 61152952320000000, 122305904640000000, 611529523200000000}

    Returns: 4

  43. {1, 2, 8, 32, 192, 576, 2880, 8640, 51840, 311040, 933120, 3732480, 18662400, 74649600, 149299200, 746496000, 4478976000, 17915904000, 71663616000, 429981696000, 1289945088000, 6449725440000, 38698352640000, 232190115840000, 1160950579200000, 6965703475200000, 34828517376000000, 139314069504000000, 835884417024000000}

    Returns: 2

  44. {1, 4, 16, 64, 128, 512, 3584, 25088, 150528, 301056, 2107392, 12644352, 63221760, 442552320, 3097866240, 12391464960, 74348789760, 446092738560, 2230463692800, 8921854771200, 53531128627200, 267655643136000, 1605933858816000, 3211867717632000, 19271206305792000, 134898444140544000, 674492220702720000}

    Returns: 2

  45. {1, 4, 24, 48, 240, 1680, 13440, 40320, 241920, 1209600, 8467200, 67737600, 270950400, 1354752000, 9483264000, 47416320000, 237081600000, 711244800000, 4267468800000, 21337344000000, 85349376000000, 426746880000000, 853493760000000, 3413975040000000, 6827950080000000, 34139750400000000, 136559001600000000, 546236006400000000}

    Returns: 2

  46. {1, 9, 27, 135, 1080, 5400, 21600, 86400, 604800, 1209600, 3628800, 14515200, 72576000, 435456000, 1306368000, 6531840000, 58786560000, 176359680000, 881798400000, 1763596800000, 12345177600000, 111106598400000, 999959385600000, 8999634470400000, 17999268940800000, 161993420467200000, 971960522803200000}

    Returns: 2

  47. {1, 5, 10, 100, 700, 6300, 12600, 88200, 441000, 2646000, 21168000, 42336000, 169344000, 1016064000, 7112448000, 49787136000, 497871360000, 1991485440000, 15931883520000, 111523184640000, 446092738560000, 1784370954240000, 12490596679680000, 74943580078080000, 599548640624640000}

    Returns: 2

  48. {1, 5, 55, 385, 1155, 5775, 46200, 138600, 277200, 3049200, 27442800, 109771200, 548856000, 2195424000, 21954240000, 241496640000, 965986560000, 9659865600000, 28979596800000, 260816371200000, 1564898227200000, 4694694681600000, 28168168089600000, 84504504268800000, 845045042688000000}

    Returns: 2

  49. {1, 8, 48, 192, 384, 2304, 20736, 207360, 2488320, 22394880, 67184640, 739031040, 5912248320, 70946979840, 567575838720, 1135151677440, 2270303354880, 22703033548800, 45406067097600, 317842469683200, 1907054818099200, 22884657817190400, 228846578171904000, 915386312687616000}

    Returns: 3

  50. {1, 8, 24, 120, 360, 720, 3600, 32400, 259200, 777600, 2332800, 4665600, 13996800, 55987200, 223948800, 895795200, 3583180800, 7166361600, 64497254400, 193491763200, 1934917632000, 7739670528000, 15479341056000, 46438023168000, 139314069504000, 835884417024000, 2507653251072000, 22568879259648000, 112844396298240000, 677066377789440000}

    Returns: 3

  51. {1, 13, 39, 273, 1911, 34398, 447174, 1788696, 8943480, 107321760, 214643520, 1073217600, 18244699200, 127712894400, 2043406310400, 12260437862400, 49041751449600, 294250508697600, 588501017395200, 2942505086976000, 14712525434880000, 29425050869760000, 588501017395200000}

    Returns: 2

  52. {1, 29, 58, 174, 1566, 43848, 175392, 1052352, 2104704, 27361152, 109444608, 547223040, 2188892160, 61288980480, 122577960960, 490311843840, 23534968504320, 353024527564800, 1765122637824000, 17651226378240000, 229465942917120000, 917863771668480000}

    Returns: 2

  53. {1, 2, 116, 696, 6960, 41760, 250560, 751680, 2255040, 85691520, 514149120, 10282982400, 113112806400, 226225612800, 678676838400, 2036030515200, 26468396697600, 291152363673600, 4949590182451200, 9899180364902400, 702841805908070400}

    Returns: 2

  54. {1, 52, 4680, 173160, 865800, 55411200, 3490905600, 13963622400, 69818112000, 2094543360000, 12567260160000, 37701780480000, 5542161730560000, 77590264227840000, 543131849594880000}

    Returns: 1

  55. {1, 203, 406, 1218, 3654, 43848, 11970504, 694289232, 14580073872, 5598748366848, 901398487062528, 19830766715375616, 277630734015258624, 832892202045775872}

    Returns: 2

  56. {1, 2, 8, 16, 192, 56640, 1755840, 193142400, 3476563200, 62578137600, 9136408089600, 383729139763200, 767458279526400, 75978369673113600, 987718805750476800}

    Returns: 2

  57. {1, 1266, 5064, 70896, 3544800, 3374649600, 43870444800, 570315782400, 1140631564800, 4562526259200, 2340575970969600, 98304190780723200, 786433526245785600}

    Returns: 1

  58. {1, 24, 48, 96, 1152, 744192, 5953536, 101210112, 26213419008, 445628123136, 75311152809984, 1656845361819648, 777060474693414912}

    Returns: 2

  59. {1, 3, 168, 672, 6577536, 22962178176, 122043977005440, 244087954010880, 10007606114446080, 710540034125671680}

    Returns: 1

  60. {1, 2, 36, 458568, 22469832, 4044569760, 62322775431840, 547131645516123360}

    Returns: 1

  61. {1, 6, 12, 10056, 20112, 985488, 1035747888, 5178739440, 15660508066560, 125284064532480, 375852193597440, 49988341748459520, 749825126226892800}

    Returns: 2

  62. {1, 84158, 23059292, 276711504, 78586067136, 1581308842910592, 9487853057463552, 929809599631428096}

    Returns: 1

  63. {1, 109, 331741936, 2653935488, 7961806464, 546570051947136, 776129473764933120}

    Returns: 1

  64. {1, 4095, 8190, 393120, 166570840800, 55164264772780800, 827463971591712000}

    Returns: 1

  65. {1, 230960, 461920, 923840, 28148480960, 600069317105280, 715282625989493760}

    Returns: 2

  66. {1, 291, 2259324, 5494675968, 3131965301760, 28187687715840, 84563063147520, 719885356574837760}

    Returns: 1

  67. {1, 10, 101290, 100986130, 807889040, 11310446560, 79173125920, 9738294488160, 876446503934400, 597736515683260800}

    Returns: 1

  68. {1, 15, 30, 90, 69300, 64896125679000, 12070679376294000, 772523480082816000}

    Returns: 1

  69. {1, 5, 50, 250, 750, 2250, 18000, 90000, 15120000, 105840000, 846720000, 794136393388800000}

    Returns: 2

  70. {1, 5, 40, 320, 3200, 25600, 128000, 256000, 2048000, 16384000, 163840000, 655360000, 6553600000, 8935853260800000, 17871706521600000, 71486826086400000, 571894608691200000}

    Returns: 2

  71. {1, 2, 4, 8, 16, 32, 64, 2304667200, 4609334400, 9218668800, 27656006400, 55312012800, 110624025600, 221248051200, 442496102400, 884992204800, 1769984409600, 3539968819200, 7079937638400, 14159875276800, 28319750553600, 56639501107200, 113279002214400, 226558004428800, 453116008857600, 906232017715200, 1812464035430400, 3624928070860800, 7249856141721600, 14499712283443200, 28999424566886400, 57998849133772800, 115997698267545600, 231995396535091200, 463990793070182400, 927981586140364800}

    Returns: 6

  72. {1, 3, 9, 27, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, 19131876, 57395628, 172186884, 516560652, 13020427794312, 39061283382936, 117183850148808, 351551550446424, 1054654651339272, 3163963954017816, 9491891862053448, 28475675586160344, 85427026758481032, 256281080275443096, 768843240826329288}

    Returns: 4

  73. {1, 4, 20, 60, 240, 960, 2880, 14400, 72000, 216000, 1080000, 3240000, 9720000, 38880000, 194400000, 972000000, 1944000000, 7776000000, 38880000000, 77760000000, 311040000000, 4665288960000000, 9330577920000000, 46652889600000000, 186611558400000000, 933057792000000000}

    Returns: 2

  74. {1, 5, 25, 125, 500, 2500, 10000, 40000, 200000, 2122000000, 10610000000, 31830000000, 95490000000, 381960000000, 1145880000000, 3437640000000, 6875280000000, 20625840000000, 82503360000000, 412516800000000, 2062584000000000, 8250336000000000, 16500672000000000, 33001344000000000, 132005376000000000, 660026880000000000}

    Returns: 2

  75. {1, 5, 20, 80, 320, 1600, 6400, 19200, 206169600, 618508800, 3092544000, 12370176000, 49480704000, 247403520000, 494807040000, 1979228160000, 9896140800000, 29688422400000, 59376844800000, 296884224000000, 1484421120000000, 7422105600000000, 14844211200000000, 44532633600000000, 222663168000000000, 667989504000000000}

    Returns: 2

  76. {1, 3, 9, 27, 270, 540, 1080, 3240, 55555555555553400, 166666666666660200, 333333333333320400, 999999999999961200}

    Returns: 3

  77. {1, 4, 13245476616, 26490953232, 52981906464, 211927625856, 423855251712, 847710503424, 2543131510272, 7629394530816, 15258789061632, 61035156246528, 244140624986112, 976562499944448, 3906249999777792, 15624999999111168, 62499999996444672, 249999999985778688, 999999999943114752}

    Returns: 3

  78. {1, 5, 25, 125, 625, 1250, 6250, 25000, 125000, 625000, 2500000, 12500000, 62500000, 187500000, 750000000, 416250000000, 832500000000, 4162500000000, 20812500000000, 104062500000000, 416250000000000, 1665000000000000, 3330000000000000, 6660000000000000, 19980000000000000, 39960000000000000, 199800000000000000, 999000000000000000}

    Returns: 3

  79. {1, 2, 4, 8, 10416666666666664, 20833333333333328, 41666666666666656, 124999999999999968, 249999999999999936, 499999999999999872, 999999999999999744}

    Returns: 4

  80. {1, 6, 24, 36432, 255024, 1530144, 10711008, 53555040, 160665120, 642660480, 3213302400, 19279814400, 57839443200, 404876102400, 2024380512000, 14170663584000, 99194645088000, 595167870528000, 2380671482112000, 11903357410560000, 83323501873920000, 166647003747840000, 999882022487040000}

    Returns: 2

  81. {1, 4, 20, 100, 400, 1600, 6400, 32000, 160000, 480000, 2400000, 12000000, 60000000, 240000000, 1200000000, 6000000000, 30000000000, 90000000000, 180000000000, 720000000000, 3600000000000, 10800000000000, 43200000000000, 820800000000000, 4104000000000000, 16416000000000000, 65664000000000000, 196992000000000000, 984960000000000000}

    Returns: 3

  82. {1, 10, 130, 1040, 6240, 81120, 1054560, 6327360, 5716776087360, 74318089135680, 445908534814080, 5796810952583040, 75358542383579520, 979661050986533760}

    Returns: 1

  83. {1, 6, 78, 1014, 8112, 105456, 1370928, 8225568, 49353408, 493534080, 987068160, 24416118005760, 317409534074880, 4126323942973440, 53642211258654720}

    Returns: 2

  84. {1, 5, 15, 60, 120, 999999999999999960}

    Returns: 1

  85. {1, 3, 15, 75, 225, 450, 900, 3600, 14400, 72000, 288000, 1152000, 8064000, 16128000, 80640000, 161280000, 322560000, 645120000, 2580480000, 18063360000, 108380160000, 433520640000, 16015119482880000, 64060477931520000, 320302389657600000, 640604779315200000}

    Returns: 3

  86. {1, 7, 28, 56, 224, 448, 1792, 3584, 10752, 21504, 86016, 172032, 688128, 3440640, 13762560, 55050240, 110100480, 550502400, 2202009600, 8808038400, 52848230400, 264241152000, 1849688064000, 66834778816512000, 200504336449536000, 802017345798144000}

    Returns: 3

  87. {1, 100, 10000, 1000000, 100000000, 10000000000, 1000000000000, 100000000000000, 10000000000000000, 1000000000000000000}

    Returns: 1

  88. {1, 1000, 1000000, 1000000000, 1000000000000, 1000000000000000, 1000000000000000000}

    Returns: 1

  89. {1, 10000, 100000000, 1000000000000, 10000000000000000}

    Returns: 1

  90. {1, 1000000, 1000000000000, 1000000000000000000}

    Returns: 1

  91. {1, 1000000000, 1000000000000000000}

    Returns: 1

  92. {1, 2, 4, 16, 96, 672, 1344, 2688, 8064, 40320, 80640, 241920, 725760, 680688350979840, 2042065052939520, 4084130105879040, 8168260211758080, 16336520423516160, 441086051434936320, 882172102869872640}

    Returns: 4

  93. {1, 5, 25, 125, 375, 1875, 9375, 46875, 234375, 1171875, 5859375, 29296875, 146484375, 732421875, 3662109375, 18310546875, 91552734375, 457763671875, 2288818359375, 11444091796875, 57220458984375, 286102294921875, 1430511474609375, 7152557373046875, 35762786865234375, 178813934326171875, 894069671630859375}

    Returns: 3

  94. {1, 2251799813685249}

    Returns: 1

  95. {1, 2}

    Returns: 1

  96. {1, 42}

    Returns: 1

  97. {1, 20000}

    Returns: 1

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

    Returns: 4

  99. {1, 2, 8, 16, 64, 512, 4096, 16384}

    Returns: 2

  100. {1, 2, 8, 64, 512, 4096, 16384}

    Returns: 1

  101. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683}

    Returns: 3

  102. {1, 9, 27, 243, 729, 2187, 19683}

    Returns: 2

  103. {1, 9, 27, 243, 729, 19683}

    Returns: 1

  104. {1, 4, 16, 64, 256, 1024, 4096, 16384}

    Returns: 2

  105. {1, 16, 256, 1024, 4096, 16384}

    Returns: 1

  106. {1, 5, 25, 125, 625, 3125, 15625}

    Returns: 2

  107. {1, 5, 25, 125, 3125, 15625}

    Returns: 1

  108. {1, 6, 36, 216, 1296, 7776}

    Returns: 1

  109. {1, 10, 100, 1000, 10000}

    Returns: 1

  110. {1, 10, 100, 1000, 10000, 20000}

    Returns: 1

  111. {1, 5, 25, 100, 400, 2800, 19600}

    Returns: 1

  112. {1, 3, 18, 108, 540, 2700, 18900}

    Returns: 1

  113. {1, 2, 14, 98, 686, 4802, 19208}

    Returns: 1

  114. {1, 4, 16, 80, 400, 2800, 19600}

    Returns: 1

  115. {1, 2, 12, 72, 432, 2592, 18144}

    Returns: 1

  116. {1, 2, 8, 56, 392, 2352, 16464}

    Returns: 1

  117. {1, 4, 20, 100, 400, 2800, 19600}

    Returns: 1

  118. {1, 2, 6, 24, 120, 720, 5040}

    Returns: 1

  119. {1, 2, 6, 12, 36, 72, 216, 648, 1296, 2592, 7776, 15552}

    Returns: 3

  120. {1, 100, 20000}

    Returns: 1

  121. {1, 2, 10000, 20000}

    Returns: 2

  122. {1, 3, 6561, 19683}

    Returns: 1

  123. {1, 3, 9, 6561, 19683}

    Returns: 2

  124. {1, 3, 2187, 6561, 19683}

    Returns: 2

  125. {1, 23, 966, 11592}

    Returns: 1

  126. {1, 1000, 2000, 4000, 8000, 16000}

    Returns: 3

  127. {1, 5000, 10000, 20000}

    Returns: 2

  128. {1, 2000, 10000, 20000}

    Returns: 1

  129. {1, 19999}

    Returns: 1

  130. {1, 10007}

    Returns: 1

  131. {1, 101, 10201}

    Returns: 1

  132. {1, 99, 9801}

    Returns: 1

  133. {1, 49, 2401}

    Returns: 1

  134. {1, 99, 9801, 19602}

    Returns: 1

  135. {1, 4, 24, 144, 432, 2160, 12960}

    Returns: 2

  136. {1, 4, 24, 144, 432, 2160, 15120}

    Returns: 1

  137. {1, 3, 9, 36, 144}

    Returns: 2

  138. {1, 5, 10, 40, 200, 1000}

    Returns: 2

  139. {1, 2, 6, 30, 210, 2310}

    Returns: 1

  140. {1, 4, 8, 32, 64, 256, 512, 2048, 4096, 16384}

    Returns: 3

  141. {1, 3, 9, 1107, 4428}

    Returns: 1

  142. {1, 3, 9, 45, 405, 1215}

    Returns: 2

  143. {1, 3, 9, 27, 621, 19872}

    Returns: 2

  144. {1, 2, 4, 8, 16}

    Returns: 3

  145. {1, 7, 42, 210, 840, 2520, 5040}

    Returns: 1

  146. {1, 7, 42, 210, 840, 2520, 17640}

    Returns: 1

  147. {1, 7, 42, 210, 840, 2520, 10080}

    Returns: 1

  148. {1, 7, 42, 210, 420, 1260, 5040, 15120}

    Returns: 2

  149. {1, 4, 24, 48, 144, 720, 4320}

    Returns: 2

  150. {1, 5, 25, 100, 500, 3500, 17500}

    Returns: 2

  151. {1, 6, 42, 168, 672, 2688, 10752}

    Returns: 2

  152. {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, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488 }

    Returns: 6

  153. {1, 2, 6, 42, 294, 1764, 14112, 42336, 84672, 423360, 2963520, 23708160, 142248960, 711244800, 2133734400, 14936140800, 119489126400, 955913011200, 7647304089600, 22941912268800, 183535298150400, 917676490752000, 5506058944512000, 44048471556096000, 132145414668288000 }

    Returns: 2

  154. {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456, 1073741824, 4294967296, 17179869184, 68719476736, 274877906944, 1099511627776, 4398046511104, 17592186044416, 70368744177664, 281474976710656, 1125899906842624, 4503599627370496 }

    Returns: 3

  155. {1, 4, 12, 48, 144, 432, 864, 3456, 10368, 20736, 82944, 248832, 995328, 1990656, 5971968, 17915904, 71663616, 143327232, 286654464, 859963392, 1719926784, 5159780352 }

    Returns: 3

  156. {1, 2, 4, 8, 24, 72 }

    Returns: 2

  157. {1, 2, 6, 30, 60, 180, 900, 1800, 5400, 27000, 54000, 162000, 810000, 1620000, 4860000, 24300000, 48600000, 145800000, 729000000, 1458000000, 4374000000, 21870000000, 43740000000, 131220000000, 656100000000, 1312200000000, 3936600000000, 19683000000000, 39366000000000, 118098000000000, 590490000000000, 1180980000000000, 3542940000000000, 17714700000000000, 35429400000000000, 106288200000000000, 531441000000000000 }

    Returns: 4

  158. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827 }

    Returns: 3

  159. {1, 3, 9, 27 }

    Returns: 2

  160. {1, 4, 16, 64 }

    Returns: 1

  161. {1, 2, 8, 32 }

    Returns: 1

  162. {1, 2, 4, 8, 24, 72, 216, 648, 1944 }

    Returns: 2

  163. {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, 564859072962 }

    Returns: 3

  164. {1, 3, 9, 27, 81 }

    Returns: 2

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

    Returns: 6

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

    Returns: 4

  167. {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000 }

    Returns: 2

  168. {1, 5, 15, 60, 120, 360, 2160, 8640, 25920, 51840, 311040, 1244160, 6220800, 18662400, 111974400, 335923200, 671846400, 1343692800, 8062156800, 24186470400, 145118822400, 870712934400, 3482851737600, 10448555212800, 31345665638400, 62691331276800, 313456656384000, 626913312768000, 3761479876608000 }

    Returns: 3

  169. {1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 1062882, 3188646, 9565938, 28697814, 86093442, 258280326, 774840978, 2324522934, 6973568802, 20920706406, 62762119218, 188286357654, 564859072962, 1694577218886, 5083731656658 }

    Returns: 4

  170. {1, 3, 9, 27, 81, 243, 729, 2187 }

    Returns: 2

  171. {1, 1048576, 1099511627776 }

    Returns: 1

  172. {1, 5, 25, 125, 625, 3125, 15625, 78125 }

    Returns: 2

  173. {1, 3, 9, 27, 81, 243, 729, 2187, 6561 }

    Returns: 2

  174. {1, 5, 25, 125, 625 }

    Returns: 1

  175. {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125, 6103515625, 30517578125, 152587890625, 762939453125, 3814697265625, 19073486328125, 95367431640625, 476837158203125, 2384185791015625, 11920928955078125, 59604644775390625 }

    Returns: 2

  176. {1, 2, 4, 8 }

    Returns: 2

  177. {1, 3, 9 }

    Returns: 1

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

    Returns: 5

  179. {1, 2, 4, 800000000000000000 }

    Returns: 2

  180. {1, 100000000, 200000000 }

    Returns: 1

  181. {1, 2, 6, 24, 120, 120000000000000 }

    Returns: 1

  182. {1, 2, 4, 8, 16, 32, 64, 128 }

    Returns: 3

  183. {1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, 4194304, 16777216, 67108864, 268435456 }

    Returns: 2

  184. {1, 3, 9, 45, 225, 675, 3375, 6750, 33750, 168750, 506250, 1012500, 5062500, 10125000, 50625000, 101250000, 506250000, 1518750000, 4556250000, 13668750000, 41006250000, 82012500000, 246037500000, 492075000000, 2460375000000, 7381125000000, 14762250000000, 29524500000000, 59049000000000, 295245000000000, 885735000000000, 2657205000000000, 13286025000000000, 66430125000000000, 199290375000000000, 996451875000000000 }

    Returns: 4

  185. {1, 4294967296 }

    Returns: 1

  186. {1, 2, 1000000000000000000 }

    Returns: 1

  187. {1, 2, 4, 8, 32, 128, 512, 2048, 6144, 18432, 55296 }

    Returns: 2

  188. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 2324522934, 4649045868, 9298091736, 18596183472, 37192366944, 74384733888, 148769467776 }

    Returns: 3

  189. {1, 2, 4, 8, 100000000000000000 }

    Returns: 2

  190. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 }

    Returns: 4

  191. {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163 }

    Returns: 3

  192. {1, 1000000000000000000 }

    Returns: 1

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: