Problem solving Set II

1. Packaging Cupcakes
Now that Chef has finished baking and frosting his cupcakes, it's time to package them. Chef
has N cupcakes, and needs to decide how many cupcakes to place in each package. Each package must
contain the same number of cupcakes. Chef will choose an integer A between 1 and N, inclusive, and place
exactly A cupcakes into each package. Chef makes as many packages as possible. Chef then gets to eat the
remaining cupcakes. Chef enjoys eating cupcakes very much. Help Chef choose the package size A that
will let him eat as many cupcakes as possible.

Input
Input begins with an integer T, the number of test cases. Each test case consists of a single integer N, the
number of cupcakes.

Output
For each test case, output the package size that will maximize the number of leftover cupcakes. If multiple
package sizes will result in the same number of leftover cupcakes, print the largest such size.

Constraints
 1 ≤ T ≤ 1000
 2 ≤ N ≤ 100000000 (108)

Sample Input
2
2
5

Sample Output
2
3

Explanation
In the first test case, there will be no leftover cupcakes regardless of the size Chef chooses, so he chooses
the largest possible size. In the second test case, there will be 2 leftover cupcakes.

2. Reverse The Number

If an Integer N, write a program to reverse the given number.

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 reverse of the given number N.

Constraints
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 100000

Example
Input
4
12345
31203
2123
2300
Output
54321
30213
3212
32

3. Finding Square Roots

In olden days finding square roots seemed to be difficult but nowadays it can be easily done using in-built
functions available across many languages.
Assume that you happen to hear the above words and you want to give a try in finding the square root of
any given integer using in-built functions. So here's your chance.

Input
The first line of the input contains an integer T, the number of test cases. T lines follow. Each T contains an
integer N whose square root needs to be computed.

Output
For each line of input output the square root of the input integer.

Constraints
1<=T<=20
1<=N<=10000
Input:
3
10
5
10000

Output:
3
2
100

4. Ciel and Receipt

Tomya is a girl. She loves Chef Ciel very much.
Tomya like a positive integer p, and now she wants to get a receipt of Ciel's restaurant whose total price is
exactly p. The current menus of Ciel's restaurant are shown the following table.
Name of Menu price
eel flavored water 1
deep-fried eel bones 2
clear soup made with eel livers 4
grilled eel livers served with grated radish 8
savory egg custard with eel 16
eel fried rice (S) 32
eel fried rice (L) 64
grilled eel wrapped in cooked egg 128
eel curry rice 256
grilled eel over rice 512
deluxe grilled eel over rice 1024
eel full-course 2048
Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12).
Since Tomya is a pretty girl, she cannot eat a lot. So please find the minimum number of menus whose total
price is exactly p. Note that if she orders the same menu twice, then it is considered as two menus are
ordered.

Input
The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case
contains an integer p.

Output
For each test case, print the minimum number of menus whose total price is exactly p.

Constraints
1≤T≤5
1 ≤ p ≤ 100000 (105)
There exists combinations of menus whose total price is exactly p.

Sample Input
4
10
256
255
4096

Sample Output
2
1
8
2

Explanations
In the first sample, examples of the menus whose total price is 10 are the following:
1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)
1+1+1+1+1+1+1+1+2 = 10 (9 menus)
2+2+2+2+2 = 10 (5 menus)
2+4+4 = 10 (3 menus)
2+8 = 10 (2 menus)
Here the minimum number of menus is 2.
In the last sample, the optimal way is 2048+2048=4096 (2 menus). Note that there is no menu whose price
is 4096.

5. Second Largest
Three numbers A, B and C are the inputs. Write a program to find second largest among three numbers.

Input
The first line contains an integer T, total number of testcases. Then follow T lines, each line contains three
integers A, B and C.

Output
Display the second largest among A, B and C.

Constraints
 1 ≤ T ≤ 1000
 1 ≤ A,B,C ≤ 1000000

Example
Input
3
120 11 400
10213 312 10
10 3 450

Output
120
312
10

6. Chef and Remissness

