PHT - Pigeonhole Tower

no tags 

Pigeon SSNA want to build a tower with some wood walls. Let's describe the tower they want to make:

  1. A Tower can consist of different number of level.
  2. If a tower contain levels then 1st level must contain  holes , 2nd level L-1 , 3rd level L-2 ….. L level contain 1 hole .
  3. Each room contain 3 wood walls.

See the picture below:

3 level 4level
3 Level Tower 4 Level tower

Now pigeon SSNA has n wood walls. What is maximum number of level he can made.


Input starts with an integer T (≤ 100000), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 1012)


For each case of input you have to print the case number and expected answer.

Sample Input

Output for Sample Input

Case 1: 3
Case 2: 4

hide comments
ritun_1999: 2020-04-06 04:11:59

My O(1) solution is showing TLE...Please help.

mrdevesh_00: 2019-12-18 20:55:41

AC in one go!!!!

aryan29: 2019-06-01 01:12:01

Waste of time easy question just make a formula

deku__: 2019-05-10 05:38:48

So you are given no. of walls as input and you're expected to find no. of levels. You can use A.P concept to solve it.

kshubham02: 2019-04-14 16:43:09

ok ended up solving without the figure. For the record for level = 3, the tower looks like this -
where | and __ denote a wood wall being used.

Last edit: 2019-04-14 16:46:13
kshubham02: 2019-04-14 16:10:39
URL broken. Image not visible. Please fix.

silentknight16: 2019-02-18 18:03:02

AC in one go!!!

akt_114: 2018-08-08 20:42:53

AC in one go !!

oneinchatatime: 2018-07-18 18:53:16


amankumarkeshu: 2018-05-28 06:18:32

Can anyone see the image of the picture ?

Added by:Ajharul Islam Barid
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Own Problem