HomeProgrammingTCS CodeVita 2017 Round 1 Questions

TCS CodeVita 2017 Round 1 Questions

By virtualoops July 29, 2017 Programming 0 Comments
TCS CodeVita 2017 Round 1 Questions
Problem: Ball Passing game

TCS India has organised a blind folded ball passing game for 2 players.

They have special kind of ground where player B can throw the ball in any four
directions (up, down, right, left).

Screenshot (26)

The ground consist of some slant poles on which when the balls strikes the ball
changes its direction by 90 degree as shown below.

Screenshot (44)

If suppose you have thrown a ball in a direction in which there is no pole then
ball goes out of the stadium in that direction.

The player B has the ball initially. The objective is to output the minimum step in
which we can pass to A and also count of poles the ball has struck. If he can never
pass the ball to A, then your output should be -1.

If you get multiple minimum steps then output those steps in which the ball hits
minimum number of barriers.

For example,

A 0 0

0 0

0 B 0

Here two output are possible

4 3 and 4 1 but you have to print 4 1 as output as this path has minimum numbers of
barriers.

Input Format:

First line containing the integer K indicating the size of the field

Next two lines each having a pair of integers separated by space giving the row and
column numbers of the position of A and B respectively K lines of K integers each
separated by space, giving the position of the barrier in the field � 0 indicating
no barrier, 1 indicating a / barrier and 2 indicating a \ barrier.

Output Format:

Minimum number of steps required for the ball to reach A.

Number of barriers ball on which the ball bounces.

Constraints:

3<= K <=20
Example 1

Input

0 3

3 2

0 0 1 0

1 0 1 1

0 0 0 0

2 0 0 0

Screenshot (45)

Output

4 2

Explanation

Shown in the figure above.

Example 2

Input

2 2

0 0

0 0 1

0 0 0

0 0 0

Screenshot (46)

Output

-1

Explanation

The ball goes out of the field after hitting barrier at 1 3

Problem: Forest Fire

Roco is an island near Africa which is very prone to forest fire. Forest fire is
such that it destroys the complete forest. Not a single tree is left.

This Island has been cursed by God, and the curse is that whenever a tree catches
fire it passes the fire to all its adjacent tree in all 8 directions, North, South,
East, West, North-East, North-West, South-East and South-West.

Screenshot (47)

And it is given that the fire is spreading every minute in the given manner, that
is every tree is passing fire to its adjacent tree.

Suppose that the forest layout is as follows T denotes Tree an W denotes water.

Screenshot (48)

As you can see that in the figure below the tree at (3, 3) will pass the Fire to
the its adjacent 5 trees. Other three adjacent places having water and hence it
will not be impacted.

Screenshot (49)

If suppose the tree that catches the fire is at (3, 3), then the fire from 3, 3
will be passed on to (2, 3),(3, 4),(3, 2),(4, 2),(2, 4). Which will happen in 2nd
minute.

Screenshot (50)

Screenshot (51)

Thus from the figure you can see in the 4th minute whole forest will be on fire.

Your task is that given the location of the first tree that catches fire, determine
how long would it take for the entire for us to be on Fire. You may assume that the
layout of the forest is such that the whole forest will catch fire for sure and
that will be at least one tree in the forest.

Input Format:

First line contains two integers M,N, space separated, giving the size of forest in
terms of the number of rows and column respectively.

The next line contains two integers X,Y, space separated, giving the coordinates of
the first tree that catches the fire.

The next M lines, where ith lines containing N characters each of which is either T
or W, giving the position of tree and water in the ith row of the forest.

Output Format:

Single integer indicating the number of minutes taken for the entire to catch fire.

Constraints:
3 <= M <= 20

3 <= N <= 20

Example 1

Input

3 3

1 3

W T T

T W W

W T T

Output

Explanation

In the second minute, Tree at (1,2) catches fire. In the third minute, the tree at
(2, 1) catches fire, fourth minute (3,2) catches fire and in the fifth minute the
last tree at (3, 3) catches fire.

Example 2

Input

6 6

1 6

W T T T T T

T W W W W W

W T T T T T

W W W W W T

T T T T T T

T W W W W W

Output

16

Explanation

The minute at which each tree catches fire is given below:

W 5 4 3 2 1

6 W W W W W
W 7 8 9 10 11

16 15 14 13 12 11

16 W W W W W

Problem: Oil Spill

You are on a rocky island and beneath the surface of the island is a rich source of
Black gold petroleum. But sometimes due to the porous rocks, oil starts gushing out
and you need to move the people to safety before the spill spread to their
neighborhood. The island is full of ups and down and for simplicity you can assume
that one can divide the surface into small square and the elevation is uniform in a
square and is known. Oil always flows down from higher elevation to lower one and
it can spread in any of the 4 adjacent directions (it does not flow diagonally)
from any grid square. However, if all the adjacent square have the same or higher
elevation, it does not flow any further and forma pool at the grid square. If
there are more than one adjacent square which have an elevation lower than the
current square, it flow to a highest of these square (to more than one square if
they are of the same elevation).

