codechef program #13:Coins And Triangle;codechef program #14: Smallest Numbers of Notes
#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
- 1 ≤ T ≤ 1000
- 1 ≤ 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
Post a Comment