Connection Status:
Competition Arena > BlockTower

BlockTower

SRM 559 · 2012-06-05 · by tehqin

SRM 559 · 2012-06-05 · by tehqin · Brute Force, Simple Search, Iteration
Class Name: BlockTower
Return Type: int
Method Name: getTallest
Arg Types: (vector<int>)
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:
  1. 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.
  2. 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.
  3. Josh will never place a box of an even height on top of a box of an odd height.
You are given the int[] blockHeights. Return the height of the tallest possible block tower Josh can build.

Constraints

  • blockHeights will contain between 1 and 50 elements, inclusive.
  • Each element of blockHeights will be between 1 and 50, inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

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

Submitting as anonymous