TCS Code-Vita Round 1 Challenge: Questions-2017 (The Great Pile Up, what is your rank, Almost Isosceles Right Triangles, Counting the Rational Numbers, Counting the Rational Numbers, Special Triangles)

TCS Code-Vita Round 1

Problem : The Great Pile Up

There are several piles of cards on the table arranged from left to right. All of them do not contain the same number of cards. As the boss insists on symmetry, Ramu is asked to merge the minimum number of adjacent piles so that if a list of the number of cards in each pile is given in left to right order, the list reads the same whether it is read in the left to right order or the right to left order.

For example, if the piles of cards initially were 1 2 2 5 1 3 1 1, there can be three merges (2,2), (5,1) and (3,1) to give 1 4 6 4 1.
Note that merging 3 numbers, say (1,2,2) is counted as 2 merges, one between (1 2) and the next between the resulting 3 and the next two. Hence another solution (1,2,2) (5,1) (3,1,1) resulting in 5 6 5 takes 2 + 2 + 1 or 5 merges, and is not minimal.

Another (trivial) solution is to merge all the piles to give 16. This may be the only solution in some cases, and shows that all initial sets have at least one (not necessarily minimal) solution

Input

There are two lines.
The first line is the number of piles.
The next line contains space separated positive integers, representing the numbers of cards in the piles from left to right.

Output 

If the minimal merge results in more than one pile, the output has two lines, the first giving one integer (the number of merges) and the second containing space separated integers, giving the number of cards in the final pile sequence in order (left to right).
If there is no solution other than merging all into one pile, the output will be a single line containing the letters "TRIVIAL MERGE".

Constraints

The initial number of piles will be less than 50, and the number of cards in each pile in the initial configuration will be less than 1000.

Example 1 

Input:
8
1 4 3 6 1 2 1 5

Output:
3
5 3 7 3 5

Explanation:
If we merge (1 4) , (6 1) and (2 1), (or three merges) the resulting set of piles is 5 3 7 3 5 (which is the same when read from left to right or right to left). As this is the minimum set of merges, the output is 3 (the number of merges) in the first line and 5 3 7 3 5 (the final pile position) in the second line.

Example 2 

Input:
10
1 7 6 2 5 9 7 4 2 8

Output:
3
8 6 7 9 7 6 8

Explanation:
If we merge (1 7) , (2 5) and (4 2), (or three merges) the resulting set of piles is 8 6 7 9 7 6 8 (which is the same when read from left to right or right to left). As this is the minimum set of merges, the output is 3 (the number of merges) and 5 3 7 3 5 (the final pile position).

Example 3 

Input:
10
17 3 15 10 13 18 3 7 20 2

Output:
TRIVIAL MERGE

Explanation:
As there is no set of adjacent merges that results in a set of piles that reads the same both ways other than merging all into one pile (9 merges resulting in a pile with 108 cards), the output is one line, with "RIVIAL MERGE" in it.

Problem : What is your rank

Consider the 10 digits: 0,1,2,3,4,5,6,7,8,9.

There are 10! ( 10 factorial, or 1* 2 * 3 * ... 10) permutations that could be formed using these digits exactly once allowing leading 0 in a permutation. These permutations can be arranged in the increasing lexicographic order (using the collating sequence 0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9). For example, the first sequence in the ordering is 0123456789 and the next number is 0123456798. The last number is of course 9876543210. We will call the position of a permutation in the lexicographic order as the rank of that number. The rank of 0123456789 is 1 and that of 0123456798 is 2. The rank of 9876543210 is 10! = 3628800.

The input will consist of a positive integer T followed by T permutations of the ten digits. Write a program to determine the ranks for each of the T permutations, and compute the remainder when the T ranks are all multiplied and the result is divided by 23456.

Constraints

0 ≤ T ≤ 20

Example 1

Input:
3
9876543210
0123456789
0123456798

Output:
9696

Explanation:
The ranks for the given input permutations are 3628800, 1, and 2. The product of these ranks is 7257600, and the remainder when this is divided by 23456 is 9696. Hence the output is 9696.

