OBSTACLE GAME | Code vita 2018

Given a n*n Array matrix (A) with A[0][0] element as the starting point and any one element as the destination.

Problem Description

Given a n*n Array matrix (A) with A[0][0] element as the starting point and any one element as the destination. Find the destination and print the route map.

Rules:

1. Array Matrix with n*n elements such that n >=2 and n<=10.

2. Starting point A[0][0] value will be 'A'.

3. Destination value will be 'D'

4. There will be always 1 continuous route which can be straight or diagonal.

5. There are 4 types of hurdles and corresponding values :

a. Stone denoted by 'S'

b. Wall denoted by 'L'

c. Water denoted by 'W'

d. Thorn denoted by 'T'

6. Music provides mind peace. Which will be denoted by 'M'. It is not a hurdle.

6. The value of route will be 'R'.

Input

First Line contains dimension N of Matrix A.

Next N Lines, each contains N values delimited by space

Output

At every Step print the surrounded hurdles in ascending order of values. i.e. for every 'R' print the surrounding hurdles.

If there are no hurdled around step in the route, print 'NO HURDLES' for that step.

On reaching destination print 'DESTINATION'

Music 'M' is not a hurdle. It should not be included in output.

Constraints

2 <= N <= 20

Example 1

Input

4

A S L D

T R W R

R M S R

W R R M

  

Output:

L S S T W

T W

S W

S

S W

L S W

DESTINATION

Example 2

Input:

5

A S L W M

R S L D T

M R T R M

T L R M S

S L S W T

Output:

S S

L L S T T

L L S T W

L S T T

DESTINATION

INCREASING SUBSEQUENCE WITH LARGEST SUM | Code vita 2017

Problem Description:

Given a sequence a1, a2, ..... an, of positive integers, a strictly increasing subsequence is a subsequence of the given sequence such that each term of the subsequence is strictly less than the next. For example, in the sequence 1, 2, 10, 3, 7 , 4, two strictly increasing sub sequences are 1, 10 and 2, 3, 4

The Input consists of N sets of five integers each. From these sets, a derived sequence is formed by selecting one of the five numbers in each set as part of the sequence.   

The objective is to pick the numbers from each set so that the corresponding derived sequence has the strictly increasing subsequence with the largest sum. 

Input 

The first line of the input has a positive integer N which is the number of sets of the numbers in the input. Each of the next N lines consists of a set of five (not necessarily distinct) comma separated positive integers. 

Output 

The sum of the elements of the longest strictly increasing subsequence in all possible derived sequences 

Constraints   

N<=50 
Integers in sets<=10000

Example 1    

Input:  

5 
3000,400,1500,4350,2700 
2050,3650,650,2750,4300 
2000,700,2100,700,1650 
300,200,500,600,200 
3000,3100,3200,1100,1400 

Output: 

8850 

Explanation: 

A possible derived sequence from the input which gives the maximum sum for a strictly increasing subsequence is 1500,2050,2100,500,3200 (one from each row), and the strictly increasing subsequence that gives the maximum sum from this from this is 1500,2050,2100,3200, whose sum is 8850, which is the output

Example 2    

Input:  

6
800,3000,600,3600,800 
1400,5200,1600,6000,2600
3200,3800,3200,1600,2400
800,2800,4800,600,1400
5200,1400,4800,3800,800
5000,4200,4800,1800,2000 

Output:  

17400 

Explanation:  

A possible derived sequence that gives a maximum sum for a strictly increasing subsequence is 800, 1600, 2400, 2800, 4800, 5000. All appear in the strictly increasing subsequence, and the sum is 17400, which is the output

SKYLINE | Code vita 2017

Problem Description:

Humans have now set up housing societies on the moon, where the societies are very large, and each building can be very high. There are N consecutive buildings in a society. The owners decided to increase the heights of the buildings. Being aesthetically oriented, they wanted to ensure that the heights (all measured as number of floors in the building) of consecutive buildings differ at most by one floor so that the skyline of the buildings look pleasing. That is, if the heights of the buildings are h1, h2, ... hn, then after the height increase, their heights become H1, H2, .... Hn such that ­1 <= Hi ­ H(i+1) <= 1 for all i = 1, 2, ...n­1. The modification is made such that the total number of floors added to the society is a minimum.

The owner of the pth building wants to know what will be the height of his building before agreeing to this plan for modification, Given the initial heights of the buildings, can you write a program to answer the query pth owner has?  

Input    

T number of test cases   

A set of 2 lines for each of the T test cases containing   

N, the number of buildings, P the position the building for which we want to know the height after modification   

