codechef program #13:Coins And Triangle;codechef program #14: Smallest Numbers of Notes

tricoin

#1: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 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.

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

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 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.


My Solution:


import java.util.*;
class tricoin
{

public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int a=in.nextInt();
for(int i=0;i<a;i++)
{
 int w=in.nextInt();
int ans=(-1+(int)Math.sqrt(1+(8*w)))/2;;

 System.out.println(ans);
}



}
}

Problem Statement #2



Consider a currency system in which there are notes of seven denominations, namely, Rs. 1, Rs. 2, Rs. 5, Rs. 10, Rs. 50, Rs. 100. If the sum of Rs. N is input, write a program to computer smallest number of notes that will combine to give Rs. N

Input

The first line contains an integer T, total number of testcases. Then follow T lines, each line contains an integer N.

Output

Display the smallest number of notes that will combine to give N.

Constraints

  •  T  1000
  •  N  1000000

Example

Input
3 
1200
500
242

Output
12
5
7

My Solution



import java.util.*;
class Smallnotes
{

public static void main(String args[])
{
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int c=0;
for(int i=0;i<a;i++)
{

int b=in.nextInt();
if(b>100)

{

c+=b/100;
b=b%100;
}

if(b>=50&&b!=0)
{
c+=b/50;
b=b%50;
}
if(b>=10&&b!=0)
{
c+=b/10;
b=b%10;
}
if(b>=5&&b!=0)
{
c+=b/5;
b=b%5;
}
if(b>=2&&b!=0)
{
c+=b/2;
b=b%2;
}
if(b>=1&&b!=0)
{
c+=b/1;
b=b%1;
}
System.out.println(c);
c=0;
}
}
}

Comments

Popular Posts