Connection Status:
Competition Arena > CannonBalls

CannonBalls

SRM 288 · 2006-02-08 · by Olexiy

SRM 288 · 2006-02-08 · by Olexiy · Dynamic Programming, Math
Class Name: CannonBalls
Return Type: int
Method Name: fewestPiles
Arg Types: (int)
Problem Statement

Problem Statement

Captain Brown Beard keeps his pirate ship stocked with a healthy supply of cannon balls. Because he is very tidy, he insists that all of the cannon balls be stacked into perfect tetrahedron shapes. Such a pyramid is constructed by arranging cannon balls into an equilateral triangle with side length n. Then, on top of that is stacked an equilateral triangle of side length n-1, and so on, until there is a single cannon ball placed on the top (this single cannon ball is a triangle of side length 1). For example, a stack of size 3 will have three layers that look like this (from top to bottom):

  X

  X
 X X

  X
 X X
X X X

So, each triangle will contain 1, 3, 6, 10, etc. cannon balls. Thus, any complete stack will have 1, 4, 10, 20, etc. cannon balls.

You are given an int n, the number of cannon balls loaded on the ship. You are to return an int indicating the least possible number of stacks into which the cannon balls can be piled.

Constraints

  • n will be between 1 and 300000, inclusive.
Examples
0)
1
Returns: 1

This is the smallest single stack we can make.

1)
5
Returns: 2

A stack with 1 cannon ball, and a stack with 4 cannon balls.

2)
9
Returns: 3

9 = 4 + 4 + 1

3)
15
Returns: 3
4)
40
Returns: 2
5)
91
Returns: 2

91 = 56 + 35

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

Coding Area

Language: C++17 · define a public class CannonBalls with a public method int fewestPiles(int n) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous