Statistics

Problem Statement for "NinePatch"

Problem Statement

A nine-patch quilt is made from blocks containing nine squares of fabric arranged in a three-by-three grid. You are making a nine-patch quilt from rectangular fabric scraps and want to know how many blocks you can make. Each square of fabric will be two inches on each side, so each block will be six inches on each side (ignoring seam allowances).

You will be given the length and width in inches of each fabric scrap as two int[]'s, where the dimensions of scrap i are given by element i of length and element i of width. You plan to cut as many squares as possible from each scrap, but the squares must all be cut with sides parallel to the sides of the scrap (because a square cut at an angle will stretch in unwanted ways). You will return the maximum number of blocks that can be constructed using all the scraps.

For example, suppose you have only a single scrap that is 13 inches long and 9 inches wide. There is room for 6 two-inch squares lengthwise and 4 two-inch squares widthwise, so you could cut a total of 24 squares. From those squares, you could make 2 blocks, with 6 squares left over. Note that, after cutting the 24 squares, you would have some extra strips. You might think you could sew those strips together into as many as 5 extra two-inch squares. Combined with the 6 solid squares left over, you would then have enough squares to make another block. However, for aesthetic reasons, you have decided that your individual squares must never show any seams, so you refuse to piece together squares in this fashion.

Definition

Class:
NinePatch
Method:
numBlocks
Parameters:
int[], int[]
Returns:
int
Method signature:
int numBlocks(int[] length, int[] width)
(be sure your method is public)

Constraints

  • length contains between 1 and 50 elements, inclusive.
  • width contains the same number of elements as length.
  • Each element of length is between 1 and 1000, inclusive.
  • Each element of width is between 1 and 38, inclusive.

