Algorithm

 problem Link : https://www.codechef.com/problems/TRICOIN 

Problem

Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.

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 a 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.
  • and so on as shown in the given figure.

1461147954-8b9f4b7d27-A.png

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

Subtasks

  • Subtask 1 (48 points) : 1 ≤ N ≤ 105
  • Subtask 2 (52 points) : 1 ≤ N ≤ 109

Sample 1:

Input
 
Output
 
3
3
5
7
2
2
3

Explanation:

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

 

Code Examples

#1 Code Example with C Programming

Code - C Programming

  #include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned long long
#define pb push_back
#define ss second
#define ff first
#define fr(m) for (int i = 0; i  <  m; i++)
#define fro(m) for (int i = 1; i  <  m; i++)
#define frj(m) for (int j = 0; j  <  m; j++)
#define frr(n) for (int i = n; i >= 0; i--)
#define nl '\n'
#define yes cout << "YES" << nl
#define no cout << "NO" << nl
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << " " << x << endl;
#define fast_io (ios_base::sync_with_stdio(false), cin.tie(NULL));

ll fact(ll n)
{
    if (n == 0)
        return 1;
    ll res = 1;
    for (ll i = 2; i  < = n; i++)
        res = res * i;
    return res;
}
ll nPr(ll n, ll r) { return fact(n) / fact(n - r); }
ll nCr(ll n, ll r) { return fact(n) / (fact(r) * fact(n - r)); }
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll mypow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a);
        b /= 2;
        a = (a * a);
    }
    return ans;
}
bool isPrime(ll n)
{
    if (n  < = 1)
        return false;
    for (ll i = 2; i  < = sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

#define PI 3.141592653589793238;
#define INF LONG_LONG_MAX;
#define MOD 1e9 + 7;

//////////////////////////////////Code Start/////////////////////////////////////

void solve()
{
    int n, i, m;
    cin >> n;
    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }
    for (i = 1; i  <  n; i++)
    {
        m = (i * i + i) / 2;
        if (m > n)
            break;
    }
    cout << i - 1 << endl;
}

int main()
{
    fast_io;
    int TC = 1;
    cin >> TC;
    while (TC--)
        solve();
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3 3 5 7

Output

x
–
+
cmd
2 2 3
Advertisements

Demonstration

CodeChef solution TRICOIN  - Coins and Triangle  Codechef solution in C,C++

Previous
CodeChef solution RIP2000 - 2000 Codechef solution in C,C++
Next
CodeChef solution CHEFBOTTLE =- Chef and Water Bottles Codechef solution in C,C++