Statistics

Problem Statement for "ChangeOptimizer"

Problem Statement

Johnny Indecision has a change purse with some change in it. However, he is deathly afraid of having to figure out what might happen if he has to spend some of it. This fear arises because there may be more than one way to give out a certain amount of change. For example, if he has 1 dime (worth 10 cents) and 2 nickels (worth 5 cents apiece), there are two ways to make 10 cents. He also does not want to incur any more change, so he wants to be sure that he has exact change for any amount up to the amount of money he has.

So he would like to exchange his current change with some more predictable coins at the bank. As the bank clerk, you must solve Johnny's dilemma by giving him enough change to allow him to be able to spend any amount of money up to the amount he currently has, but the coins you give him must provide exactly one way to make each of those amounts. In addition, he would like to have as few coins as possible, even if it means having more smaller denomination coins. For example, if Johnny brings 49 cents to the bank, and the only coins available are 1, 10, and 25 cent pieces, there are three valid options:

  1. one 25-cent piece and 24 1-cent pieces
  2. four 10-cent pieces and nine 1-cent pieces
  3. 49 1-cent pieces
Each of these combinations results in only one way to make 1 to 49 cents, but the second way is preferable because it has the least number of coins of the three options. If multiple ways exist which have the fewest coins possible, return the way which has the most coins of the highest denomination. If multiple ways have an equal number of coins with the highest denomination, then return the way with the most coins of the second highest denomination, and so on. For example, with a monetary system that includes 1, 3, 6, and 2-cent pieces, and a balance of 11 cents, there are two answers with four coins:
  1. two 1-cent pieces, a one 3-cent piece, and a 6-cent piece
  2. one 1-cent piece, two 2-cent pieces, and a 6-cent piece
The first way is preferable because of its higher valued 3-cent piece.

You will be given a int[] coinTypes, which will be a list containing the value of each type of coin in the monetary system (which will always include a coin valued at 1). You will also be given an int value specifying the amount of money Johnny has. The return value should be a int[] indicating how many coins of each type you should give Johnny back. Element i of the return value should be how many coins valued at coinTypes[i] should be given to Johnny.

Definition

Class:
ChangeOptimizer
Method:
fewestCoins
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] fewestCoins(int[] coinTypes, int value)
(be sure your method is public)

Constraints

  • coinTypes has between 1 and 50 elements, inclusive.
  • Each element of coinTypes is between 1 and 100,000,000, inclusive.
  • There will be no repeated values in coinTypes.
  • There will be exactly one element in coinTypes equal to 1.
  • value is between 1 and 1,000,000,000, inclusive.