Examples

  1. { 13 }

    { 9 }

    Returns: 2

    The example above.

  2. { 1, 8 }

    { 4, 1 }

    Returns: 0

    One scrap is too short to make any squares, and the other scrap is too narrow.

  3. { 7, 13, 192 }

    { 6, 22, 31 }

    Returns: 168

  4. { 11, 373, 163, 318, 83, 835, 102, 501, 631, 598, 676, 651, 169, 365, 243, 523, 193, 62, 81, 252, 280, 283, 939, 277, 228, 901, 195, 232, 323, 807, 104, 800, 580, 108, 360, 650, 744, 126, 675, 606, 121, 991, 380, 400, 873, 682, 102, 485, 201, 902 }

    { 17, 23, 38, 11, 3, 34, 33, 36, 20, 5, 11, 31, 7, 29, 6, 19, 13, 22, 1, 31, 20, 37, 34, 1, 30, 20, 34, 33, 21, 27, 2, 9, 1, 37, 32, 34, 15, 18, 11, 21, 17, 11, 13, 18, 21, 19, 13, 27, 17, 8 }

    Returns: 11363

  5. { 771, 53, 163, 903, 606, 806, 8, 637, 74, 659, 419, 652, 714, 120, 866, 83, 311, 132, 299, 257, 183, 290, 964, 232, 450, 493, 931, 916, 390, 130, 230, 935, 686, 566, 680, 282, 428, 956, 578, 642, 6, 178, 182, 228, 606, 13, 568, 886, 900, 479 }

    { 30, 9, 25, 25, 12, 21, 14, 9, 3, 11, 34, 10, 16, 36, 24, 2, 24, 16, 33, 34, 9, 32, 10, 4, 36, 8, 19, 24, 17, 8, 19, 22, 10, 2, 5, 17, 1, 5, 5, 37, 36, 30, 29, 21, 37, 37, 7, 1, 7, 4 }

    Returns: 10399

  6. { 806, 249, 743, 617, 771, 48, 258, 846, 508, 618, 156, 242, 267, 139, 212, 181, 539, 63, 84, 872, 46, 205, 368, 225, 728, 565, 384, 83, 832, 807, 383, 556, 603, 997, 903, 140, 65, 734, 125, 627, 852, 67, 203, 308, 88, 663, 717, 833, 868, 551 }

    { 22, 8, 37, 14, 37, 26, 3, 16, 5, 11, 32, 6, 3, 10, 37, 22, 32, 4, 23, 24, 28, 28, 1, 26, 4, 20, 31, 35, 38, 16, 3, 34, 32, 21, 22, 25, 23, 24, 22, 17, 17, 38, 36, 36, 20, 20, 1, 34, 38, 11 }

    Returns: 13400

  7. { 615, 670, 927, 411, 266, 92, 609, 482, 17, 877, 88, 632, 858, 200, 929, 647, 832, 287, 440, 474, 295, 266, 672, 699, 365, 38, 181, 976, 764, 465, 386, 152, 30, 361, 195, 824, 234, 864, 470, 393, 199, 535, 806, 226, 449, 153, 52, 418, 5, 546 }

    { 37, 31, 19, 36, 18, 7, 35, 8, 31, 28, 33, 15, 13, 37, 2, 27, 19, 29, 9, 19, 19, 18, 33, 27, 5, 33, 16, 38, 10, 15, 9, 27, 35, 14, 6, 35, 35, 36, 13, 7, 29, 10, 23, 14, 5, 16, 37, 14, 12, 29 }

    Returns: 12951

  8. { 843, 551, 923, 440, 889, 332, 794, 224, 922, 771, 392, 344, 484, 460, 408, 342, 771, 592, 123, 34, 880, 26, 977, 866, 346, 249, 214, 401, 340, 153, 151, 482, 933, 320, 192, 624, 348, 93, 426, 548, 145, 23, 309, 358, 941, 433, 662, 769, 289, 745 }

    { 38, 37, 4, 35, 37, 3, 2, 25, 18, 7, 10, 29, 2, 10, 25, 14, 27, 33, 10, 2, 19, 6, 38, 17, 12, 33, 11, 2, 20, 10, 16, 19, 9, 38, 30, 31, 3, 18, 1, 31, 31, 19, 36, 23, 17, 37, 31, 23, 37, 35 }

    Returns: 13782

  9. { 737, 678, 865, 310, 940, 885, 880, 151, 525, 544, 544, 885, 5, 324, 586, 607, 312, 767, 38, 643, 28, 880, 975, 290, 661, 97, 275, 14, 596, 460, 123, 193, 575, 184, 403, 577, 408, 849, 589, 10, 918, 372, 198, 579, 16, 529, 395, 293, 195, 268 }

    { 34, 23, 25, 10, 27, 19, 29, 4, 17, 33, 16, 17, 17, 19, 27, 36, 36, 1, 1, 31, 14, 27, 9, 27, 15, 16, 12, 28, 14, 19, 31, 31, 31, 6, 30, 9, 36, 37, 38, 20, 10, 15, 35, 30, 9, 8, 9, 12, 18, 33 }

    Returns: 13745

  10. { 362, 135, 829, 64, 124, 238, 96, 353, 3, 764, 490, 823, 481, 803, 601, 747, 454, 961, 519, 944, 176, 415, 448, 952, 532, 456, 111, 620, 460, 585, 435, 566, 943, 49, 194, 64, 20, 370, 529, 310, 945, 793, 505, 673, 714, 772, 173, 531, 914, 607 }

    { 35, 19, 1, 3, 7, 11, 1, 15, 9, 23, 19, 12, 24, 30, 14, 38, 2, 14, 36, 16, 8, 10, 19, 25, 9, 32, 30, 25, 12, 21, 36, 29, 14, 13, 7, 18, 18, 36, 10, 36, 1, 14, 28, 28, 33, 31, 26, 3, 22, 12 }

    Returns: 13059

  11. { 740, 189, 478, 679, 414, 401, 374, 558, 424, 483, 746, 320, 406, 26, 189, 989, 600, 8, 720, 815, 578, 663, 11, 716, 822, 643, 350, 304, 258, 995, 88, 61, 671, 908, 333, 403, 328, 294, 637, 768, 6, 250, 475, 584, 73, 123, 376, 944, 220, 440 }

    { 27, 4, 36, 9, 4, 15, 32, 11, 1, 6, 22, 36, 28, 5, 38, 7, 12, 17, 1, 30, 34, 22, 26, 3, 11, 14, 26, 33, 15, 12, 26, 3, 20, 8, 25, 26, 29, 21, 26, 27, 9, 20, 17, 37, 14, 36, 1, 13, 28, 9 }

    Returns: 10976

  12. { 270, 832, 677, 4, 977, 472, 529, 143, 233, 643, 286, 577, 453, 156, 120, 226, 210, 914, 840, 797, 678, 161, 606, 427, 467, 500, 742, 789, 276, 12, 209, 141, 872, 701, 94, 2, 578, 201, 243, 563, 597, 125, 988, 702, 265, 706, 777, 476, 512, 410 }

    { 15, 10, 24, 38, 14, 10, 27, 6, 5, 5, 1, 2, 18, 6, 33, 24, 27, 26, 14, 36, 15, 2, 11, 5, 35, 15, 23, 13, 1, 13, 5, 8, 31, 34, 31, 22, 23, 28, 25, 28, 32, 31, 36, 15, 5, 30, 37, 36, 30, 29 }

    Returns: 13260

  13. { 606, 517, 358, 813, 522, 766, 795, 661, 572, 465, 729, 290, 905, 61, 187, 147, 449, 531, 44, 969, 337, 539, 232, 936, 117, 579, 115, 402, 486, 510, 952, 400, 681, 287, 919, 323, 581, 943, 730, 652, 48, 847, 490, 386, 21, 86, 70, 869, 415, 334 }

    { 36, 2, 35, 37, 1, 28, 11, 9, 5, 22, 7, 12, 34, 6, 26, 29, 5, 24, 13, 36, 21, 26, 37, 7, 9, 27, 35, 13, 9, 14, 3, 1, 8, 18, 6, 7, 20, 26, 8, 32, 10, 32, 20, 9, 10, 6, 19, 18, 24, 7 }

    Returns: 12006

  14. { 806, 249, 743, 617, 771, 48, 258, 846, 508, 618, 156, 242, 267, 139, 212, 181, 539, 63, 84, 872, 46, 205, 368, 225, 728, 565, 384, 83, 832, 807, 383, 556, 603, 997, 903, 140, 65, 734, 125, 627, 852, 67, 203, 308, 88, 663, 717, 833, 868, 551 }

    { 22, 8, 37, 14, 37, 26, 3, 16, 5, 11, 32, 6, 3, 10, 37, 22, 32, 4, 23, 24, 28, 28, 1, 26, 4, 20, 31, 35, 38, 16, 3, 34, 32, 21, 22, 25, 23, 24, 22, 17, 17, 38, 36, 36, 20, 20, 1, 34, 38, 11 }

    Returns: 13400

  15. { 615, 670, 927, 411, 266, 92, 609, 482, 17, 877, 88, 632, 858, 200, 929, 647, 832, 287, 440, 474, 295, 266, 672, 699, 365, 38, 181, 976, 764, 465, 386, 152, 30, 361, 195, 824, 234, 864, 470, 393, 199, 535, 806, 226, 449, 153, 52, 418, 5, 546 }

    { 37, 31, 19, 36, 18, 7, 35, 8, 31, 28, 33, 15, 13, 37, 2, 27, 19, 29, 9, 19, 19, 18, 33, 27, 5, 33, 16, 38, 10, 15, 9, 27, 35, 14, 6, 35, 35, 36, 13, 7, 29, 10, 23, 14, 5, 16, 37, 14, 12, 29 }

    Returns: 12951

  16. { 843, 551, 923, 440, 889, 332, 794, 224, 922, 771, 392, 344, 484, 460, 408, 342, 771, 592, 123, 34, 880, 26, 977, 866, 346, 249, 214, 401, 340, 153, 151, 482, 933, 320, 192, 624, 348, 93, 426, 548, 145, 23, 309, 358, 941, 433, 662, 769, 289, 745 }

    { 38, 37, 4, 35, 37, 3, 2, 25, 18, 7, 10, 29, 2, 10, 25, 14, 27, 33, 10, 2, 19, 6, 38, 17, 12, 33, 11, 2, 20, 10, 16, 19, 9, 38, 30, 31, 3, 18, 1, 31, 31, 19, 36, 23, 17, 37, 31, 23, 37, 35 }

    Returns: 13782

  17. { 737, 678, 865, 310, 940, 885, 880, 151, 525, 544, 544, 885, 5, 324, 586, 607, 312, 767, 38, 643, 28, 880, 975, 290, 661, 97, 275, 14, 596, 460, 123, 193, 575, 184, 403, 577, 408, 849, 589, 10, 918, 372, 198, 579, 16, 529, 395, 293, 195, 268 }

    { 34, 23, 25, 10, 27, 19, 29, 4, 17, 33, 16, 17, 17, 19, 27, 36, 36, 1, 1, 31, 14, 27, 9, 27, 15, 16, 12, 28, 14, 19, 31, 31, 31, 6, 30, 9, 36, 37, 38, 20, 10, 15, 35, 30, 9, 8, 9, 12, 18, 33 }

    Returns: 13745

  18. { 362, 135, 829, 64, 124, 238, 96, 353, 3, 764, 490, 823, 481, 803, 601, 747, 454, 961, 519, 944, 176, 415, 448, 952, 532, 456, 111, 620, 460, 585, 435, 566, 943, 49, 194, 64, 20, 370, 529, 310, 945, 793, 505, 673, 714, 772, 173, 531, 914, 607 }

    { 35, 19, 1, 3, 7, 11, 1, 15, 9, 23, 19, 12, 24, 30, 14, 38, 2, 14, 36, 16, 8, 10, 19, 25, 9, 32, 30, 25, 12, 21, 36, 29, 14, 13, 7, 18, 18, 36, 10, 36, 1, 14, 28, 28, 33, 31, 26, 3, 22, 12 }

    Returns: 13059

  19. { 740, 189, 478, 679, 414, 401, 374, 558, 424, 483, 746, 320, 406, 26, 189, 989, 600, 8, 720, 815, 578, 663, 11, 716, 822, 643, 350, 304, 258, 995, 88, 61, 671, 908, 333, 403, 328, 294, 637, 768, 6, 250, 475, 584, 73, 123, 376, 944, 220, 440 }

    { 27, 4, 36, 9, 4, 15, 32, 11, 1, 6, 22, 36, 28, 5, 38, 7, 12, 17, 1, 30, 34, 22, 26, 3, 11, 14, 26, 33, 15, 12, 26, 3, 20, 8, 25, 26, 29, 21, 26, 27, 9, 20, 17, 37, 14, 36, 1, 13, 28, 9 }

    Returns: 10976

  20. { 270, 832, 677, 4, 977, 472, 529, 143, 233, 643, 286, 577, 453, 156, 120, 226, 210, 914, 840, 797, 678, 161, 606, 427, 467, 500, 742, 789, 276, 12, 209, 141, 872, 701, 94, 2, 578, 201, 243, 563, 597, 125, 988, 702, 265, 706, 777, 476, 512, 410 }

    { 15, 10, 24, 38, 14, 10, 27, 6, 5, 5, 1, 2, 18, 6, 33, 24, 27, 26, 14, 36, 15, 2, 11, 5, 35, 15, 23, 13, 1, 13, 5, 8, 31, 34, 31, 22, 23, 28, 25, 28, 32, 31, 36, 15, 5, 30, 37, 36, 30, 29 }

    Returns: 13260

  21. { 606, 517, 358, 813, 522, 766, 795, 661, 572, 465, 729, 290, 905, 61, 187, 147, 449, 531, 44, 969, 337, 539, 232, 936, 117, 579, 115, 402, 486, 510, 952, 400, 691, 287, 919, 323, 581, 943, 730, 652, 48, 847, 490, 386, 21, 86, 70, 869, 415, 334 }

    { 36, 2, 35, 37, 1, 28, 11, 9, 5, 22, 7, 12, 34, 6, 26, 29, 5, 24, 13, 36, 21, 26, 37, 7, 9, 27, 35, 13, 9, 14, 3, 1, 8, 18, 6, 7, 20, 26, 8, 32, 10, 32, 20, 9, 10, 6, 19, 18, 24, 7 }

    Returns: 12008

  22. { 376 }

    { 32 }

    Returns: 334

  23. { 863, 430 }

    { 36, 22 }

    Returns: 1124

  24. { 344, 608, 501 }

    { 30, 32, 37 }

    Returns: 1327

  25. { 690, 609, 344, 36 }

    { 14, 3, 34, 32 }

    Returns: 659

  26. { 502, 271, 882, 772, 814 }

    { 8, 14, 8, 5, 7 }

    Returns: 634

  27. { 566, 382, 105, 617, 127, 419 }

    { 28, 19, 38, 19, 20, 9 }

    Returns: 1211

  28. { 799, 219, 233, 675, 629, 937, 294 }

    { 27, 26, 1, 38, 18, 1, 7 }

    Returns: 1808

  29. { 295, 644, 913, 421, 913, 854, 316, 753 }

    { 18, 25, 22, 14, 35, 34, 16, 33 }

    Returns: 3773

  30. { 824, 484, 106, 568, 657, 731, 3, 163, 605 }

    { 10, 32, 12, 13, 31, 24, 23, 30, 35 }

    Returns: 2623

  31. { 299, 285, 795, 54, 284, 673, 52, 637, 675, 401 }

    { 10, 6, 7, 19, 6, 13, 17, 33, 26, 28 }

    Returns: 1947

  32. { 928, 708, 869, 442, 967, 563, 967, 647, 68, 804, 381 }

    { 23, 8, 32, 13, 32, 26, 28, 19, 16, 33, 1 }

    Returns: 4727

  33. { 878, 538, 563, 643, 97, 491, 437, 647, 311, 639, 362, 209 }

    { 37, 23, 23, 25, 30, 23, 13, 34, 20, 10, 32, 13 }

    Returns: 3853

  34. { 775, 195, 866, 976, 340, 691, 645, 207, 735, 933, 822, 566, 433 }

    { 16, 9, 6, 34, 1, 16, 16, 27, 6, 33, 11, 13, 4 }

    Returns: 3610

  35. { 70, 518, 912, 697, 149, 98, 522, 250, 644, 25, 320, 303, 40, 930 }

    { 23, 37, 29, 20, 22, 8, 5, 25, 5, 36, 7, 34, 22, 16 }

    Returns: 2865

  36. { 552, 133, 359, 29, 703, 534, 629, 580, 59, 246, 13, 804, 741, 371, 796 }

    { 23, 10, 36, 6, 12, 21, 30, 15, 29, 21, 37, 27, 5, 36, 36 }

    Returns: 4038

  37. { 978, 686, 512, 268, 574, 742, 946, 635, 576, 263, 132, 993, 749, 67, 587, 978 }

    { 19, 4, 23, 27, 13, 10, 33, 10, 8, 15, 17, 12, 29, 10, 21, 34 }

    Returns: 4954

  38. { 463, 465, 75, 657, 593, 171, 474, 444, 106, 917, 419, 38, 608, 670, 323, 112, 409 }

    { 16, 25, 26, 1, 19, 5, 35, 5, 19, 19, 10, 1, 28, 1, 18, 13, 1 }

    Returns: 2678

  39. { 907, 100, 220, 314, 879, 767, 936, 862, 561, 244, 403, 919, 65, 424, 139, 397, 654, 793 }

    { 32, 9, 6, 28, 20, 19, 4, 8, 34, 16, 16, 22, 21, 5, 2, 13, 36, 35 }

    Returns: 5276

  40. { 870, 116, 298, 172, 150, 568, 698, 301, 416, 281, 234, 571, 259, 176, 272, 521, 884, 904, 835 }

    { 2, 9, 28, 32, 32, 4, 9, 26, 8, 7, 14, 25, 17, 28, 19, 13, 20, 13, 9 }

    Returns: 3175

  41. { 861, 236, 229, 354, 970, 770, 357, 154, 148, 742, 605, 253, 595, 614, 674, 527, 169, 558, 899, 690 }

    { 17, 19, 8, 6, 26, 6, 38, 13, 30, 11, 26, 7, 15, 4, 24, 17, 12, 3, 12, 19 }

    Returns: 4387

  42. { 131, 503, 132, 763, 689, 81, 528, 436, 969, 806, 17, 59, 95, 664, 9, 394, 13, 751, 402, 932, 821 }

    { 33, 9, 25, 16, 16, 9, 22, 4, 35, 11, 33, 25, 26, 18, 22, 35, 31, 36, 27, 8, 13 }

    Returns: 4847

  43. { 702, 880, 440, 590, 562, 688, 830, 889, 168, 811, 280, 346, 945, 289, 581, 449, 743, 313, 524, 572, 73, 619 }

    { 2, 27, 22, 2, 27, 29, 2, 21, 7, 23, 19, 6, 31, 14, 5, 34, 8, 8, 13, 22, 1, 11 }

    Returns: 5493

  44. { 278, 143, 108, 925, 633, 363, 917, 783, 855, 772, 881, 189, 473, 228, 239, 90, 291, 964, 279, 67, 552, 458, 415 }

    { 21, 34, 27, 4, 18, 19, 33, 22, 32, 38, 8, 1, 1, 8, 15, 23, 25, 18, 9, 23, 28, 24, 20 }

    Returns: 5968

  45. { 663, 823, 807, 837, 868, 907, 370, 573, 17, 804, 623, 568, 659, 28, 789, 724, 42, 82, 276, 972, 784, 565, 804, 119 }

    { 6, 31, 28, 9, 16, 34, 16, 17, 24, 30, 8, 6, 18, 33, 23, 1, 26, 25, 36, 31, 27, 23, 4, 2 }

    Returns: 7194

  46. { 337, 675, 162, 553, 71, 711, 413, 643, 906, 837, 245, 173, 399, 637, 19, 930, 57, 874, 562, 538, 148, 297, 166, 107, 886 }

    { 16, 15, 34, 15, 3, 15, 13, 18, 25, 3, 26, 33, 20, 13, 2, 24, 37, 8, 23, 33, 34, 18, 24, 9, 20 }

    Returns: 5537

  47. { 602, 202, 343, 749, 768, 113, 912, 600, 77, 137, 309, 717, 579, 801, 201, 477, 660, 179, 672, 39, 245, 135, 444, 876, 614, 349 }

    { 38, 9, 38, 22, 36, 16, 9, 32, 25, 15, 16, 29, 15, 18, 19, 23, 28, 30, 15, 22, 4, 21, 1, 27, 10, 22 }

    Returns: 6928

  48. { 443, 709, 181, 998, 674, 114, 671, 72, 564, 91, 213, 438, 240, 988, 71, 976, 278, 882, 95, 660, 518, 34, 13, 950, 527, 165, 499 }

    { 25, 34, 24, 10, 5, 15, 27, 27, 31, 19, 7, 28, 38, 30, 36, 34, 38, 12, 23, 18, 38, 1, 18, 7, 16, 27, 18 }

    Returns: 7262

  49. { 430, 503, 200, 425, 41, 810, 372, 130, 369, 209, 375, 881, 689, 574, 951, 354, 132, 217, 892, 708, 760, 376, 158, 823, 177, 1000, 939, 732 }

    { 15, 29, 31, 25, 6, 14, 30, 14, 10, 20, 31, 32, 24, 34, 27, 24, 23, 8, 36, 12, 30, 19, 5, 17, 32, 20, 8, 2 }

    Returns: 8345

  50. { 41, 283, 799, 741, 646, 997, 675, 950, 409, 594, 727, 535, 492, 950, 761, 226, 925, 870, 816, 10, 837, 394, 741, 989, 215, 110, 234, 553, 854 }

    { 38, 3, 8, 20, 28, 24, 38, 1, 25, 8, 22, 7, 4, 34, 20, 3, 24, 19, 32, 34, 9, 32, 8, 13, 7, 26, 14, 35, 12 }

    Returns: 8675

  51. { 446, 982, 61, 213, 743, 326, 117, 942, 791, 387, 646, 329, 609, 793, 730, 532, 792, 671, 679, 194, 490, 184, 882, 3, 296, 970, 98, 386, 21, 420 }

    { 20, 29, 15, 22, 10, 36, 28, 15, 6, 25, 23, 20, 9, 6, 4, 24, 29, 21, 20, 9, 2, 26, 15, 15, 14, 10, 12, 21, 14, 28 }

    Returns: 6700

  52. { 275, 439, 493, 362, 511, 693, 35, 908, 546, 286, 587, 317, 666, 65, 515, 138, 472, 715, 497, 121, 543, 478, 772, 624, 8, 743, 358, 274, 595, 699, 620 }

    { 33, 18, 17, 4, 18, 23, 8, 15, 37, 17, 7, 12, 1, 2, 19, 8, 7, 15, 15, 16, 17, 36, 13, 24, 34, 30, 25, 16, 9, 8, 4 }

    Returns: 6264

  53. { 254, 782, 810, 906, 343, 979, 649, 536, 353, 143, 384, 36, 432, 584, 159, 2, 941, 887, 482, 63, 757, 634, 858, 111, 786, 328, 302, 854, 526, 712, 149, 853 }

    { 6, 24, 30, 33, 20, 5, 35, 5, 9, 8, 13, 17, 7, 37, 14, 33, 32, 1, 38, 33, 26, 5, 10, 20, 24, 2, 9, 31, 20, 36, 18, 15 }

    Returns: 9033

  54. { 641, 360, 87, 978, 651, 69, 244, 983, 634, 336, 632, 646, 622, 895, 463, 639, 875, 936, 499, 472, 408, 967, 753, 895, 490, 563, 302, 334, 526, 866, 458, 466, 863 }

    { 7, 9, 8, 22, 8, 25, 29, 10, 7, 33, 33, 38, 28, 25, 7, 33, 16, 3, 9, 31, 24, 37, 34, 38, 25, 33, 26, 37, 30, 10, 24, 3, 29 }

    Returns: 11722

  55. { 121, 401, 894, 289, 116, 667, 427, 938, 664, 793, 20, 542, 643, 283, 438, 695, 434, 515, 105, 797, 788, 980, 306, 907, 289, 521, 367, 961, 489, 603, 423, 926, 975, 372 }

    { 16, 4, 28, 3, 13, 1, 6, 20, 28, 25, 2, 7, 21, 29, 24, 15, 32, 30, 11, 29, 33, 5, 37, 20, 35, 32, 16, 14, 36, 26, 21, 4, 28, 8 }

    Returns: 10165

  56. { 937, 37, 121, 591, 258, 420, 288, 108, 35, 767, 827, 785, 652, 361, 169, 741, 472, 998, 223, 414, 300, 931, 835, 51, 87, 17, 733, 190, 441, 242, 197, 68, 167, 208, 589 }

    { 26, 20, 24, 8, 23, 7, 18, 27, 6, 28, 25, 14, 20, 24, 11, 12, 37, 8, 22, 11, 6, 35, 9, 17, 15, 36, 33, 36, 15, 25, 1, 33, 11, 1, 15 }

    Returns: 7347

  57. { 795, 624, 655, 102, 219, 193, 380, 433, 487, 508, 668, 717, 700, 777, 534, 918, 398, 180, 375, 804, 920, 483, 797, 373, 225, 588, 416, 39, 389, 965, 669, 95, 838, 848, 561, 140 }

    { 23, 28, 4, 19, 20, 34, 35, 1, 15, 33, 5, 26, 23, 32, 5, 19, 13, 36, 16, 35, 9, 27, 30, 25, 15, 19, 27, 6, 20, 28, 24, 6, 26, 17, 5, 3 }

    Returns: 10491

  58. { 423, 55, 4, 700, 570, 475, 759, 324, 115, 539, 168, 65, 227, 624, 323, 645, 705, 381, 791, 937, 167, 829, 339, 318, 634, 407, 980, 460, 846, 692, 397, 19, 852, 293, 80, 672, 935 }

    { 33, 23, 4, 34, 7, 16, 28, 3, 9, 31, 26, 11, 12, 3, 31, 3, 15, 31, 14, 38, 32, 19, 9, 3, 26, 1, 6, 28, 29, 11, 37, 37, 36, 28, 6, 21, 24 }

    Returns: 9881

  59. { 372, 554, 917, 896, 828, 917, 715, 625, 881, 378, 378, 419, 535, 687, 68, 113, 935, 508, 286, 501, 641, 811, 304, 599, 389, 738, 576, 549, 81, 980, 707, 890, 318, 500, 467, 191, 212, 387 }

    { 22, 35, 22, 28, 27, 34, 28, 22, 3, 9, 30, 32, 37, 36, 14, 31, 17, 20, 33, 24, 6, 27, 21, 6, 24, 14, 15, 13, 7, 8, 2, 26, 4, 4, 37, 24, 15, 11 }

    Returns: 11550

  60. { 8, 332, 994, 800, 22, 849, 917, 19, 652, 462, 2, 327, 904, 128, 540, 208, 203, 162, 909, 219, 201, 66, 796, 998, 370, 724, 300, 910, 304, 795, 434, 958, 410, 925, 81, 317, 303, 284, 491 }

    { 9, 32, 2, 29, 38, 3, 21, 22, 21, 5, 24, 25, 12, 21, 18, 2, 10, 3, 28, 14, 14, 14, 12, 15, 21, 25, 29, 21, 18, 14, 7, 31, 26, 17, 11, 10, 30, 33, 33 }

    Returns: 8978

  61. { 615, 935, 33, 743, 629, 78, 465, 931, 579, 151, 52, 487, 264, 533, 581, 168, 730, 648, 566, 713, 488, 729, 553, 322, 368, 717, 105, 355, 50, 719, 696, 50, 595, 691, 572, 928, 46, 825, 461, 583 }

    { 10, 24, 27, 31, 24, 31, 35, 9, 12, 37, 34, 19, 3, 15, 35, 38, 37, 25, 23, 36, 14, 10, 5, 26, 2, 32, 21, 30, 7, 10, 2, 22, 21, 26, 19, 10, 31, 38, 15, 15 }

    Returns: 11022

  62. { 205, 296, 187, 107, 933, 466, 160, 828, 683, 853, 94, 498, 640, 232, 237, 508, 556, 909, 607, 194, 458, 140, 478, 651, 239, 69, 917, 220, 412, 8, 341, 876, 694, 221, 119, 748, 957, 314, 90, 185, 303 }

    { 38, 29, 4, 26, 4, 18, 28, 17, 6, 2, 34, 34, 19, 31, 3, 19, 10, 28, 2, 28, 25, 29, 2, 22, 26, 35, 30, 5, 3, 11, 18, 33, 21, 17, 2, 30, 11, 17, 1, 22, 27 }

    Returns: 8602

  63. { 931, 999, 493, 595, 71, 549, 951, 534, 255, 597, 728, 699, 705, 130, 635, 19, 85, 99, 665, 659, 919, 831, 499, 728, 875, 129, 343, 947, 168, 246, 643, 416, 490, 16, 159, 729, 911, 754, 270, 428, 132, 958 }

    { 6, 8, 12, 19, 20, 7, 17, 24, 25, 32, 38, 11, 22, 13, 33, 1, 21, 36, 24, 4, 19, 19, 26, 38, 27, 30, 10, 29, 31, 15, 8, 17, 32, 1, 28, 36, 26, 8, 12, 4, 20, 22 }

    Returns: 12146

  64. { 604, 709, 913, 178, 834, 744, 325, 884, 252, 169, 726, 684, 8, 960, 206, 243, 305, 927, 610, 678, 694, 836, 409, 719, 535, 435, 666, 922, 944, 255, 82, 786, 702, 468, 570, 526, 652, 683, 711, 775, 124, 249, 753 }

    { 26, 29, 23, 20, 24, 36, 1, 23, 21, 24, 33, 6, 23, 10, 37, 27, 37, 17, 37, 27, 5, 34, 1, 19, 37, 26, 24, 10, 21, 38, 31, 31, 22, 9, 5, 3, 29, 2, 17, 3, 25, 19, 36 }

    Returns: 13739

  65. { 75, 998, 242, 635, 416, 937, 462, 885, 668, 102, 588, 939, 736, 337, 983, 80, 731, 54, 739, 733, 395, 888, 372, 550, 16, 667, 422, 927, 374, 672, 157, 148, 304, 852, 678, 188, 877, 958, 731, 224, 29, 514, 448, 61 }

    { 27, 7, 2, 2, 12, 12, 9, 18, 38, 20, 27, 4, 18, 23, 28, 14, 35, 11, 3, 21, 28, 21, 37, 21, 34, 13, 12, 31, 14, 2, 37, 38, 33, 4, 15, 28, 22, 31, 2, 6, 33, 5, 12, 29 }

    Returns: 10660

  66. { 41, 146, 750, 726, 364, 262, 619, 524, 852, 966, 273, 680, 511, 518, 454, 367, 56, 166, 325, 821, 399, 633, 677, 680, 193, 411, 883, 185, 260, 823, 307, 370, 735, 909, 927, 653, 81, 950, 866, 684, 926, 812, 366, 912, 829 }

    { 16, 20, 5, 27, 9, 26, 1, 21, 13, 4, 10, 24, 3, 33, 3, 34, 34, 15, 28, 36, 6, 5, 32, 34, 33, 16, 28, 12, 7, 26, 6, 38, 29, 9, 20, 31, 35, 12, 27, 28, 36, 28, 4, 2, 8 }

    Returns: 13008

  67. { 310, 322, 439, 950, 698, 5, 727, 787, 561, 881, 995, 654, 618, 756, 102, 332, 642, 577, 497, 884, 150, 359, 705, 748, 533, 62, 247, 13, 501, 85, 659, 988, 658, 804, 565, 317, 915, 424, 498, 756, 247, 510, 243, 218, 958, 714 }

    { 1, 33, 10, 24, 27, 28, 18, 3, 29, 5, 14, 5, 4, 26, 7, 18, 9, 7, 26, 9, 1, 22, 25, 9, 27, 16, 13, 29, 21, 6, 29, 7, 18, 34, 36, 38, 23, 38, 32, 8, 30, 12, 30, 23, 1, 25 }

    Returns: 11652

  68. { 578, 105, 706, 968, 922, 940, 67, 402, 2, 770, 932, 279, 892, 616, 635, 383, 41, 271, 25, 720, 537, 136, 860, 621, 771, 346, 741, 917, 15, 197, 969, 544, 264, 247, 364, 217, 414, 918, 119, 747, 477, 77, 242, 173, 58, 869, 984 }

    { 5, 30, 1, 36, 25, 28, 35, 6, 24, 2, 3, 26, 18, 13, 3, 21, 17, 9, 11, 36, 34, 24, 3, 25, 4, 2, 15, 27, 13, 6, 6, 3, 36, 11, 28, 3, 37, 22, 15, 21, 34, 16, 12, 32, 10, 30, 17 }

    Returns: 10891

  69. { 910, 556, 919, 843, 196, 709, 595, 703, 363, 125, 487, 175, 167, 951, 218, 326, 792, 288, 780, 735, 988, 335, 279, 89, 421, 551, 617, 804, 246, 629, 363, 634, 917, 445, 671, 293, 622, 183, 530, 384, 555, 506, 70, 252, 428, 996, 875, 996 }

    { 10, 4, 19, 20, 15, 15, 15, 13, 18, 15, 24, 3, 11, 7, 20, 12, 15, 6, 4, 8, 18, 28, 14, 34, 31, 2, 13, 10, 17, 6, 9, 16, 24, 26, 26, 29, 24, 16, 38, 35, 33, 22, 3, 13, 23, 16, 23, 31 }

    Returns: 12009

  70. { 689, 793, 981, 304, 972, 81, 749, 423, 875, 4, 216, 296, 870, 42, 160, 490, 494, 893, 121, 969, 682, 584, 351, 942, 961, 582, 57, 785, 360, 791, 923, 947, 677, 365, 257, 542, 862, 122, 305, 324, 835, 717, 435, 886, 18, 864, 886, 215, 210 }

    { 24, 29, 7, 9, 7, 30, 2, 36, 22, 3, 11, 28, 25, 30, 1, 26, 29, 14, 19, 4, 26, 1, 25, 19, 17, 3, 5, 29, 1, 26, 7, 26, 13, 25, 33, 2, 6, 25, 29, 35, 25, 9, 2, 15, 26, 34, 33, 33, 1 }

    Returns: 12752

  71. { 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    { 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38 }

    Returns: 52777

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: