Connection Status:
Competition Arena > ToniasTower

ToniasTower

SRM 842 · 2022-12-01 · by misof

SRM 842 · 2022-12-01 · by misof · Brute Force, Greedy, Simple Math
Class Name: ToniasTower
Return Type: int[]
Method Name: build
Arg Types: (int)
Problem Statement

Problem Statement

Tonia has N unit cubes. She wants to use all of them to build a tower.

Tonia's tower will consist of one or more rows of cubes, each row standing on the next one. (Obviously, except for the bottom row that stands on the ground.)

There is only one restriction: each row other than the bottom one must be strictly shorter (i.e., have strictly fewer cubes) than the row on which it stands.


Tonia now wonders: what is the tallest tower she can build out of all her cubes?

Find the largest X such that Tonia can use her N cubes to build a tower with X rows of cubes. Then, find one way of building such a tower. In other words, determine the number of cubes in each of the X rows of the tower.

Return a int[] with X elements: for each row of the tower, from top to bottom, the number of cubes Tonia should use in that row.

Notes

  • The return value must be sorted in ascending order and the sum of all its elements must be exactly N.
  • If there are multiple optimal answers, any one of them will be accepted.

Constraints

  • N will be between 1 and 100,000, inclusive.
Examples
0)
1
Returns: {1 }

Tonia has a single cube. She has no choice: she has to build a tower with one row, consisting of that one cube.

1)
15
Returns: {1, 2, 3, 4, 5 }

With 15 cubes Tonia can build a nice tower with five rows, consisting of 1, 2, 3, 4, and 5 cubes. A schematic side view of one way of building such a tower is shown below: each letter from A to O represents one of the cubes. AA AA BBCC BBCC DDEEFF DDEEFF GGHHIIJJ GGHHIIJJ KKLLMMNNOO KKLLMMNNOO

2)
5
Returns: {1, 4 }

The best she can do with five cubes is a tower with two rows. There are two different ways of building such a tower, and therefore two correct answers you may return: {1, 4} and {2, 3}. Either of these will be accepted. (Remember that Tonia must use all her cubes. Hence, {1, 2} and {1, 3} are not acceptable answers, even though they describe towers of the same height.)

3)
20
Returns: {1, 2, 4, 5, 8 }

Several other optimal solutions exist. The description of any valid tower that consists of exactly 20 cubes and has exactly 5 rows will be accepted.

4)
2
Returns: {2 }

Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ToniasTower with a public method vector<int> build(int N) · 43 test cases · 2 s / 256 MB per case

Submitting as anonymous