Posted in GCJ

GCJ Post #3

Continuing with my said goal ( solving 5 problems per day) This is what I did for the 2 days…

((งง •̀•̀__•́•́))งง


I have planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.
On a more personal note, I have read somewhere that re-reading the  decision made extends the life of the decision!!

So the list of problems that were chosen the last 2 days were:

  1. Laddu
  2. Akhil and colored balls
  3. Kitchen Time Table
  4. Chef And Way
  5. Alternating sub-array prefix
  6. Simple Statistics
  7. Palindrome Substrings
  8. Chef and Coloring
  9. Movie Weekend
  10. Coins and Triangle
So the lot picked problem for today is 

Coins And Triangle

*Well, actually the first lot fell to NO. 8 but it was too easy… So I thought I’ll pick again?*

The problem statement :

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn’t it strange?

Chef has an unusual way of forming a triangle using gold coins, which is described as follows:

He puts 1 coin in the 1st row.
then puts 2 coins in the 2nd row.
then puts 3 coins in the 3rd row.

The chef is interested in forming a triangle with maximum possible height using at most N coins. Can you tell him the maximum possible height of the triangle?

Input

The first line of input contains a single integer T denoting the number of test cases.

The first and the only line of each test case contains an integer N denoting the number of gold coins Chef has.

Output

For each test case, output a single line containing an integer corresponding to the maximum possible height of the triangle that Chef can get.

Constraints

1 = T = 100
1 = N = 109

Example

Input
3
3
5
7

Output
2
2
3

Explanation

Test 1: Chef can’t form a triangle with height > 2 as it requires at least 6 gold coins.
Test 2: Chef can’t form a triangle with height > 2 as it requires at least 6 gold coins.
Test 3: Chef can’t form a triangle with height > 3 as it requires at least 10 gold coins.

You are given a number N that represents the number of coins you have and you have to print the maximum possible height H of the triangle which can be made from these coins in such a way that ith row of the triangle contains i coins.

Pretty simple if you know the sum of first N natural numbers?

T = int(input());
for i in range(T):
   n = int(input());
   int h = 1;
   while((h * (h+1) / 2) <= n):
      h ++;
   print (h-1);


But I wasn’t satisfied…the answer was too direct for my liking so I was twisting the code to my liking?


So the code I came up with is this… pretty simple, right? 
t = int(input())
n = [int(input()) for i in range(t)]
for i in n:
height = triangle_height(i)
print(height)

def triangle_height(n_coin):
    height = 1
    coins = 1
    inc = 2
    while coins < n_coin:
        coins += inc
        if coins > n_coin:
            break
        inc += 1
        height += 1
    return height

// Or maybe not that different… oh well whatever…
ʕ ಡ ﹏ ಡ ʔ
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s