Problem Statement
Manao is given a sequence of squares numbered from 0 to N-1. The i-th square has side length equal to 2^a[i].
In the beginning, there is only an empty plane. Manao will process the squares one after another, in the order in which they are given. He will pick a parent object for each of the squares and then move the square onto its parent object. The parent object can be either the plane or one of the already processed squares. Each square must lie entirely within (or exactly cover) its parent object. Also, two children of the same object must never have an intersection with a positive area. (I.e., siblings may share a common boundary but they must not overlap.)
Given an int[] a, return the minimum possible covered area of the plane at the end of the process described above.
In the beginning, there is only an empty plane. Manao will process the squares one after another, in the order in which they are given. He will pick a parent object for each of the squares and then move the square onto its parent object. The parent object can be either the plane or one of the already processed squares. Each square must lie entirely within (or exactly cover) its parent object. Also, two children of the same object must never have an intersection with a positive area. (I.e., siblings may share a common boundary but they must not overlap.)
Given an int[] a, return the minimum possible covered area of the plane at the end of the process described above.
Definition
- Class:
- PackingSquares
- Method:
- leastArea
- Parameters:
- int[]
- Returns:
- long
- Method signature:
- long leastArea(int[] a)
- (be sure your method is public)
Notes
- The answer will always fit in a signed 64-bit integer.
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will be between 0 and 30, inclusive.
Examples
{0, 1, 2}Returns: 21
Manao has three squares with side lengths 1, 2 and 4. The parent for the first square can only be the plane. Since the second square does not fit into the first one, its parent should also be the plane. The same happens to the third square. Thus, the area used on the plane is equal to 1 + 4 + 16 = 21.{1, 0, 0, 0, 0, 0, 0, 0}Returns: 4
The square 0 is put on the plane. For each i > 0, square i-1 can be the parent of square i.{2, 1, 0, 2, 1}Returns: 20
Manao can use 20 units of the plane if he assigns parents as follows: Square 0: plane. Square 1: plane. Square 2: square 1. Square 3: square 0. Square 4: square 3.{30, 0, 1}Returns: 1152921504606846976
The square of side 2^30 is placed on the plane. The square of side 1 can then be placed in the square of side 2^30. Finally the square of side 2 can not be placed in the square of side 1, but can be placed in the square of side 2^30 without intersecting its sibling square of side 1.{6, 5, 12, 15, 14, 5, 6, 5, 13, 15, 11, 11}Returns: 1358958592
Back to all problems