Chef is now a corporate person. He has to attend office regularly. But chef does not want to go to office,
rather he wants to stay home and discover different recipes and cook them.
In the office where chef works, has two guards who count how many times a person enters into the office
building. Though the duty of a guard is 24 hour in a day, but sometimes they fall asleep during their duty
and could not track the entry of a person in the office building. But one better thing is that they never fall
asleep at the same time. At least one of them remains awake and counts who enters into the office.
Now boss of Chef wants to calculate how many times Chef has entered into the building. He asked to the
guard and they give him two integers A and B, count of first guard and second guard respectively.
Help the boss to count the minimum and maximum number of times Chef could have entered into the
office building.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of
the T test cases follows.
Each test case consists of a line containing two space separated integers A and B.

Output
For each test case, output a single line containing two space separated integers, the minimum and
maximum number of times Chef could have entered into the office building.

Constraints
 1 ≤ T ≤ 100
 0 ≤ A, B ≤ 1000000

Example
Input:
1
19 17

Output:
19 36

7. Servant
Write a program, which takes an integer N and if the number is less than 10 then display "What an obedient
servant you are!" otherwise print "-1".

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

Output
Output the given string or -1 depending on conditions.

Constraints
 1 ≤ T ≤ 1000
 -20 ≤ N ≤ 20

Example
Input
3
1
12
-5
Output
What an obedient servant you are!
-1
What an obedient servant you are!

8. Sums in a Triangle
Let's consider a triangle of numbers in which a number appears in the first line, two numbers appear in the
second line, three in the third line, etc. Develop a program which will compute the largest of the sums of
numbers that appear on the paths starting from the top towards the base, so that:
 on each path the next number is located on the row below, more precisely either directly below or
below and one place to the right;
 the number of rows is strictly positive, but less than 100
 all numbers are positive integers between 0 and 99.

Input
In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each
test case starts with the number of lines which is followed by their content.

Output
For each test case write the determined value in a separate line.

Example
Input:
2
3
1
21
123
4
1
12
412
2311

Output:
5
9

9. Chef And Operators

Chef has just started Programming; he is in first year of Engineering. Chef is reading about Relational
Operators.
Relational Operators are operators which check relationship between two values. Given two numerical
values A and B you need to help chef in finding the relationship between them that is,

Input
First line contains an integer T, which denotes the number of testcases. Each of the T lines contain two
integers A and B.

Output
For each line of input produce one line of output. This line contains any one of the relational operators
'<' , '>' , '='.

Constraints
T ≤ 10000
A, B ≤ 1000000001

Example
Input:
3
10 20
20 10
10 10

Output:
<
>
=

Explanation
Example case 1. In this example 1 as 10 is lesser than 20.

10. Smallest Numbers of Notes

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

11. Ambiguous Permutations

Some programming contest problems are really tricky: not only do they require a different output format
from what you might have expected, but also the sample output does not show the difference. For an
example, let us look at permutations.
A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a
permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation: You create a list of numbers where
the i-th number is the position of the integer i in the permutation. Let us call this second possibility
an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation.
The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get
rid of such annoying sample test cases, you have to write a program which detects if a given permutation is
ambiguous or not.

Input Specification
The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 100000). Then a permutation of the
integers 1 to n follows in the next line. There is exactly one space character between consecutive integers.
You can assume that every integer between 1 and n appears exactly once in the permutation.
The last test case is followed by a zero.

Output Specification
For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the
sample output.

Sample Input
4
1432
5
23451
1
1
0

Sample Output
ambiguous
not ambiguous
ambiguous

12. Valid Triangles

Write a program to check whether a triangle is valid or not, when the three angles of the triangle are the
inputs. A triangle is valid if the sum of all the three angles is equal to 180 degrees.

Input
The first line contains an integer T, total number of testcases. Then follow T lines, each line contains three
angles A, B and C of triangle separated by space.

Output
Display 'YES' or 'NO' if the triangle is Valid or not respectively.

Constraints
 1 ≤ T ≤ 1000
 1 ≤ A,B,C ≤ 180

Example
Input

3
40 40 100
45 45 90
180 1 1
Output

YES
YES
NO