Example 2

Input:
4
0123456798
0123456879
0123456897
0123456978

Output:
120

Explanation:
The ranks of the input permutations are 2, 3, 4, 5. The product of these ranks is 120, as is the remainder when this is divided by 23456. Hence the output is 120.

Problem : Almost Isosceles Right Triangles

It can be shown that every right angle triangle with integer sides has at least one side of even length. There are no right angled isosceles triangles with integer side lengths, since the square root of 2 is irrational. Consider the right angled triangle with sides 3, 4, 5. This is almost isosceles. Let us call a right angled triangle with side lengths x, x + 1, y an Almost Isosceles Right Angled triangle – AIRA for short. Such triangles are also called Nearly Isosceles Right Angled triangles. The first two triangles can be computed easily:

(3, 4, 5), (20, 21, 29)

The hypotenuse a_n of these triangles maybe computed by the recurrence relation

a₀=1,b₀=2

a_n=a_n-1+2b_n-1, b_n=2a_n+b_n-1

A factor of a positive integer is a positive integer which divides it completely without leaving a remainder. For example, for the number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself.

The objective of the program is to find the number of factors of the even side of the AIRA that is larger than a given number

Input

The input is a single number N

Output

The number of factors of the even side of the smallest AIRA which has an even side greater than N

Constraints

The even side is less than 5000000

Example 1

Input:
15

Output:
6

Explanation:
The smallest AIRA that has an even side greater than 15 is (20,21,29). The even side is 20, and its factors are (1,2,4,5,10,20), a total of 6 factors. The output is 6

Example 2

Input:
100

Output:
16

Explanation:
The smallest AIRA which has the even side greater than 100 is (119,120,169). The even side is 120, and it has (1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120). As there are 16 factors, the output is 16.

Problem : Counting the Rational Numbers

Georg Cantor proved that the rational numbers form a countably infinite set - that is, we can define a one to one correspondence between the rational numbers and the set of positive integers. One way of showing that the rational numbers are countable is by forming a two-dimensional array as follows:

Such an array would cover all rational numbers. The blank spaces shown as "-" indicate fractions that already appear in their lowest form earlier in the array. One can now count the rationals diagonal after diagonal as follows:

1/1, 2/1, 1/2, 1/3, (2/2 skipped), 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, (2/4, 3/3, 4/2 skipped), 5/1...

Write a program for perform such a counting of positive rational numbers and output the sequence number N corresponding to the input rational number Q. Note that if the input is not in its lowest form, it needs to be reduced to its lowest form before searching.

Input

A line containing a rational number in the form n/m, where n and nm are positive integers

Output

The count of that number using the above approach

Constraints

1≤n, m≤100

Example 1

Input
3/1

Output
5

Explanation

Counting the rationals up to 3/1 as per the above procedure and skipping rationals that are not in their lowest forms, 3/1 is seen to be the 5th in the countable list. Hence N = 5.

Example 2

Input
2/3

Output
8

Explanation
The input rational is 2/3. Using the above procedure, the count is 8. Hence the output is 8.

Problem : Counting the Rational Numbers

Georg Cantor proved that the rational numbers form a countably infinite set - that is, we can define a one to one correspondence between the rational numbers and the set of positive integers. One way of showing that the rational numbers are countable is by forming a two-dimensional array as follows:

Such an array would cover all rational numbers. The blank spaces shown as "-" indicate fractions that already appear in their lowest form earlier in the array. One can now count the rationals diagonal after diagonal as follows:

1/1, 2/1, 1/2, 1/3, (2/2 skipped), 3/1, 4/1, 3/2, 2/3, 1/4, 1/5, (2/4, 3/3, 4/2 skipped), 5/1...

Write a program for perform such a counting of positive rational numbers and output the sequence number N corresponding to the input rational number Q. Note that if the input is not in its lowest form, it needs to be reduced to its lowest form before searching.

Input

A line containing a rational number in the form n/m, where n and nm are positive integers

Output

The count of that number using the above approach

Constraints

1≤n, m≤100

Example 1

