Statistics

Problem Statement for "ChangePurse"

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. If multiple ways exist to give Johnny change, return the one with the most coins of the highest denomination. If multiple ways exist which have the most coins of the highest denomination, return the one with the most coins of the second-highest denomination, and so on. 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, and even though it does not produce the fewest coins, the first way is preferable because it contains a high-valued 25 cent piece.

You will be given a int[] coinTypes, which will be a list containing the value of each type of coin in the given 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:
ChangePurse
Method:
optimalCoins
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] optimalCoins(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 1000000, 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 1000000000, inclusive.

Examples

  1. {1,25,10}

    49

    Returns: { 24, 1, 0 }

    The example from the problem statement.

  2. {1,7}

    49

    Returns: { 49, 0 }

    Note that {7,6} is an invalid return because even though it equals 49 cents, and it allows all values between 1 and 49, it would allow multiple ways to make 7 cents. This is the thing that Johnny fears the most.

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

    390700799

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

  4. {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288}

    1048575

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

  5. {11,5,10,1}

    109

    Returns: { 9, 0, 0, 10 }

  6. {14796, 236736, 839364, 37572, 639, 473472, 1, 751, 970, 301, 761450, 939300, 16680, 483720, 230679, 945392, 946944, 419682, 259095, 322, 236348, 238293, 472696, 518190, 922716, 953172, 967440, 556, 249, 678, 606, 822}

    373095935

    Returns: { 15, 1, 0, 0, 0, 1, 821, 0, 0, 0, 0, 0, 0, 0, 0, 0, 393, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17 }

  7. {103, 935, 559440, 596806, 31080, 470378, 894795, 38522, 242374, 99568, 907, 958, 84, 910, 298680, 695, 525875, 479, 279720, 390976, 727122, 1, 337, 254, 158727, 454, 770440, 793635, 596, 414956, 796544, 248080, 886, 829912, 848120, 535845, 14224, 896040, 940756, 570, 398272, 781952, 992320, 601}

    959835519

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 253, 0, 55, 0, 0, 0, 0, 0, 0, 1204, 0, 0, 0, 0, 0, 6, 0, 0, 0, 1, 0, 0, 0 }

  8. {150463, 22736, 886704, 902778, 1, 379, 68302, 230265, 253106, 460530, 819624, 759318, 667, 731, 916, 236785, 717228, 947140, 156750, 923, 2193, 921060, 940500, 209, 116, 707}

    926586359

    Returns: { 0, 0, 0, 0, 730, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 104, 1005, 0, 0, 0, 0 }

  9. {81056, 95480, 82248, 96138, 460320, 596, 627936, 686244, 338436, 644820, 686592, 822480, 52788, 844, 668360, 676872, 513920, 920640, 1, 140, 162112, 961380, 423, 660, 480690, 704, 972672, 654, 298, 249, 357, 822, 149, 42912, 71910}

    985316735

    Returns: { 1, 0, 0, 0, 0, 135, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 148, 0, 5, 0, 0, 0, 0, 0, 1012, 0, 1, 0, 0, 0, 1, 0, 0 }

  10. {485604, 501, 811, 261, 114240, 121401, 1, 562023, 720360, 791776, 913920, 956910, 971208, 979600, 180090, 97960, 191382, 987, 197944, 872, 5712, 158, 34, 706920, 456960, 685, 48980, 353460, 360180}

    788712959

    Returns: { 0, 0, 0, 0, 3, 0, 33, 0, 0, 0, 862, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 0, 167, 0, 1, 0, 0, 0, 0 }

  11. {691966, 11310, 250488, 371, 279220, 852992, 976458, 500976, 607, 60928, 13, 41344, 426496, 31311, 436296, 72716, 385090, 469, 213, 443, 652, 896, 1, 345983, 165376, 417872, 539856, 218148, 622050, 676272, 770180, 837660, 872592, 992256, 338136, 574, 772, 794, 646, 711, 208936, 682560, 169068, 835744, 325486}

    758282447

    Returns: { 0, 0, 0, 195, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 370, 0, 0, 0, 0, 1, 0, 0, 0, 0, 868, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  12. {232078, 881, 104429, 937, 332137, 358479, 393231, 220, 326880, 1, 277, 681, 171160, 570633, 639, 16940, 716958, 786462, 664274, 855800, 897820, 696234, 943, 260640, 85580, 720, 626574, 108960, 980640, 20, 959, 21087}

    213094199

    Returns: { 0, 0, 0, 0, 0, 0, 0, 388, 0, 19, 0, 0, 4, 0, 0, 0, 0, 0, 0, 248, 0, 0, 0, 0, 1, 0, 0, 0, 0, 10, 0, 0 }

  13. {36096, 293160, 94, 420, 237, 649, 216576, 603, 14220, 866304, 895860, 970830, 489995, 979990, 485415, 1, 950, 108288, 586320}

    993650687

    Returns: { 2, 0, 383, 0, 0, 0, 3, 0, 0, 1146, 0, 0, 0, 0, 0, 93, 0, 1, 0 }

  14. {703, 532, 86496, 366016, 731, 649110, 792, 842112, 957352, 875, 15824, 883008, 514596, 923136, 122760, 281, 441504, 610456, 461568, 958, 968, 732032, 93568, 636, 678, 724104, 859320, 87208, 617136, 147168, 811125, 1, 3934, 16, 224, 361, 991, 92416, 601, 739328, 369664, 120684, 787476, 257298}

    502431551

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 568, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 15, 0, 13, 656, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  15. {291, 168, 846228, 894825, 987272, 754, 997248, 430, 473, 524, 2, 1568, 37972, 232232, 708, 249312, 292314, 863, 181248, 498624, 423114, 584628, 399812, 635808, 678540, 49, 724992, 888, 755112, 1, 10556, 727, 862, 317904, 339270, 178965, 799624, 57116, 125852, 377556, 696696}

    172083911

    Returns: { 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 376, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 246 }

  16. {196425, 237200, 326, 507256, 785700, 948800, 1, 47440, 80, 873, 253628, 474400}

    870049599

    Returns: { 0, 1, 0, 0, 0, 916, 79, 4, 592, 0, 0, 1 }

  17. {611, 499653, 999306, 9, 249, 227, 1, 293664, 612, 681156, 642, 219055, 307944, 480928, 43992, 548130, 452, 588, 658854, 693, 60116, 438110, 744120, 876220, 31005, 227052, 1323, 85905, 859050, 880992, 644, 43811, 45, 120232, 961856, 274065, 329427, 923832, 636222, 363}

    669451775

    Returns: { 0, 0, 0, 0, 0, 0, 451, 0, 0, 0, 0, 0, 0, 1, 0, 0, 132, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 695, 0, 0, 0, 0, 0 }

  18. {12852, 18540, 684, 222678, 60, 285120, 540, 344352, 539955, 667440, 732564, 850896, 890712, 71280, 172176, 126412, 612, 374, 179985, 195, 570240, 688704, 1, 267, 593, 379236, 682, 425448, 251432, 564014, 758472, 272}

    84965759

    Returns: { 0, 0, 0, 0, 8, 1, 131, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 148, 0, 59, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  19. {148234, 325593, 651186, 279, 935088, 952320, 3864, 240, 24, 467544, 541, 119040, 444702, 476160, 108531, 1}

    106659839

    Returns: { 0, 0, 0, 0, 0, 111, 0, 495, 9, 0, 0, 3, 0, 1, 0, 23 }

  20. {54, 866700, 875776, 940614, 963738, 8, 1339, 919, 261600, 132070, 1, 483, 313538, 759, 763230, 783783, 816072, 446, 819, 2538, 164970, 6, 281, 218944, 261261, 709044, 784800, 480, 660350, 2488, 40170, 103, 90, 48150, 35694, 354522, 433350, 437943, 659880}

    306811799

    Returns: { 0, 353, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 534, 8, 0, 0, 1, 0, 0 }

  21. {29210, 58420, 350520, 708072, 720035, 230, 42355, 1, 59006, 985, 236024, 163, 701040}

    929579039

    Returns: { 1, 5, 1, 0, 0, 126, 0, 229, 0, 0, 0, 0, 1325 }

  22. {716870, 405822, 358435, 318199, 621960, 403326, 683, 735244, 613, 17365, 271834, 385, 823, 346983, 566, 170145, 510435, 995, 258990, 977, 776970, 806652, 811644, 533, 937710, 551, 288, 219, 86330, 123975, 310980, 636398, 183287, 31098, 815502, 272736, 97, 115, 867825, 194, 104190, 545472, 347, 775266, 829473, 794, 129211, 1, 134442, 733148}

    430441379

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 553, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 444, 0, 0, 0, 0, 0, 0, 0, 96, 0, 0 }

  23. {336986, 650760, 2535, 673972, 780780, 37, 38682, 928368, 23014, 965871, 285, 431, 1, 174096, 325380, 775200, 270146, 128851, 108460, 773106, 110, 518, 186, 5, 307, 845, 321957, 522288, 598364, 338, 96900, 387600, 269, 922, 991, 510365, 540292}

    848591039

    Returns: { 0, 1303, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 1, 0, 0, 0, 2, 0, 985, 0, 0, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  24. {741312, 815544, 458, 594, 434, 234, 546084, 203886, 45, 1, 23166, 370980, 547420, 136770, 741960, 163, 760320, 874224, 914850, 986048, 457425, 723, 692, 299730, 370656, 54742, 246512, 213, 952, 40424, 606360, 407772, 696654, 729368, 899190, 952000, 535, 15840, 109278, 101, 582, 591, 126720, 364684, 813660, 101943, 81366, 291, 798, 820620}

    141089111

    Returns: { 0, 172, 0, 0, 0, 0, 0, 1, 0, 722, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0 }

  25. {151848, 1, 6, 4218, 83232, 911088, 153, 147392, 303696, 749088, 869, 736960, 784}

    664183151

    Returns: { 1, 5, 702, 35, 0, 728, 0, 0, 2, 0, 0, 0, 0 }

  26. {985, 545454, 534, 200, 181818, 262820, 427520, 623689, 392000, 682682, 269434, 916, 53440, 962, 49000, 784000, 1, 35244, 961, 213760, 525640, 563904, 340, 855040, 52514, 2, 808302, 331, 974165, 80, 847, 4}

    268482559

    Returns: { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 313, 0, 1, 0, 0, 0, 667, 0, 19 }

  27. {409818, 522720, 548208, 898, 73440, 14976, 564, 153, 623, 565684, 587520, 24480, 124, 873, 501, 21450, 608844, 703872, 426024, 146880, 819636, 852048, 8577, 104, 293760, 1, 523197, 948600, 9, 261360, 432, 22, 316200, 63240}

    937094399

    Returns: { 0, 0, 0, 0, 1, 0, 0, 159, 0, 0, 1594, 2, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 8, 0, 0, 16, 0, 0, 0, 0, 0 }

  28. {1752, 486864, 973728, 6, 7, 3381, 243432, 121716, 1, 40572}

    43817759

    Returns: { 0, 1, 44, 0, 482, 11, 1, 1, 6, 2 }

  29. {374680, 772800, 820800, 456203, 146, 456, 626, 5808, 32912, 98736, 511290, 617710, 872781, 992580, 997776, 973, 659456, 198516, 912406, 585, 22040, 156816, 313632, 559746, 691152, 896, 771, 312, 57524, 1, 732320, 749360, 58, 22, 88, 736, 932, 52272, 61771, 136800, 737, 2313, 966, 223, 166296, 410400, 578424, 627264}

    793488959

    Returns: { 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 3, 65, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1264 }

  30. {664, 163520, 178752, 559821, 650231, 592424, 690092, 742633, 1, 112, 977, 25440, 127092, 799, 612208, 762552, 763200, 41, 598, 1988, 254184, 12587, 817600, 934830, 377802, 755604, 693408, 536256, 992, 941, 81760, 714, 480, 59584, 103870, 14, 29792, 76160, 345046, 224, 453, 560}

    886431167

    Returns: { 0, 0, 2, 0, 0, 0, 0, 0, 13, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1652, 0, 0, 0, 0, 0, 2, 0, 7, 1, 0, 0, 132, 0, 0 }

  31. {23868, 242, 71604, 119652, 328152, 859248, 957216, 984456, 507, 82038, 429624, 1, 3, 234, 214812, 239304}

    139198175

    Returns: { 2, 0, 2, 0, 0, 161, 0, 0, 0, 0, 1, 2, 77, 101, 1, 0 }

  32. {278, 739, 752, 30, 949, 472538, 211152, 26688, 422304, 8896, 796, 427008, 610740, 731610, 167634, 55878, 139, 106752, 358722, 739968, 844608, 424, 213504, 21060, 502902, 717444, 854016, 1, 517, 945076}

    151160831

    Returns: { 31, 0, 0, 0, 0, 0, 0, 3, 0, 2, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 176, 138, 0, 0 }

  33. {582256, 646, 304, 604, 238, 76860, 210140, 331200, 662400, 110240, 665, 62288, 490, 120, 230580, 41400, 498864, 498304, 20468, 156800, 531658, 661440, 567450, 166288, 958, 769274, 840560, 234, 922320, 520, 940800, 1, 996608, 165600, 777784, 997728, 10, 183, 916, 82800, 113490}

    559727999

    Returns: { 0, 0, 0, 0, 0, 0, 0, 1, 844, 0, 0, 0, 0, 344, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 1, 0, 0, 11, 0, 0, 1, 0 }

  34. {795, 5536, 26, 915, 18590, 60840, 49140, 2, 119700, 162235, 369000, 383936, 478800, 505995, 949, 95984, 455, 8, 420, 239400, 276800, 191968, 619305, 654810, 706420, 393120, 738000, 767872, 425880, 786240, 830400, 676, 4500, 851760, 957600, 648940, 1, 112, 180, 457}

    687245439

    Returns: { 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 0, 13, 0, 0, 0, 1, 0, 0, 0, 0, 0, 894, 0, 0, 0, 0, 0, 0, 0, 0, 1, 856, 0, 0 }

  35. {899, 48480, 387840, 448601, 1, 543, 766700, 973628, 647, 286621, 502275, 606, 697, 303, 917, 6060, 36960, 62418, 153340, 245756, 554400, 193920, 624180, 698, 802, 12120, 110880, 486814, 573242, 583528, 737268, 775680, 480, 897202}

    464632319

    Returns: { 0, 3, 1, 0, 302, 0, 0, 0, 0, 0, 0, 9, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 598, 0, 0 }

  36. {89880, 390588, 519, 887040, 70, 961, 269, 9240, 1, 156600, 861021, 867, 221760, 65098, 626400, 10, 280, 313200, 676830, 123003, 719040, 781176, 946585, 770, 73920, 5400}

    474566399

    Returns: { 0, 0, 0, 534, 10, 0, 0, 7, 9, 0, 0, 0, 3, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 11, 2, 0 }

  37. {784, 462000, 670, 77000, 2780, 1, 440, 911, 704634, 924000, 354, 15400, 231000, 258540, 57024, 298776, 446890, 597552, 50331, 726484, 513216, 821632, 410816, 870916, 836, 20, 57, 893780, 352}

    773387999

    Returns: { 0, 1, 0, 2, 0, 19, 34, 0, 0, 836, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0 }

  38. {128115, 101400, 259374, 357680, 437080, 526318, 725052, 811200, 874160, 940416, 33800, 129687, 778122, 561212, 351, 362526, 786, 6760, 646758, 715360, 426, 178840, 1, 231012, 13, 490, 25668, 26, 653166, 294515, 311, 215586, 405600, 693036, 768690, 883545, 263, 992, 806, 124, 609, 811, 2561}

    313123199

    Returns: { 0, 3, 0, 0, 0, 0, 0, 385, 0, 0, 2, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 12, 0, 1, 0, 0, 259, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  39. {910, 56160, 1, 108882, 199818, 3132, 112320, 435528, 492310, 673920, 871056, 217764, 20400, 336960, 979200, 984620, 999090, 180, 6, 18720, 653, 244800, 526, 300}

    884856959

    Returns: { 0, 1, 5, 0, 0, 0, 2, 0, 0, 1312, 0, 0, 0, 1, 0, 0, 0, 103, 29, 2, 0, 0, 0, 0 }

  40. {144000, 239859, 886, 472270, 533390, 689010, 180, 893964, 176157, 295, 90, 1, 966, 285600, 41005, 285292, 517776, 544, 830, 106380, 965, 142646, 288000, 943, 480960, 571200, 576000, 819, 660933, 944540, 959436, 984120, 529, 528471, 570584, 746, 5010, 744660, 106678, 148994, 258888, 30, 72000, 919, 40800}

    225215999

    Returns: { 1, 0, 0, 0, 0, 0, 399, 0, 0, 0, 1, 29, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 390, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0 }

  41. {151050, 216, 40, 901, 710955, 190, 337, 786, 1, 67620, 302100, 405720, 733860, 8050, 966, 811440, 414222, 99576, 7, 202860, 234889, 828444, 852600, 3480, 896184, 990150, 604200, 593759, 322, 33810, 45, 40770, 3885}

    310781519

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 6, 2, 0, 1, 0, 0, 34, 382, 0, 0, 45, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0 }

  42. {268500, 351582, 68, 888160, 444080, 244, 534720, 537000, 89205, 338099, 95, 33, 50226, 66, 486528, 596904, 442519, 676198, 375, 778, 535230, 578160, 22100, 703164, 781000, 795600, 885038, 896, 47, 960, 979, 1, 5016, 14899, 264, 17080, 536364, 963164, 973056, 539, 88400, 19272, 607, 481582, 38544, 192720, 781}

    523812959

    Returns: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 905, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32, 0, 0, 72, 0, 0, 0, 0, 0, 0, 1, 0, 0, 4, 2, 0 }

  43. {9, 371, 79023, 365500, 400860, 774, 153, 60787, 538560, 80172, 801, 731, 573516, 731000, 820440, 948276, 1, 698544, 972592, 269280, 801720, 306, 486296, 205110, 89, 3969, 40086, 91375}

    801719999

    Returns: { 16, 0, 0, 0, 1, 0, 1, 0, 0, 4, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 999, 130, 0, 0, 0, 0, 1, 0 }

  44. {40950, 608, 52312, 251015, 362806, 503, 502030, 572565, 823, 114513, 59100, 295500, 315, 325797, 409500, 858600, 889304, 977391, 591000, 1, 829, 5400, 204750, 566, 287, 298528, 158752, 725612, 968, 819000, 895584, 952512, 8190, 9, 591}

    787058999

    Returns: { 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 0, 1, 0, 0, 0, 0, 8, 0, 0, 1, 0, 0, 0, 0, 0, 0, 960, 0, 0, 4, 34, 0 }

  45. {705960, 352980, 143, 89232, 763182, 766878, 803088, 821610, 45645, 429, 537, 798, 117660, 410805, 589248, 363, 392, 673, 11154, 49104, 674240, 684255, 535392, 22308, 792, 1, 212, 52635, 109026, 267696, 337120}

    284293151

    Returns: { 0, 0, 2, 2, 0, 0, 353, 0, 0, 25, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 142, 0, 0, 0, 2, 0 }

  46. {634, 192, 7267, 988, 29068, 62016, 116272, 493, 14534, 466336, 307768, 481008, 697632, 429110, 527, 380400, 760800, 868224, 169, 26, 232544, 472006, 1, 986, 912050, 923304, 962016, 944012, 492507, 517, 528, 54723, 85822, 182410, 465088, 858220, 930176, 985014, 713}

    785998719

    Returns: { 0, 0, 1, 0, 3, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 0, 1, 0, 168, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 844, 0, 0 }

  47. {962850, 138432, 210, 240, 913, 69216, 965760, 968760, 80730, 1, 603, 989100, 4, 243, 342, 766, 877, 120720, 241440, 276864, 481425, 82764, 443232, 530838, 543609, 13851, 720017, 805, 188580, 1624, 482880, 553728, 187, 315, 19720, 40, 60401, 49455, 402804, 754320, 802256, 805266, 130, 886464, 618, 48258, 744625, 910404, 946560, 525}

    364091519

    Returns: { 0, 0, 0, 502, 0, 0, 376, 0, 0, 3, 0, 0, 9, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  48. {965024, 56, 699312, 712062, 882777, 168, 357213, 179, 798132, 408, 217728, 501, 435456, 77, 571, 265, 65912, 135150, 85344, 569, 66511, 1, 349656, 6981, 511700, 482512, 512064, 525891, 227, 889, 8064, 602, 72576, 593208, 714426, 102, 870912}

    238629887

    Returns: { 0, 2, 0, 0, 0, 47, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 55, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 2, 0, 0, 0, 273 }

  49. {952820, 112, 845748, 15939, 965600, 71, 483, 450087, 43310, 96560, 66304, 382832, 482800, 660450, 737, 191416, 792360, 771060, 638028, 385530, 765664, 899388, 900174, 958, 142, 573, 95708, 131186, 31262, 66030, 340, 111, 94350, 1, 262372, 759, 355, 396180, 449694, 937860, 154, 281916, 426, 747, 468930, 476410, 198090, 729344, 787116, 940401}

    127569959

    Returns: { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 160, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 70, 0, 0, 0, 1, 0, 0, 0, 0, 154, 0, 0, 0, 1, 0, 0, 0 }

  50. {598, 195024, 780096, 865, 377856, 308320, 911710, 96063, 455855, 864567, 1, 188928, 213, 984, 576472, 702, 956, 675563, 835380, 328, 119340, 616640, 755712, 47232, 833, 41}

    285659135

    Returns: { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 40, 1, 0, 47, 0, 0, 0, 0, 0, 2, 0, 0, 377, 3, 0, 7 }

  51. {794, 385920, 206424, 492480, 529618, 621376, 355218, 146, 1, 38836, 133693, 451178, 654192, 710436, 746496, 606690, 246240, 41040, 771840, 807070, 269, 378, 233920, 483, 467840, 842, 121338, 582002, 825696, 240, 488, 118406, 373248, 861672, 708, 403535, 60, 902356, 1536, 935851, 984960, 511, 12, 667, 860, 64320, 215418, 518}

    390044159

    Returns: { 0, 0, 0, 1, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 1, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 170, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 395, 0, 4, 0, 0, 0, 0, 0 }

  52. {955350, 971140, 171954, 66, 46, 402213, 202000, 187128, 419040, 515862, 48, 740532, 748512, 77517, 823, 1, 223, 369, 25668, 250, 242785, 276906, 477675, 616032, 154008, 399, 308016, 50424, 23280, 77004, 209520, 374256, 620136, 504240, 804426, 830718, 62376, 749, 99, 7878, 85977, 808000, 606, 965, 92, 838080}

    105957503

    Returns: { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 0, 0, 2, 0, 0, 0, 0, 171, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 278, 0 }

  53. {494208, 722376, 731798, 809064, 920448, 1, 988416, 9152, 158, 991014, 282720, 40132, 608, 143, 289755, 734, 579510, 828400, 330338, 816, 460224, 27456, 675783, 331, 436, 82368, 729, 306, 202266, 247104, 414200, 705}

    419088383

    Returns: { 1, 0, 0, 0, 0, 142, 423, 2, 0, 0, 0, 0, 0, 63, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0 }

  54. {28, 286, 1, 203, 781, 263978, 371625, 673960, 991, 441, 700749, 743250, 766080, 159885, 959310, 127680, 187, 830, 215040, 42560, 168490, 8512, 7168, 56, 383040, 324597, 108199, 645120, 100107, 709148, 336980, 649194, 791934}

    94227839

    Returns: { 1, 0, 27, 0, 0, 0, 0, 0, 0, 0, 0, 0, 122, 0, 0, 2, 0, 0, 0, 2, 0, 4, 0, 151, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

  55. {944208, 248, 2136, 49104, 122, 347325, 78684, 723, 79, 421, 315840, 245520, 664, 403704, 539168, 653718, 506620, 2, 884952, 912072, 228018, 63168, 947520, 982080, 159943, 134792, 253310, 329, 365, 36873, 76006, 314736, 368104, 694650, 986, 8, 959658, 184052, 491040, 313, 1, 446, 517, 807408, 736208}

    210165119

    Returns: { 0, 197, 0, 4, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 213, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 1, 0, 1, 0, 0, 0, 0 }

  56. {236304, 578, 154665, 518670, 588426, 201196, 645468, 658041, 401, 693600, 1, 725900, 415225, 804784, 161367, 173400, 144, 78768, 6, 216108, 259335, 219347, 322734, 830450, 12, 447, 472608, 945216, 425, 346800, 648324, 276, 459, 5826, 281, 315, 854}

    45370367

    Returns: { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 546, 2, 1, 0, 0, 0, 0, 0, 11, 0, 1, 47, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

  57. {1}

    23456

    Returns: { 23456 }

  58. { 494208, 722376, 731798, 809064, 920448, 1, 988416, 9152, 158, 991014, 282720, 40132, 608, 143, 289755, 734, 579510, 828400, 330338, 816, 460224, 27456, 675783, 331, 436, 82368, 729, 306, 202266, 247104, 414200, 705 }

    419088383

    Returns: { 1, 0, 0, 0, 0, 142, 423, 2, 0, 0, 0, 0, 0, 63, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 0 }

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: