PROBLEM STATEMENT
Given a list of line lengths, and the dimensions of the canvas return the
number of drawings possible. Each line:
1) is drawn vertically or horizontally within the confines of the canvas
2) is 1 unit wide
3) cannot intersect with any of the other lines
4) is the same color (black)
5) must be used
For example:
lengths = {3,4,5}
canvas 7 x 4
A) B) C) D)
...3334 3334444 4444333 .......
......4 ....... ....... 55555..
......4 55555.. 55555.. .......
.555554 ....... ....... 4444333
Note the numbers used in the pictures are only to show which lines were used
and don't have any other significance. A, B, C, and D are 4 examples of valid
pictures. Since all lines are the same color pictures B and C are considered
equivalent and should not be counted as 2 separate pictures. Even though D is
an upside-down version of C and B it still counts as a separate picture.
Create a class ManyPics that contains the method howMany, which takes an int[]
lengths, an int width, and an int height and returns an int representing the
number of distinct drawable pictures.
DEFINITION
Class: ManyPics
Method: howMany
Parameters: int[], int, int
Returns: int
Method signature (be sure your method is public): int howMany(int[] lengths,
int width, int height);
NOTES
- The uniqueness of a picture is completely determined by which areas are colored
- Two pictures are equivalent if each picture has exactly the same areas colored
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- lengths will contain between 1 and 4 elements, inclusive
- Each element of lengths will be between 3 and 8, inclusive
- width will be between 1 and 8, inclusive
- height will be between 1 and 8, inclusive
- The area of the canvas (width*height) will be between 2 and 32, inclusive
EXAMPLES
1) lengths = {3}
width = 3
height = 3
333 ... ... 3.. .3. ..3
... 333 ... 3.. .3. ..3
... ... 333 3.. .3. ..3
Above are the 6 possible pictures drawn from one line of length 3, and the
given canvas.
Method returns 6.
2) lengths = {4}
width = 3
height = 4
4.. .4. ..4
4.. .4. ..4
4.. .4. ..4
4.. .4. ..4
Above are the 3 possible pictures drawn from one line of length 4, and the
given canvas.
Method returns 3.
3) lengths = {3,4}
width = 3
height = 4
43. 4.3 34. .43 3.4 .34
43. 4.3 34. .43 3.4 .34
43. 4.3 34. .43 3.4 .34
4.. 4.. .4. .4. ..4 ..4
4.. 4.. .4. .4. ..4 ..4
43. 4.3 34. .43 3.4 .34
43. 4.3 34. .43 3.4 .34
43. 4.3 34. .43 3.4 .34
Above are the 12 possible pictures drawn from two lines of length 3 and 4, and
the given canvas.
Method returns 12.
4) lengths = {3,8}
width = 4
height = 7
The line of length 8 will not fit in the picture so no pictures can be drawn
using both lines.
Method returns 0.
5) lengths = {3,4,5,6}
width = 4
height = 8
Method returns 16272.