Input
3/1

Output
5

Explanation

Counting the rationals up to 3/1 as per the above procedure and skipping rationals that are not in their lowest forms, 3/1 is seen to be the 5th in the countable list. Hence N = 5.

Example 2

Input
2/3

Output
8

Explanation
The input rational is 2/3. Using the above procedure, the count is 8. Hence the output is 8.

Problem : Special Triangles

When we have 4 lines in the plane, the maximum number of triangles formed by them is 4 as shown below: Of the four triangles ABF, CDF, BDE, ACE, triangles BDE and CDF are somewhat "special". They do not have another of the given lines go through their interiors.



Given n lines in the plane, the objective is to count the number of special triangles formed by them. You may assume that no three lines will be concurrent (go through the same point). Each line will be specified by two points (x and y coordinates of two points on the line).

Note that three lines may not form a triangle, let alone a special triangle, if two of them are parallel lines.

Input

The first line will have a single integer, N, representing the number of lines in the input.

The next N lines will have four comma separated numbers representing x₁, y₁, x₂, y₂, (the x and y coordinates of two points on the line.)

Output

The output is a single line giving the number of special triangles formed.

Constraints

N≤20

Each of the x and y coordinates of the points defining any line lies between -10 and 10.

Example 1

Input
4
1,2,4,7
2,3,2,5
3,5,7,5
4,7,3,4

Output
2

Explanation


Line I is defined by the points (1,2) (A) and (4,7) (B). Similarly, line II is defined by C (2,3) and D (2,5), line III by E (3,5) and F(7,5) and line IV by B (4,7) and G (3,4).

Of the four triangles formed by the four lines, the ones by (I,II,III) and (I,III,IV) are special.

(I,II,IV) has III going through the interior, while (II,III,IV) has I going through the interior.

As only two triangles are special, the output is 2.

Example 2

Input
4
2,2,3,2
2,3,3,3
2,4,3,4
2,5,3,5

Output
0

Explanation
As all lines are parallel to the x axis, there are no triangles, and hence no special triangles. The output is 0.

Problem : Vaults in Bank

In the strong room of ABC bank there are N vaults in a row. The amount of money inside each vault displayed on the door. You can empty any number of vaults as long as you do not empty more than 2 out of any 5 adjacent vaults. For example, of the vaults 1, 2, 3, 4, 5, if you empty 4 and 5, then you can not empty any of the vaults 6, 7 or 8 but you can empty 9th vault. If you attempt to break more than 2 of any 5 adjacent vaults, an alarm sounds and the sentry, a sharp shooter will kill you instantly with his laser gun!

The output is the maximum amount of money that can be emptied without sounding the alarm

Input

The first line contains an integer N which is the number of vaults. The next line has a sequence of positive integers of length N, giving the amount of cash in the vaults in order

Output

The maximum amount of money that can be looted without sounding the alarm.

Constraints

N≤50, Amount in each vault ≤50000

Example 1

Input:
9
1000, 2000, 1000, 5000, 9000, 5000, 3000, 4000, 1000

Output:
15000

Explanation:
One possible set of vaults to be looted to get the maximum possible are vaults 4, 5, 9 are looted, giving a total loot of (5000+9000+1000)=15000. Hence the output is 15000.

Example 2

Input:
10
5000,7000,3000,5000,9000,7000,6000,4000,7000,5000

Output:
28000

Explanation:
One possible set of vaults to be looted are (2, 5, 9, 10) Note that no set of five consecutive vaults has more than two vaults looted. The total looted is (7000 + 9000 + 7000 + 5000=28000). The out put is hence 28000.

Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.

Note:

Participants submitting solutions in C language should not use functions from <conio.h> / <process.h> as these files do not exist in gcc

Note:

For C and C++, return type of main() function should be int.

NOTE:- Check the given details clearly and this https://raviraobplcivilian.blogspot.in/ (web page)goo.gl/Q4aBgj is not responsible for any inconvinence or other requirements. 

*These information & links are taken from goo.gl/CDoRxB*

© 2017 Tata Consultancy Services Limited.