PROBLEM STATEMENT
The Buddy System is applied to the children on a school outing. They are lined
up in rows and columns (usually with a few adults to hold down the level of
mayhem) and then are instructed to pair up with an adjacent child. Each pair of
buddies must then hold hands during the outing. (No adult, of course, is
anyone's buddy). We find that it works better when a pair is side-by-side in
the same row, but if necessary we allow buddies to be front-to-back (adjacent
in the same column). Create a class Buddy that contains the method pairUp that
takes the number of rows and columns, n, and an int[] representing the
locations of adults, adult, and returns the maximum number of side-by-side
pairs that can be formed while making sure that each child is paired up with
exactly one other child. If there is no way to pair up all the children, it
will return -1.
DEFINITION:
Class: Buddy
Method: pairUp
Parameters: int, int[]
Returns: int
Method Signature (be sure your method is public): int pairUp(int n, int[] adult);
There are n-squared people arranged in a square, with one corner being at
row=1,col=1 and the diagonally opposite at row=n, col=n. adult contains
row,col,row,col,... indicating the location of an adult with each row,col
pair. Each other location in the square is occupied by a child. The same
location may appear more than once in adult, in which case your program should
ignore the redundant appearances.
NOTES
- no child may have more than one buddy
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- n is between 1 and 12 inclusive
- adult contains between 0 and 50 elements inclusive
- adult contains an even number of elements
- each element in adult is between 1 and n inclusive
EXAMPLES
1) n=4, adult = {1,1,4,4}: return -1.
There are 14 children (4 x 4 - 2 adults). It is impossible to pair up all 14
with adjacent neighbors.
2) n=3, adult = {2,2,2,2,2,2}: return 2.
x x y
z A y
z w w
There is one adult in the center of the 3 x 3 square. We can pair the first 2
in row 1 and the last 2 in row 3 as side-by-side buddies, and the remaining 4
children can be paired as front-to-back buddies. This optimal pairing (there
are others) is shown above.
3) n=12, adult = { }: return 72.
All the children can be paired side-by-side. This is 12 x 12 children so 72
side-by-side pairs.
4) n=1, adult = {1,1}: return 0.
There are no children, so they are already paired up! There are 0 side-by-side
pairs.
5) n=12, adult = {12,12}: return -1
|