Examples

  1. {1,10,25}

    49

    Returns: { 9, 4, 0 }

    From the problem statement

  2. {1,3,6,2}

    11

    Returns: { 2, 1, 1, 0 }

    From the problem statement

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

    1234567

    Returns: { 1, 1, 0, 1, 0, 0, 0, 154320, 0, 0 }

  4. {91001,3567,222123,4456,1,732234,123793,982312,14781}

    65864135

    Returns: { 0, 0, 0, 0, 14780, 0, 0, 0, 4455 }

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

    1000000

    Returns: { 1000000, 0, 0, 0, 0 }

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

    134217727

    Returns: { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

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

    3628799

    Returns: { 4, 0, 0, 0, 1, 0, 0, 0, 0, 362879 }

  8. {5260, 259420, 415, 310420, 11519400, 80635800, 476, 3839800, 29055040, 77294580, 87165120, 395, 1, 20}

    806357999

    Returns: { 729, 0, 0, 0, 6, 9, 0, 2, 0, 0, 0, 0, 19, 262 }

  9. {3265020, 1, 938, 45710280, 812308, 91420560, 187, 16830}

    182841119

    Returns: { 13, 186, 0, 1, 0, 1, 89, 193 }

  10. {233, 91197900, 92713920, 300, 1, 218700, 119995, 12359485, 37078455, 203320, 391, 74156910}

    889882919

    Returns: { 514, 0, 0, 0, 232, 0, 102, 2, 1, 0, 0, 11 }

  11. {23434944, 71625708, 5858736, 1, 410, 70304832, 130, 124, 567, 72930, 98658, 60240180, 85682016, 10992, 23436, 101680, 21420504, 30120090, 16, 42841008}

    140609663

    Returns: { 2, 0, 3, 15, 0, 1, 0, 0, 0, 0, 0, 0, 0, 532, 0, 0, 0, 0, 686, 0 }

  12. {42557060, 99, 156, 12741, 366210, 90934272, 5616, 32559912, 85100, 11466900, 60191208, 25233824, 74547600, 97679736, 1, 10164, 137, 233830, 1280664, 585, 502856, 1636810, 3375570, 18636900, 20253420, 55220235, 60760260, 85114120, 78, 686, 698, 303, 965, 664048, 2066688, 62621910, 68801400, 80959816, 20873970, 86961, 75701472, 83061, 115, 363, 526, 306870, 1911150, 34400700}

    894418199

    Returns: { 0, 0, 0, 149, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 136, 0, 92, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 1 }

  13. {4210320, 3572360, 16, 74476116, 93952170, 706, 412, 4240, 153, 57157760, 83633934, 31317390, 53534, 18619029, 37238058, 501, 1, 324760, 382748, 41816967, 21879, 92627040, 218937, 377}

    968189507

    Returns: { 0, 0, 0, 12, 0, 0, 0, 0, 142, 0, 0, 0, 0, 1, 1, 0, 152, 0, 0, 0, 850, 0, 0, 0 }

  14. {21179700, 34800480, 213, 831, 3834, 1, 17400240, 56134881, 42359400, 68685760, 81227124, 84718800, 91942224, 40613562, 790920, 858572, 63191295, 988, 221877, 489855, 466, 22, 7458, 141198, 999372, 845, 867, 7059900, 3692142, 8700120}

    162454247

    Returns: { 0, 0, 17, 0, 962, 212, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0 }

  15. {46592, 1792, 12610, 538, 376, 217986, 128, 392740, 282, 29590, 34411520, 42071298, 52432380, 75699306, 84046360, 1, 513, 520, 312832, 88947540, 95047680, 99998080, 970, 765, 425277, 14824590, 420160, 19009536, 3745170, 26216190, 37849653, 42023180, 68823040, 84142596, 730}

    996215219

    Returns: { 0, 0, 296, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 0, 0, 969, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 6, 1, 0, 0, 0, 0, 0 }

  16. {64423520, 76626432, 1, 42140, 575210, 27027000, 186116, 917, 606597, 732, 713426, 723, 276, 39828824, 4026470, 9009000, 54593730, 59927784, 64305640, 81081000, 391, 56, 42251040, 970, 84502080, 94248960, 216672, 24024, 312, 266064, 14981946, 32152820, 360360, 14083680, 172, 294528}

    422510399

    Returns: { 0, 0, 731, 0, 0, 0, 0, 0, 0, 295, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0, 64, 0, 0, 0, 0, 0, 0, 2, 0, 0 }

  17. {34751808, 756, 87, 149, 68838, 318276, 383724, 817, 31644, 510625, 54, 4343976, 35631144, 43149876, 42180, 61908, 30314196, 47505915, 54244344, 56653128, 71262288, 86299752, 88848750, 90942588, 44424375, 57533520, 25704, 95011830, 66, 13561086, 14808125, 17815572, 459, 28766760, 53679, 1, 703, 72}

    570098303

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 562, 0, 585, 0, 1, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 53, 0, 0 }

  18. {623, 114, 639, 23798450, 737, 71556, 601, 10152108, 18590132, 27156, 604494, 28839672, 36779784, 14419836, 470, 549, 116090, 38211705, 41456250, 59679096, 22237, 382, 441396, 20485116, 71395350, 73559568, 76423410, 146, 23501340, 77979726, 81940464, 82912500, 86519016, 91368972, 94005360, 45828, 178, 1, 71816, 331650, 439215, 6828372, 890, 870420}

    778671143

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 530, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 185, 0, 0, 0, 0, 8, 0, 0, 0, 0, 145, 0, 0, 0, 0, 0, 0 }

  19. {1, 454990, 78258280, 40, 761, 48216960, 99801600, 535744, 792, 526, 49900800, 920, 33480, 441600, 27855360, 31268160, 744480, 39129140, 83566080, 93804480}

    399206399

    Returns: { 39, 0, 0, 22, 0, 0, 3, 0, 0, 0, 1, 479, 0, 112, 0, 0, 0, 0, 0, 0 }

  20. {645116, 36570080, 80994800, 136948, 88740000, 94725924, 857, 859, 51614982, 301842, 77079564, 12846594, 119110, 94472820, 277, 1, 99992980, 44370000, 19998596, 442986, 731, 20679148, 55658344, 409, 92, 27829172, 47362962, 73140160, 52277, 484476, 45260, 50324, 118320, 82716592, 14790000, 292, 408, 469, 901}

    621179999

    Returns: { 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 407, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 124, 0, 2, 0, 289, 0, 0 }

  21. {950, 54188904, 39200, 27252100, 62025520, 210256, 98, 282310, 458, 120, 322553, 11, 370, 727, 781, 234900, 118, 75590880, 80740660, 1, 9537, 15680000, 81756300, 240, 82285196, 83755800, 348, 353400, 9031539, 44161200, 62611560, 88322400, 91804106, 74881, 87910, 226320, 78400000, 652, 272, 131446, 5450420, 27918600, 45902053, 645480, 37795440}

    377954399

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 119, 0, 0, 0, 942, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 166, 0, 0, 0, 0, 0, 0, 0, 0, 1 }

  22. {51499140, 691, 48386646, 36777312, 73554624, 862, 768042, 216144, 21257400, 68391540, 541053, 79371873, 81702432, 82941975, 85029600, 93061116, 96773292, 472, 896, 711, 37425, 810, 30081, 419580, 674325, 46530558, 63384408, 67496880, 94454340, 613085, 148, 182664, 23613585, 564, 1, 75, 675, 322608, 785, 365769, 2657175, 27647325, 48840, 37, 513, 12874785, 33748440, 42514800}

    995303699

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 0, 74, 8, 998, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0 }

  23. {188955, 30192750, 1700595, 54975875, 59520825, 765, 670950, 1, 2199035, 90578250, 23664, 10064250, 48, 205, 994, 3485}

    543469499

    Returns: { 0, 2, 0, 0, 0, 0, 14, 993, 0, 5, 0, 2, 0, 0, 674, 0 }

  24. {2091, 528066, 552767, 2055453, 6074016, 44880, 1, 922, 26802972, 30831795, 467232, 79433376, 172, 45674958, 489, 627, 657, 301713, 310714, 4880500, 68327000, 88610718, 92495385, 97184256, 98741552, 584, 72900, 942, 893, 33166020, 80408916, 547, 660, 405, 1525920, 542536, 63963156, 762, 39044, 66332040, 76041504, 57984960, 91349916, 51, 509257, 285138, 185592}

    647467694

    Returns: { 982, 0, 0, 14, 0, 0, 50, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0 }

  25. {98475696, 348, 99740880, 99810576, 1484964, 1, 91410228, 186, 722, 36455, 70034, 189375, 247, 214578, 143, 416075, 82498, 994704, 27009906, 32669208, 32825232, 391, 317, 41638740, 51156, 45705114, 48253426, 30233196, 3128, 24935220, 273, 375, 49905288, 67694, 97092, 13879580, 935, 60466392, 54019812, 92784725, 181, 83277480, 60346, 96506852, 65338416}

    689329871

    Returns: { 6, 0, 0, 0, 0, 390, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 2, 7, 0, 0, 0, 0, 0, 0, 317, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  26. {361120, 895, 773280, 1, 12372480, 592, 37117440, 48390080, 74234880}

    668113919

    Returns: { 0, 863, 15, 894, 2, 0, 1, 0, 8 }

  27. {214926, 873, 188680, 45682344, 21707280, 890, 1, 317, 6287556, 2583, 330924, 35695044, 652, 876, 44012892, 754720, 88025784, 94567440, 43414560, 76931316, 369, 407044, 86829120, 88439337, 91364688, 436, 71390088, 841, 108252, 566588, 782649, 516840}

    792232055

    Returns: { 0, 0, 0, 0, 0, 0, 435, 0, 6, 0, 18, 0, 0, 0, 1, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 758, 0, 0, 0, 0, 0, 0 }

  28. {12752640, 453, 717600, 714, 723, 762, 436639, 845, 821, 121240, 655979, 2125440, 22320456, 28863076, 48274380, 50920800, 53057550, 56690400, 3, 86589228, 741, 280, 1787940, 9127776, 53136, 26528775, 432, 58305, 33558, 1419, 800, 1, 4250880, 328422, 36783264, 10184160, 38257920, 52850151, 55453153, 73022208, 73566528, 76515840, 76786866, 96548760, 354699, 328242, 931, 673569, 893970}

    229547519

    Returns: { 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 143, 0, 0, 0, 0, 0, 39, 0, 122, 0, 0, 0, 0, 2, 2, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0 }

  29. {8312997, 41410096, 43983216, 62357568, 478, 664, 28308672, 3145408, 86613504, 87966432, 24390288, 97561152, 204, 102, 17264, 7330536, 161000, 32436, 173992, 4454112, 21991608, 48780576, 56617344, 43306752, 49877982, 93380000, 679, 6, 68, 7616, 99755964, 50592, 1, 3354, 2710032, 395857, 161}

    703731455

    Returns: { 0, 0, 1, 0, 0, 0, 0, 0, 0, 7, 0, 0, 158, 1, 0, 2, 0, 225, 0, 0, 1, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 5, 0, 0, 0, 0 }

  30. {65003400, 66388140, 92018556, 34914236, 74444, 97849142, 20431296, 30744, 17, 9, 728, 200392, 1, 1214582, 4369, 851, 56, 2844, 96119, 481936, 603359, 7747488, 11566464, 828996, 5107824, 54232416, 69828472, 347, 6500340, 8442, 43441848, 48924571, 78947830, 81725184, 86883696, 117, 91378752, 834, 57832320, 503, 30459584, 18, 296, 2553912, 85995, 40862592}

    490351103

    Returns: { 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 8, 0, 0, 0, 0, 897, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 157, 0, 1, 0, 1 }

  31. {13676850, 21657688, 22861440, 75, 31293288, 47739780, 627, 46812, 200598, 56555970, 73184520, 84672315, 1, 16934463, 82389120, 120960, 81870750, 998, 44919, 2763, 2729025, 7620480, 315, 884070, 45722880, 86630752, 91445760, 867, 93879864, 424, 15688, 95479560, 294690, 95737950, 634, 32617, 63, 69975, 1367685, 3, 14636904, 169, 198442, 338130, 188, 7823322, 8238912}

    640120319

    Returns: { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 62, 0, 0, 0, 0, 0, 2, 383, 0, 1, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0 }

  32. {99075600, 11310, 873080, 8256300, 13608000, 27216000, 1, 978, 51809550, 54432000, 62702416, 16512600, 30240, 83206656, 389456, 964, 950, 38000, 41603328, 12810204, 120, 22990000, 303600, 45980000, 85561840, 926, 435, 88954800, 797070, 6716, 7560, 866736, 907200, 23, 789, 4536000, 33025200, 660, 32349, 91960000}

    163295999

    Returns: { 0, 0, 0, 0, 1, 1, 119, 0, 0, 2, 0, 0, 29, 0, 0, 0, 0, 0, 0, 0, 62, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 4, 0, 0, 2, 0, 0, 0, 0 }

  33. {83736688, 4176, 375570, 87381504, 436020, 751, 688, 3276900, 94643640, 118, 553064, 9656766, 2152, 70792192, 89387775, 762, 112, 538, 16, 225, 507, 431825, 52430400, 560082, 78912720, 92583000, 182250, 94192, 7281792, 9900, 3640896, 47321820, 67597362, 584, 1, 53767872, 702, 3186, 260064, 438584, 657606, 14563584, 646, 46291500, 50437160, 43690752, 22, 1379538, 71507280}

    786433535

    Returns: { 0, 0, 0, 8, 0, 0, 377, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 15, 0, 0, 0, 13, 0, 0, 2, 0, 0, 0, 1, 0, 0, 0 }

  34. {6046500, 1, 278, 434044, 982, 12093000, 96744000, 8340, 48372000, 4170, 96791812}

    290231999

    Returns: { 1, 277, 14, 0, 0, 3, 2, 724, 1, 1, 0 }

  35. {66690, 206244, 1795013, 93366000, 95792060, 97939296, 306, 1, 6669000, 190, 12626640, 707, 620060, 266760, 13320580, 95, 163183, 44644320, 331, 313908, 8161608, 328055, 46683000, 19760, 47896030, 563, 63133200, 79923480, 455, 95147, 86828724, 89288640, 721}

    746927999

    Returns: { 3, 0, 0, 7, 0, 0, 0, 94, 6, 350, 0, 0, 0, 24, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  36. {20918486, 681, 80593668, 90789120, 197, 426, 279226, 33794, 62755458, 1, 717, 140, 932844, 69030456, 77168000, 88722424, 67257960, 280, 84804, 15762, 298, 83172, 1513152, 2555484, 27186, 19292000, 30263040, 145734, 89320, 265636, 17888388, 1484000, 29292534, 34515228, 58585068, 71553552, 14840, 382, 895, 742, 494935, 38584000, 44361212, 72598760, 554, 26726490}

    771679999

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 139, 0, 1, 0, 0, 9, 0, 0, 52, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 99, 0, 0, 0, 0, 1, 0, 0, 0, 0 }

  37. {98054145, 61, 419, 8, 433, 643, 138127, 380033, 1264896, 8740759, 1908424, 126309, 213, 34587, 17481518, 32684715, 34351632, 32, 6912, 326952, 5059584, 35417088, 1, 478, 63659736, 63814674, 68703264, 31907337, 70834176, 477106, 84353616, 87407590}

    637507583

    Returns: { 0, 0, 0, 3, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 215, 182, 0, 6, 1, 7, 0, 0, 0, 0, 0, 8, 0, 0, 0 }

  38. {147323, 544149, 649, 26, 3473340, 267243, 6946680, 587, 13893360, 17103552, 27786720, 60400539, 83360160, 68414208, 72482916, 1, 687, 4758}

    333440639

    Returns: { 0, 0, 0, 182, 1, 0, 1, 0, 1, 0, 2, 0, 3, 0, 0, 25, 0, 729 }

  39. {1127555, 36081760, 40440272, 410, 87344, 211, 86697, 44822349, 68085248, 4510220, 899, 181000, 9020440, 216832, 54942426, 72163520, 1, 75839000, 352, 724, 80880544, 106, 2717, 209, 56442500, 87787350, 89644698, 90308, 283185, 436051, 740, 95865520, 351, 344840, 809}

    649471679

    Returns: { 3, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 3, 0, 0, 8, 208, 0, 0, 0, 0, 0, 414, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  40. {93945600, 932, 521920, 11946456, 116, 14872176, 95571648, 97212920, 1, 694, 107184, 144918, 2986614, 534, 4986, 3131520, 4941280, 30373920, 64080, 34588960, 18, 792, 61766, 66387200, 74360880, 890, 2898360, 75357360, 6, 943, 181368, 603520, 747, 33193600, 47785824, 50162112, 4, 12540528, 69177920, 585620, 91121760}

    764573183

    Returns: { 0, 0, 0, 3, 0, 0, 7, 0, 5, 0, 0, 0, 3, 0, 598, 0, 0, 0, 0, 0, 276, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }

  41. {17014, 35372106, 61, 636682, 36, 87444, 1684386, 5053158, 20958240, 8041728, 48992976, 24496488, 30852, 31917060, 160140, 56292096, 78311886, 83832960, 47, 251304, 855, 475380, 72257760, 95751180, 942, 70744212, 940, 85619600, 26103962, 97985952, 347, 42809800, 873260, 709, 41916480, 9032220, 44225, 10479120, 296, 1}

    251498879

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 19, 0, 0, 0, 0, 0, 0, 0, 928, 0, 0, 0, 0, 0, 11, 0, 1, 0, 0, 1, 0, 46 }

  42. {284888, 338845, 211172, 75718, 344640, 373305, 660822, 73784828, 309399, 79611840, 1, 401, 131, 262, 419727, 22806576, 30030426, 52859820, 70652224, 90091278, 550, 91226304, 479, 88846590, 83945400, 168844, 60951603, 453, 483, 615, 93175902, 718, 11403288, 45613152, 61791, 45355082, 90710164, 596, 723, 884}

    912263039

    Returns: { 0, 0, 53, 0, 0, 0, 0, 0, 0, 0, 130, 0, 1, 805, 0, 1, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 }

  43. {686080, 91036980, 87203844, 620, 266190, 934, 2839290, 22984038, 26472528, 42497280, 10115220, 213, 18318, 8824176, 21248640, 4, 51681280, 71352320, 189, 88263, 68142960, 45968076, 309, 932, 79417584, 490232, 192, 980464, 44548, 84994560, 2560, 104780, 74, 91936152, 824, 193270, 27129732, 49749, 137088, 59619820, 9043244, 403760, 1, 251, 50443470, 6460160}

    397087919

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 232, 0, 0, 0, 0, 0, 0, 0, 525, 4, 1, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0 }

  44. {1880013, 42188778, 78753060, 242592, 468350, 519, 84377556, 740154, 1, 11280078, 93201650, 797, 456, 475, 140130, 51, 9819040, 45120312, 9843, 843, 89264, 74233152, 90240624, 22560156}

    992646863

    Returns: { 5, 0, 0, 0, 0, 0, 0, 0, 50, 1, 0, 0, 0, 0, 0, 192, 0, 1, 190, 0, 0, 0, 10, 1 }

  45. {74480, 1013824, 8110592, 638976, 24331776, 408, 257115, 29110725, 16, 79872, 6944, 85, 101, 593, 666, 53025, 47284224, 72841440, 92712305, 60386040, 94568448, 314279, 59596810, 1, 182, 97327104, 98217930, 59670, 18542461, 150878, 656370, 51112880, 115218, 196588, 58221450, 23642112, 70513416, 93982800, 476, 915, 34680, 323, 152, 18796560, 192}

    378273791

    Returns: { 0, 0, 0, 36, 0, 0, 0, 0, 11, 7, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 415 }

  46. {148, 571, 2279200, 18778, 27635226, 72934400, 36467200, 82, 32782, 294636, 65120, 4558400, 1, 74, 63936012, 82905678}

    802278399

    Returns: { 439, 0, 1, 0, 0, 10, 1, 0, 0, 0, 34, 7, 73, 1, 0, 0 }

  47. {17838144, 83347440, 97849140, 72716, 660, 196, 95904, 172920, 525532, 9716690, 36, 96086, 937, 68016830, 211, 449, 74100012, 31858, 79270950, 165846, 41673720, 959, 1, 108, 35676288, 71352576, 8919072}

    570820607

    Returns: { 1, 0, 0, 0, 0, 0, 92, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35, 887, 1, 7, 1 }

  48. {62480, 780346, 37456608, 9364152, 4682076, 1, 18728304, 74913216, 973, 142}

    973871807

    Returns: { 0, 5, 1, 1, 1, 972, 1, 12, 801, 0 }

  49. {80598240, 40299120, 32310495, 74064416, 336, 475, 96096, 521, 83729520, 300200, 13433040, 412, 88528320, 31095, 90309219, 98402304, 28, 99, 1008, 402524, 2697552, 203, 371385, 24600576, 29509440, 37032208, 50469664, 25234832, 27076, 100032, 1, 45, 917, 160979, 10296, 452592, 4, 30103073, 10770165, 49201152, 50733800, 64620990}

    688816127

    Returns: { 0, 0, 0, 0, 285, 0, 255, 0, 0, 0, 0, 0, 0, 0, 0, 6, 11, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 6, 0, 0, 1, 0, 0 }

  50. {857, 335087, 204820, 2457840, 48922702, 84541061, 7373520, 913, 88482240, 44241120, 252, 820787, 14747040, 97845404, 1, 220}

    442411199

    Returns: { 0, 0, 11, 2, 0, 0, 1, 0, 4, 1, 0, 0, 2, 0, 219, 930 }

  51. {360, 7776, 733, 1, 352573, 2766960, 5533920, 51280515, 83559801, 22135680, 622, 43920, 62674560, 18, 357730, 93036894, 585, 634, 53890, 358605, 424826, 11067840, 830, 88542720, 404352, 94082990}

    265628159

    Returns: { 121, 0, 0, 17, 0, 1, 1, 0, 0, 3, 0, 62, 0, 19, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0 }

  52. {785, 15000, 19, 123200, 9893205, 23443680, 37380000, 70331040, 14877, 74760000, 79145640, 275, 102050, 28952000, 39572820, 30, 1, 293046, 5340000, 19786410, 57904000, 338, 4959}

    158291279

    Returns: { 0, 0, 260, 0, 1, 0, 0, 0, 664, 0, 1, 0, 0, 0, 1, 0, 18, 0, 0, 1, 0, 0, 2 }

  53. {22626648, 12738786, 55619190, 81893340, 84208896, 19079424, 85346337, 89171502, 90506592, 11123838, 28448779, 798, 161, 921, 52095, 38158848, 521, 42104448, 1, 45253296, 57973754, 69863222, 76317696, 21052224, 30393, 23112, 80352, 115, 838, 24, 454, 588, 84847, 119834, 127573, 9539712, 90346, 96, 661, 298116, 596232, 27297780, 61478, 63550403}

    992130047

    Returns: { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 587, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 506, 0, 0, 0, 1, 0, 0, 0, 1, 15, 0, 0, 0 }

  54. {1}

    14398711

    Returns: { 14398711 }

  55. { 10, 1 }

    1

    Returns: { 0, 1 }

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

    939524095

    Returns: { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13 }

  57. { 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29 }

    1000000000

    Returns: { 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 52631578, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  58. { 147323, 544149, 649, 26, 3473340, 267243, 6946680, 587, 13893360, 17103552, 27786720, 60400539, 83360160, 68414208, 72482916, 1, 687, 4758 }

    333440639

    Returns: { 0, 0, 0, 182, 1, 0, 1, 0, 1, 0, 2, 0, 3, 0, 0, 25, 0, 729 }

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: