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