N space separated integers showing the original heights of the buildings 

Output    

T lines containing   

height of the Pth building after modification for each of the T test cases   

Constraints   

1<=T<=50   

1<=N<=104 P<=N   

1<=height of each building <= 5000 (There are very tall buildings in the society) 

Example 1  

Input:  

1  

7 4  

9 5 17 7 10 2 18   

Output:  

16   

Explanation:  

After modification the heights will become 15 16 17 16 16 17 18. Hence the fourth building will have height 16 floors.   

Example 2    

Input:  

1  

13 12  

34 80 56 41 16 39 70 85 73 75 20 33 83   

Output:  

82   

Explanation:  

After modification, the heights would be  79 80 80 81 82 83 84 85 84 83 82 82 83

ON A CUBE | Code vita 2017

Problem Description:

A solid cube of 10 cm x 10cm x 10 cm rests on the ground. It has a beetle on it, and some sweet honey spots at various locations on the surface of the cube.  The beetle starts at a point on the surface of the cube, and goes to the honey spots in order along the surface of the cube.

1. If it goes from a point to another point on the same face (say X to Y), it goes in an arc of a circle that subtends an angle of 60 degrees at the centre of the circle

2. If it goes from one point to another on a different face, it goes by the shortest path on the surface of the cube, except that it never travels along the bottom of the cube

The beetle is a student of Cartesian geometry, and knows the coordinates (x, y, z) of all the points it needs to go to. The origin of coordinates it uses is one corner of the cube on the ground, and the z axis points up. Hence, the bottom surface (on which it does not crawl) is z=0, and the top surface is z=10. The beetle keeps track of all the distances travelled, and rounds the distance travelled to two decimal places once it reaches the next spot, so that the final distance is a sum of the rounded distances from spot to spot.

Input Format:

The first line gives an integer N, the total number of points (including the starting point) the beetle visits

The second line is a set of 3N comma separated non-negative numbers, with up to two decimal places each. These are to be interpreted in groups of three as the x, y, z coordinates of the points the beetle needs to visit in the given order

Output Format:

One line with a number giving the total distance travelled by the beetle accurate to two decimal places. Even if the distance travelled is an integer, the output should have two decimal places.

Constraints:

None of the points the beetle visits is on the bottom face (z=0) or on any of the edges of the cube (the lines where two faces meet)

2≤N≤10

Example 1

Input

3

1,1,10,2,1,10,0,1,9

Output

4.05

Explanation

There are three points visited by the beetle (N=3). The beetle starts on the top face of the cube (z=10) at point (1,1,10) and goes to another point on the same face (2,1,10). Though the straight line distance is 1, it travels on the arc of a circle subtending an angle of 60 degrees at the centre of the circle, and hence travels (2*π)/6 or 1.05 (note that it rounds the distance at each leg of the journey). It then travels from (2,1,10) on the face z=10 to (0,1,9) on the face x=0 along the surface of the cube. This is a distance of 3. The total distance travelled is 1.05+3=4.05. The output is 4.05

Example 2

Input

3

1,1,10,2,1,10,0,5,9

Output

6.05

Explanation

There are three points visited by the beetle (N=3). The beetle starts on the top face of the cube (z=10) at point (1,1,10) and goes to another point on the same face (2,1,10). As before. This distance is 1.05. It then travels from (2,1,10) on the face z=10 to (0,5,9) on the face x=0 along the surface of the cube. The shortest distance on the surface of the cube between these points is 5. The total distance travelled is 1.05+5=6.05. The output is 6.05

CONTINUOUS NIVEN NUMBERS | Code vita 2017

Problem Description:

In recreational mathematics, a Niven number in a given number base, is an integer that is divisible by the sum of its digits when written in that base. For example, in base 10, 18 is a Niven number since 18 is divisible by 1+8 = 9. Also, 12001 in base 3 is also a Niven number since the sum of the digits is 4 (which is 11 in base 3) divides 12001 (12001 = 1021 x 11).

Given a base b, any number n < b is trivially a Niven number. We will ignore this case.

Given a base b, and a positive integer T, find the lowest number L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Input Format:         

First line contains two integers, b and T

Output Format:

A single integer L such that L, L+1, ..., L+T-1 are all Niven numbers but neither L-1 nor L+T are Niven numbers.

Constraints:

2 ≤ b ≤ 10

1 < T < 7

Example 1

Input

10 4

Output

510

Explanation

510, 511, 512 and 513 are Niven numbers and 514 is not a Niven number. Also 509 is not a Niven number. It can be seen that for N < 510, no four consecutive numbers are Niven numbers.

