BlockTower
SRM 559 · 2012-06-05 · by tehqin
SRM 559 · 2012-06-05 · by tehqin · Brute Force, Simple Search, Iteration
Problem Statement
Problem Statement
Josh loves playing with blocks. Currently, he has N blocks, labeled 0 through N-1. The heights of all blocks are positive integers. More precisely, for each i, the height of block i is blockHeights[i]. Josh is interested in making the tallest block tower possible. He likes all his towers to follow three simple rules:
int[] blockHeights. Return the height of the tallest possible block tower Josh can build.
- The blocks must be stacked in a single column, one atop another. The height of the tower is simply the sum of heights of all its blocks.
- The labels of blocks used in the tower must increase from the bottom to the top. In other words, whenever Josh places box x on top of box y, we have x > y.
- Josh will never place a box of an even height on top of a box of an odd height.
Constraints
- blockHeights will contain between 1 and 50 elements, inclusive.
- Each element of blockHeights will be between 1 and 50, inclusive.
Examples
0)
{4,7}
Returns: 11
The optimal tower contains both blocks. Block 0 is on the bottom of the tower.
1)
{7,4}
Returns: 7
This time the optimal tower contains just block 0. Josh cannot put block 1 on top of it, because 4 is even and 7 is odd.
2)
{7}
Returns: 7
3)
{4}
Returns: 4
4)
{48,1,50,1,50,1,48}
Returns: 196
Note that in a valid tower the labels of the blocks have to increase from bottom to top. Their heights do not have to. In this case the optimal tower consists of blocks 0, 2, 4, and 6, in this order. Its total height is 48 + 50 + 50 + 48 = 196.
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BlockTower with a public method int getTallest(vector<int> blockHeights) · 124 test cases · 2 s / 256 MB per case