We need to determine the length of the longest path the oil spill will spread.

Input Format:

The first line has two comma separated positive integer giving the number of rows
(m) and column (n) of the grid.

The next m lines (one for each row) is the comma separated set of n positive
integers giving the elevation of the corresponding grid square.

The last line is a comma separated set of two integers, the row and column number
of the grid from where the all stats to gush out.

Output Format:

The output is a single line containing the number of squares in the longest path
the oil takes (if it takes more than one path).

Constraints:

m,n <= 10

Elevation of any grid square <=200

Example 1

Input�

3,3

45,40,40
50,55,70

56,58,60

2,3

Output

Explanation

There are 3 rows and 3 columns in the grid. The grid looks like this.

Screenshot (52)

The oil gushes out from (2,3). Its elevation is 70. The elevation of the adjacent
square are 60,55 and 40. I flows to the maximum of these, or 60, at location (3,3).
Using the same logic, the full path is (2,3),(3,3),(3,2),(3,1),(2,1),(1,1),(1,2).
It does not move from (1,2) as all the grid squares adjacent to the square are at
the same ore higher elevation.

Example 2

3,3

30,40,45

50,55,60

53,54,55

2,3

Output

Explanation

The grid looks like this

Screenshot (53)

The oil starts at (2,3). There are three adjacent square of elevation 45,55 and 55.
It will flow to the maximum if these, and as there are two equal, it will flow to
both.

The two paths are (2,3),(2,2)(2,1),(1,1) of the length 4 and (2,3),(3,3),(3,2),

(3,1),(2,2),(1,1) of length 6. As this is the longest path, the output is 6.

Problem : Book Fair

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.

Problem : On a cube

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.A 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 (rn)/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

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
Problem : Collating Sequence

You are writing a book on Physics. Your niece, a Codevita winner, secretly hacked
into your computer, and changed the collating sequence of your alphabet, and then
protected the collating sequence with a password. When you create an index for the
book, you find a strange order, instead of the standard dictionary order.

After a lot of pleading, she says she will reset the sequence if you show you are
smart enough to determine the sequence from some information she will give you. She
says she will give a set of strings in the letters of the alphabet (in upper case),
each of which is in ascending order in the changed collating sequence. You need to
use this to determine the order of all the letters in the alphabet in the changed
sequence.

You know that your niece is tricky, and may not give complete information. In that
case, you know she would expect you to give all possible orders of the letters in
the changed sequence which are consistent with the information given to you. In
such a case, you know she will give enough information to ensure that there are no
more than two possibilities for the collating sequence.

Input Format:

The first line gives the number of strings, N, she will give you

The next N lines give a set of strings, in ascending order in the changed collating
sequence.

Output Format:

If the set of inputs is enough to determine the sequence for the full alphabet, the
output is one line with that sequence.

If multiple sequences satisfy the input given, all the sequences must be given, one
per line, sorted in normal dictionary order. When this occurs, you may assume that
there are no more than two possible sequences.

Constraints:

3<N<15

Length of each string <= 20

Example 1

Input

DCEFGHIPQRSTUVWXYZ

IJKLMNOP

CABEZ

DBQR
Output

DCABEFGHIJKLMNOPQRSTUVWXYZ

Explanation

From string 1, EFGHI and PQRSTUVWXYZ are in normal alphabetical order. From string
2, we know that JKLMNO come between I and P. Hence the order for the last 22
letters of the alphabets is EFGHI]KLMNOPQRSTUVWXYZ. From strings 1 and 3, C,D,A and
B come before E, and must be the first four letters in the collating sequence. From
string 1, D comes before C, and from string 3 C comes before A and A comes before
B. Hence the first four letters must be ordered DCAB. Hence the full collating
sequence is DCABEFGHIJKLMNOPQRSTUVWXYZ, which is the output.

Example 2

Input

DCEFGHIPQRSTUVWXYZ

IJKLMNOP

CAEZ

DCBEQR

Output

DCABEFGHIJKLMNOPQRSTUVWXYZ

DCBAEFGHLIKLMNOPQRSTUVWXYZ

Explanation

As before the last 22 letters are ordered EFGHIJKLMNOPQRSTUVWXYZ. Using strings 1,3
and 4, D, C, A, B all occur before E. Hence they must be the first four. From
string 1 and string 3, D, C and A are in that order. From string 4, D, C and B are
in that order. But no information is available about whether A comes before or
after B in the collating sequence. Hence, we must consider both orders as possible.
The first four letters in order are DCAB or DCBA. Combining this with the last 22
letters gives the two lines in the output. They are in that order as that is the
dictionary order for the two strings.

Problem : Concatenating primes

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

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.