Example 2

Input

5 5

Output

44

Explanation

44 in base 5 is equivalent to 24 in base 10. Clearly, sum of the digits is 8 = 13 in base 5 and 13 x 3 = 44 in base 5 and hence 44 is a Niven number. Similarly we can see 44+1 = 100, 101, 102 and 103 in base 5 are also Niven numbers. 104 is not a Niven number.

COUNTING NUMERIC SUBSEQUENCES | Code vita 2017

Problem Description:

If one is given a string of length N, there are two ways of specifying substrings of it. One way is to give the string representation, namely the substring itself. The other way is to specify a numeric subsequence of the numbers (1,2,3,... N). These correspond to the positions in the original string of the characters of the substring.

Thus if the string "tcsin", the numeric subsequence (1,3,5) represents the substring whose characters are from the positions 1,3,5 from the original string, or the substring "tsn".

Regular expressions are a very standard way to represent patterns in strings. One symbol in it is "+", which represents all strings that have one or more occurrences of the preceding character. Thus the regular expression t+c+s+i+n+ represents any string which has a string of t's followed by a string of c's followed by a string of s's followed by a string of i's followed by a string of n's. Each of these strings of repeating letters must have at leat one character. Thus ttcsssiiiiinn, tcsin, tcccsiin all satisfy it, while tcin does not (the string of s's has 0 characters) and tscin does not (the string of c's is after the string of c's, when it should be before).

If the length of the string is N, the objective is to count the number of distinct numeric subsequences of (1,2,3,... N) that correspond to a substring that matches the regular expression t+c+s+i+n+

Input

The input will be one line of a string of letters.

Output

The output is the remainder when the number of distinct numeric subsequences is divided by (109+7)

Constraints

5≤ N ≤ 105

Example 1

 

Input:

tcstcsin

Output:

7

Explanation:

Here, N is 8, and we are looking for distinct subsequences of (1,2,...8). The distinct numeric subsequences and the corresponding substrings are given. It may be seen that all the substrings match the regular expression, and there are no more numeric subsequences that correspond to substrings that match the regular expression. As there are 7 distinct numeric subsequences, the output is 7. [the remainder when 7 is divided by (109+7)]

Numeric        Substring

(1,2,3,7,8)               tcsin

(1,2,3,6,7,8)            tcssin

(1,2,6,7,8)               tcsin

(1,2,5,6,7,8)            tccsin

(1,5,6,7,8)               tcsin

(1,4,5,6,7)               ttcsin

(4,5,6,7)                  tcsin

Example 2

Input:

tcsintcsin

Output:

11

Explanation:

Here, N is 10, and we are looking for distinct subsequences of (1,2,...10). The distinct numeric subsequences and the corresponding substrings are given. It may be seen that all the substrings match the regular expression, and there are no more numeric subsequences that correspond to substrings that match the regular expression. As there are 11 distinct numeric subsequences, the output is 11 [the remainder when 11 is divided by (109+7)]

Numeric                    Substring

(1,2,3,4,10)                tcsin

(1,2,3,4,5,10)             tcsinn

(1,2,3,4,9,10)             tcsiin

(1,2,3,4,10)                tcsin

(1,2,3,8,9,10)             tcssin

(1,2,8,9,10)                tcsin

(1,2,8,9,10)                tcsin

(1,2,7,8,9,10)             tccsin

(1,7,8,9,10)                tcsin

(1,6,7,8,9,10)             ttcsin

(6,7,8,9,10)                tcsin

(1,2,3,4,5)                  tcsin

ROUND VAULTS IN BANK | Code vita 2017

Problem Description:

In the strong room of ABC bank there are N vaults arranged in a circle. 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. 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! Note that as the vaults are arranged in a circle, the last vault is adjacent to the first one.

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

Input Format:

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 its vaults in order

Output Format:

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

The vaults 1, 5, 6 are looted, giving a total loot of (1000+5000+9000)=15000

Example 2

Input

10

1000,2000,3000,5000,9000,7000,6000,4000,7000,5000

Output

26000

Explanation

There are 10 vaults arranged in a circle. The amounts in the vaults are 1000, 2000, ... 5000.

One way of getting the maximum is to loot vaults 4, 5, 9 and 10 giving a total of 26000. Hence the output is 26000. Note that no 5 adjacent vaults have more than 2 looted.

PALINDROME SORTING | Code vita 2017

Problem Description:

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. Given a palindrome write a program to print the sorted list of all palindromes that can be constructed from the alphabets of the given palindrome. All palindromes should start in a newline.

Input Format:

The first line, an integer T, indicating the number of test cases
T lines each containing one string (palindrome)

Output Format:

For each test case, one line indicating the Test case number
The next lines containing a sorted list of all palindromes constructed from the given palindrome of the ith test case

Constraints:

T ≤ 10

Example 1

Input 

1
NITIN

Output 

INTNI
NITIN

Explanation 

There are only two palindromes that can be constructed from NITIN

Example 2

Input 

1
ABCDCBA

Output 

ABCDCBA
ACBDBCA
BACDCAB
BCADACB
CABDBAC
CBADABC

Explanation 
Since there is only one D, it can only be the middle letter in the palindrome. The remaining lettere A, B, C can be arranged in 6 possible ways and each way gives rise to a palindrome.

CONCATENATING PRIME | Code vita 2017

Problem Description:

If you like numbers, you may have been fascinated by prime numbers. Sometimes we obtain by concatenating two primes. For example, concatenating 2 and 3, we obtain the prime 23. The aim is to find all such distinct "concatenated primes" that could be obtained by concatenating primes ≤ a given integer N.

Input Format:

Integer N

Output Format: 

M, the number of distinct primes that could be obtained by concatenating two primes ≤ N

Constraints:

N ≤ 70

Example 1 

Input

10

Output

4 

Explanations

The primes ≤ 10 are 2, 3, 5, 7. These can be used to form the following concatenated numbers: 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77. Of these, there are four primes: 23 37 53 and 73. Hence the output is 4. 

Example 2

Input

20 

Output

17 

Explanation

The prime numbers up to 20 are 2 3 5 7 11 13 17 and 19. 

Concatenating these two at a time in all possible ways, we get the following numbers:

22 23 25 27 211 213 217 219

32 33 35 37 311 313 317 319

52 53 55 57 511 513 517 519

72 73 75 77 711 713 717 719

112 113 115 117 1111 1113 1117 1119

132 133 135 137 1311 1313 1317 1319

172 173 175 177 1711 1713 1717 1719

192 193 195 197 1911 1913 1917 1919

We have the following 17 primes numbers in this list: 23 37 53 73 113 137 173 193 197 211 311 313 317 719 1117 1319 1913 Hence the output would be 17.

BOOK FAIR | Code vita 2017

Problem Description:

It is the Annual Book Fair. There are thousands of book stalls and this year the organizers introduced a new scheme. In every stall either you can collect a coupon bearing a number but then you must skip next k stalls or you can simply go to the next stall without collecting the coupon. At the end, your prize is free books worth the sum of the numbers on the coupon you have collected.

Input Format:

The first line has two positive integers, N (the number of stalls) and k (the number of stalls to skip if you collect a coupon).

The next N lines have 1 positive integer each, which is the value of the coupons you collect from the corresponding stall.

Output Format:

The output is one number that is the maximum value of the sum of coupons collected according to the rules.

Constraints:

N<50

Number on the coupon <1000

Example 1

Input

10,2

4

5

8

7

5

4

3

4

6

5

Output

19

Explanation

N =10, k=2

The highest value is obtained if you pick the stall numbers 1,4,7,10, giving a value of 4+7+3+5=19.

Example 2

Input

10,2

50

70

40

50

90

70

60

40

70

50

Output

230

Explanation

There are 10 stalls, and k=2. The coupon values are as shown. If you visit stalls 2, 5 and 9, you get a total value of 230, which is the maximum possible. The output is 230.

SMALLEST MULTIPLE IN PERMUTED DIGITS | Code vita 2017

Problem Description:

Given two integers N, d , find the smallest number that is a multiple of d that could be formed by permuting the digits of N. You must use all the digits of N, and if the smallest multiple of d has leading zeros, they can be dropped. If no such number exists, output -1.

Input

A line containing two space separated integers, representing N and d.

Output

A single line giving the permutation of N that is the smallest multiple of d, without any leading zeroes, if any. If not such permutation exists, the output should be -1

Constraints

1≤N≤1000000000000
1≤d≤1000000

Example 1

Input

210
2

Output

12

Example 2

Input

1707693158
853684

Output
513917768

Example 3

Input

531
2

Output

-1

Explanation

1. In first test case the minimum number formed using all the three digits divisible by the given divisor is 012 which is equivalent to 12 and this is a multiple of d = 2. Hence the output is 12.
2. In second test case the minimum number formed using all the digits divisible by the given divisor is 0513917768. So in this case the output will be 513917768.
3. In the last case all permutations of digits of N are odd and hence not divisible by d.