SPORT STADIUM | Code vita 2018

It is the sports event of the year for the residents of Sportsville.  Their team had finally made it to the finals of the Bowls League Cup.

Problem Description

It is the sports event of the year for the residents of Sportsville.  Their team had finally made it to the finals of the Bowls League Cup.

They have booked tickets for the city contingent for the same row, and the size of the contingent (N) is smaller than the number of seats booked(S).Unfortunately, there was rain the previous night and some of the seats are still wet. Some of the contingent love Bowls so much and are excited enough not to mind sitting on a wet chair. There are k of these. However, others want to sit on a dry seat so that they can enjoy the match more.

The contingent wants to minimize the distance between the first and last person in the row so that they can still conduct Mexican Waves, and other forms of support for their team.

Because they want to sit together, any block of 15 or more contiguous unoccupied seats between the first person sitting and the last person sitting is unacceptable.

There are M blocks of seats, starting with a dry block, with alternating wet and dry blocks.  The number of seats in each block is known.

Given S (the number of seats in the row), N (the size of the contingent),k (the number of the contingent who are willing to sit in a wet seat), and the distribution of wet and dry blocks, write a program to find the minimum distance between the first and the last member of the contingent in the row.

Input

The first line contains four comma separated numbers representing S, N, k and M respectively.

The second line is a set of M comma separated numbers representing the number of seats in each block of seats.  The first block is dry, and the remaining blocks alternate between wet and dry.

Output

One integer representing the minimum distance between the first and last member of the row.  If it is impossible to seat all the members according to their preferences,and with the unoccupied seat restriction,  the result should be 0.

Constraints

S,N,k < 1000,  M < 30

Example 1

Input

100,50,5,6

3,10,30,5,30,22

Output

49

Explanation

S = 100, and there are 100 seats in the row.  N=50, and there are 50 members in the contingent. k=5, and 5 people (out of the 50) do not mind sitting on wet seats.  M=6, and there are 6 blocks of seats.  The number of seats in each block is 3,10,30,5,30 and 22, with the first block of 3 seats being dry, the next 10 being wet and so on.

One possible positioning to achieve the minimum distance is to place the a set of 30 people in seats 14 to 43 (the dry block), the 5 people who do not mind sitting on wet seats in the wet block 44 to 48, and the remaining 15 people (of the 50) in the seats 49 to 63.  There is no unoccupied seat between the first person and the last person, and so this is acceptable.The distance between the last allocated seat (63) and the first allocated seat (14), is 49.  This is the output.

Example 2

Input

100,50,5,8

3,7,10,10,20,10,20,20

Output

64

Explanation

S = 100, and there are 100 seats in the row.  N=50, and there are 50 members in the contingent. k=5, and 5 people (out of the 50) do not mind sitting on wet seats.  M=8, and there are 8 blocks of seats.

One possible positioning is to have a set of 10 people sit in the dry block 11 – 20, the 5 people who will accept wet seats in seats 21 – 25 (in the wet block 21 – 30), another 20 people in the dry block 31 – 50, leave the wet block 51-60 empty, and seat the remaining 15 people in seats 61 – 75 (in the dry block 61-80.  There is a block of 5 unoccupied seats (26-30) between the first person and the last person.  As this is not more than 15, this is acceptable. The distance from the last allocated seat (75) and the first allocated seat (11) is 64.  This is the result.

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

SORTING BOXES | Code vita 2018

Problem Description

The parcel section of the Head Post Office is in a mess. The parcels that need to be loaded to the vans have been lined up in a row in an arbitrary order of weights. The Head Post Master wants them to be sorted in the increasing order of the weights of the parcels, with one exception. He wants the heaviest (and presumably the most valuable) parcel kept nearest his office.

You and your friend try to sort these boxes and you decide to sort them by interchanging two boxes at a time. Such an interchange needs effort equals to the product of the weights of the two boxes.

The objective is to reposition the boxes as required with minimum effort.

Constraints

N<=50

Weights <= 1000

Input Format

The first line consists of two space separated positive integers giving the number of boxes (N) and the position of the Head Post Master's office (k) where the heaviest box must be.

The second line consists of N space separated positive integers giving the weights of the boxes. You may assume that no two weights are equal.

Output

The output is one line giving the total effort taken to get the boxes in sorted order, and the heaviest in position k.

Explanation

Example 1

Input

5 2

20 50 30 80 70

Output

3600

Explanation

There are 5 boxes (N=5) and the heaviest box must be in position 2 (k=2). If we look at the final order (sorted, with the heaviest at position 2), it should be 20 80 30 50 70. If we look at this, we notice that only the 50 and the 80 parcels need to be exchanged. As this takes effort of the product of the weights, the effort is 4000.

Further reduction can be obtained if we use the smallest package (20) as an intermediary. If we exchange 20 with 50 (effort 1000), then with 80 (effort 1600) and back with 50 again (effort 1000), the effect is the same, with a total effort of 3600 (less th an the effort obtained by the direct move)an the effort

The results after the optimal sequence of exchanges are

50 20 30 80 70

50 80 30 20 70

20 80 30 50 70

As this takes an effort of 3600, the output is 3600.

Example 2

Input

6 3

30 20 40 80 70 60

Output

7600

Explanation

There are 6 parcels, and the heaviest should be at position 3. Hence the final order needs to be 20 30 80 40 60 70. If we look at the initial position, we see that 20 and 30 need to be exchanged (effort 600), 40 and 80 need to be exchanged (effort 3200) and 60 and 70 need to be exchanged (effort 4200). Hence the total effort is 600+3200+4200=8000.

If we use the same approach as in Example 1, we get the following efforts

(600) 20 30 40 80 70 60

(3200) 20 30 80 40 70 60

(1200) 60 30 80 40 70 20

(1400) 60 30 80 40 20 70

(1200) 20 30 80 40 60 70

A total effort of 7600 is obtained rather than an effort of 8000, which is the output.

HOP GAME | Code vita 2018

Problem Description

Dr Felix Kline, the Math teacher at Gauss School introduced the following game to teach his students problem solving. He places a series of “hopping stones” (pieces of paper) in a line with points (a positive number) marked on each of the stones.

Students start from one end and hop to the other end. One can step on a stone and add the number on the stone to their cumulative score or jump over a stone and land on the next stone. In this case, they get twice the points marked on the stone they land but do not get the points marked on the stone they jumped over.

At most once in the journey, the student is allowed (if they choose) to do a double jump that is, they jump over two consecutive stones - where they would get three times the points of the stone they land on, but not the points of the stone they jump over.

The teacher expected his students to do some thinking and come up with a plan to get the maximum score possible. Given the numbers on the sequence of stones, write a program to determine the maximum score possible.

Constraints

The number of stones in the sequence< 30

Input Format

The first line contains N, the number of integers (this is a positive integer)

The next line contains the N points (each a positive integer) separated by commas. These are the points on the stones in the order the stones are placed.

Output

One integer representing the maximum score

Explanation

Example 1

Input

3

4,2,3

Output

10

Explanation

There are 3 stones (N=3), and the points (in the order laid out) are 4,2 and 3 respectively.

If we step on the first stone and skip the second to get 4 + 2 x 3 = 10. A double jump to the third stone will get only 9. Hence the result is 10, and the double jump is not used

Example 2

Input

6

4,5,6,7,4,5

Output

35

Explanation

N=6, and the sequence of points is given.One way of getting 35 is to start with a double jump to stone 3 (3 x 6=18), go to stone 4 (7) and jump to stone 6 (10 points) for a total of 35. The double jump was used only once, and the result is 35.

GEMS COLLECTOR | Code vita 2018

Problem Description

Gems Collection is very interesting game. Given N sacks, each filled with random number of Gems, the objective of the game is to collect maximum number of Gems by picking up the sacks, subject to certain rules.

The rules are as follows

1. Start from left-most sack and move towards right. Player needs to decide then and there whether the current sack is to be picked up or not. Player cannot pick up sacks on the left once the player has moved past them.

2. Player cannot pick two consecutive sacks i.e. if the player picks Si then Si+1 can not be picked

3. The player can skip any number of sacks as desired

4. For every three consecutive skips, the player will get one Super Card.

5. The player can use one super card to pick two consecutive sacks one time

Example:

Gems in sacks: 5 8 12 3 6

Possible pickups without using Super Card: (5 and 12 and 6), (5 and 12), (5 and 3), (5 and 6), (8 and 3), (8 and 6), (12 and 6), only 5, only 8, only 12, only 3 and only 6

A Super Card allows the following pickup -

If Player skips sacks worth 5, 8 and 12 gems then player can pick-up consecutive sacks 3 and 6.

Once a super card is used, its power is lost.

Write a program to determine the maximum number of gems that can be collected by the player as the number of gems in all sacks is already known.

Constraints

1 <= T <= 10

1<= N <= 500

1 <= Gems in one sack <= 100

Input Format

The First line contains one integer T denoting the test cases.

For each test case,

the first line contains one integer N denoting number of sacks.

the second line contains N space delimited integers, representing the number of gems in each sack.

Output

Maximum number of gems for each test case T separated by new line.

Explanation

Example 1

Input:

1

3

7 10 1

Output:

10

Explanation

After applying all 5 rules, player can pick up maximum 10 gems.

Example 2

Input:

3

1

98

6

2 2 2 5 6 7

4

7 8 9 10

Output:

98

18

18

Explanation

For test case 1:

After applying all 5 rules, player can pick up maximum 98 gems as there is only one sack.

For test case 2:

Player will skip first three sacks to gain 1 super card and pickup 5 gems sack, then player will use super card to pick up 6 and 7 gems sack.

So, total gems = 5 + 6 + 7 = 18 gems.

For test case 3:

Player will pick 8 and 10 gems.

FARMING FIGURES | Code vita 2018

Problem Description

You are given N sticks of varying lengths. You need to determine whether it is possible to form a polygon of positive area by arranging them in some order. For example, if three sticks of lengths 1, 1, 1 are given we can easily see that we can form a triangle by arranging them in order. On the other hand, if the sticks have lengths 1, 2, 1, then we cannot form a polygon of non-zero area with these.

Constraints

1 <= N <= 100

Length of any stick will be less than 100

Input Format

The first line contains an integer N indicating number of sticks

The next line contains N space separated positive integers giving the lengths of the sticks

Output Format

One line containing the number of sides of the polygon of most sides (of at least 3 sides) that can be formed with some of the sticks. If no polygon can be formed, the output should be 0.

Explanation

Example 1

Input

3

1 1 1

Output

3

Explanation

N=3, and there are 3 sticks, each of length 1. With three sticks of length 1, we can form a triangle

Example 2

Input

4

1 2 3 6

Output

0

Explanation

We cannot form a 4 sided polygon using all four sticks. Similarly, a triangle cannot be formed with any three sticks. Since no polygon can be formed, the result is 0.

DATE AND TIME | Code vita 2018

Problem Description

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of givingArun 12 distinct digits from 0 to 9, and have him form the largest date time in 2018 with them. Arun is a little nervous, and asks you to help him with a computer program.

Usha will give Arun 12 distinct digits. He needs to create a date time combination in the year 2018: the date in the MM/DD form (all four digits must be present), and the time in the format HH:MM (all four digits must be present). The date may be from 01/01 to 12/31 and the time may be from 00:00 to 23:59 (in the 24 hour format). The digits provided may be used only once in the answer that Arun gives.

If more than one date time combination may be formed, Arun needs to give the latest valid date time possible in the year 2018.

Constraints

Single digits (any of 0-9)

Input Format

A line consisting of a sequence of 12 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing.

Output

The maximum possible valid date time in the year 2018. The output must be in the format

MM/DD HH:MM

If no date time can be constructed, the output should be 0

Explanation

Example1 :

Input

0,0,1,2,2,2,3,5,9,9,9,9

Output

12/30 22:59

Explanation

The 12 digits to be used by Arun are given.

The maximum valid date time using only the digits given, and with each digit used at most once is

12/30 22:59

This is the output.

Example 2

Input

3,3,3,3,3,3,3,3,3,3,3,3

Output

0

Explanation

As no digit less than 3 is present in the input, a valid month cannot be formed. Hence no valid Date time can be formed with the input digits.

CROSS WORDS | Code vita 2018

Problem Description

A crossword puzzle is a square grid with black and blank squares, containing clue numbers (according to a set of rules) on some of the squares. The puzzle is solved by obtaining the solutions to a set of clues corresponding to the clue numbers.

The solved puzzle has one letter in each of the blank square, which represent a sequence of letters (consisting of one or more words in English or occasionally other languages) running along the rows (called “Across”, or “A”) or along the columns (called “Down” or “D”). Each numbered square is the beginning of an Across solution or a Down solution. Some of the across and down solutions will intersect at a blank square, and if the solutions are consistent, both of them will have the same letter at the intersecting square.

In this problem, you will be given the specifications of the grid, and the solutions in some random order. The problem is to number the grid appropriately, and associate the answers consistently with the clue numbers on the grid, both as Across solutions and as Down solutions, so that the intersecting blank squares have the same letter in both solutions.

Rules for Clue Numbering

The clue numbers are given sequentially going row wise (Row 1 first, and then row2 and so on)

Only blank squares are given a clue number

A blank square is given a clue number if either of the following conditions exist (only one number is given even if both the conditions are satisfied)

It has a blank square to its right, and it has no blank square to its left (it has a black square to its left, or it is in the first column). This is the beginning of an Across solution with that number

It has a blank square below it, and no blank square above it (it has a black square above it or it is in the first row). This is the beginning of a Down solution with that number

Constraints

5<=N<=15

5<=M<=50

Input Format

The input consists of two parts, the grid part and the solution part

The first line of the grid part consists of a number, N, the size of the grid (the overall grid is N x N) squares. The next N lines correspond to the N rows of the grid. Each line is comma separated, and has number of pairs of numbers, the first giving the position (column) of the beginning of a black square block, and the next giving the length of the block. If there are no black squares in a row, the pair “0,0” will be specified. For example, if a line contains “2,3,7,1,14,2”, columns 2,3,4 (a block of 3 starting with 2), 7 (a block of 1 starting with 7) and 14,15 (a block of 2 starting with 14) are black in the corresponding row.

The solution part of the input appears after the grid part. The first line of the solution part contains M, the number of solutions. The M subsequent lines consist of a sequence of letters corresponding to a solution for one of the Across and Down clues. All solutions will be in upper case (Capital letters)

Output

The output is a set of M comma separated lines. Each line corresponds to a solution, and consists of three parts, the clue number, the letter A or D (corresponding to Across or Down) and the solution in to that clue (in upper case)

The output must be in increasing clue number order. Ifa clue number has both an Across and a Down solution, they must come in separate lines, with the Across solution coming before the Down solution.

Explanation

Example 1

Input

5
5,1
1,1,3,1,5,1
0,0
1,1,3,1,5,1
1,1
5
EVEN
ACNE
CALVE
PLEAS
EVADE

Output

1,A,ACNE

2,D,CALVE

3,D,EVADE

4,A,PLEAS

5,A,EVEN

Explanation

N is 5, and the disposition of the black squares are given in the next 5 (N) lines. The grid looks like this

BRIDE HUNTING | Code vita 2018

Problem Description

Sam is an eligible bachelor. He decides to settle down in life and start a family. He goes bride hunting.

He wants to marry a girl who has at least one of the 8 qualities mentioned below:-

1) The girl should be rich.

2) The girl should be an Engineer/Doctor.

3) The girl should be beautiful.

4) The girl should be of height 5.3".

5) The girl should be working in an MNC.

6) The girl should be an extrovert.

7) The girl should not have spectacles.

8) The girl should be kind and honest.

He is in search of a bride who has some or all of the 8 qualities mentioned above. On bride hunting, he may find more than one contenders to be his wife.

In that case, he wants to choose a girl whose house is closest to his house. Find a bride for Sam who has maximum qualities. If in case, there are more than one contenders who are at equal distance from Sam’'s house; then

print "“Polygamy not allowed”".

In case there is no suitable girl who fits the criteria then print “"No suitable girl found"”

Given a Matrix N*M, Sam's house is at (1, 1). It is denoted by 1. In the same matrix, the location of a marriageable Girl is also denoted by 1. Hence 1 at location (1, 1) should not be considered as the location of a marriageable Girl’s location.

The qualities of that girl, as per Sam’'s criteria, have to be decoded from the number of non-zero neighbors (max 8-way) she has. Similar to the condition above, 1 at location (1, 1) should not be considered as the quality of a Girl. See Example section to get a better understanding.

Find Sam, a suitable Bride and print the row and column of the bride, and find out the number of qualities that the Bride possesses.

NOTE: - Distance is calculated in number of hops in any direction i.e. (Left, Right, Up, Down and Diagonal)

Constraints

2 <= N,M <= 10^2

Input Format

First Line contains the row (N) and column (M) of the houses.

Next N lines contain the data about girls and their qualities.

Output

It will contain the row and column of the bride, and the number of qualities that Bride possess separated by a colon (i.e. :).

Explanation

Example 1

Input:

2 9

1 0 1 1 0 1 1 1 1

0 0 0 1 0 1 0 0 1

Output:

1:7:3

Explanation:

The girl and qualities are present at (1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,4),(2,6),(2,9).

The girl present at (1,3) has 2 qualities (i.e. (1,4)and (2,4)).

The girl present at (1,4) has 2 qualities.

The Bride present at (1,6) has 2 qualities.

The Bride present at (1,7) has 3 qualities.

The Bride present at (1,8) has 3 qualities.

The Bride present at (1,9) has 2 qualities.

The Bride present at (2,4) has 2 qualities.

The Bride present at (2,6) has 2 qualities.

The Bride present at (2,9) has 2 qualities.

As we see, there are two contenders who have maximum qualities, one is at (1,7) and another at (1,8).

The girl who is closest to Sam's house is at (1,7). Hence, she is the bride.

Hence, the output will be 1:7:3.

Example 2

Input:

6 6

1 0 0 0 0 0

0 0 0 0 0 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 0 0 0 0

Output:

4:4:8

Explanation:

The bride and qualities are present at (3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)

The Bride present at (3,3) has 3 qualities (i.e. (3,4),(4,3) and (4,4)).

The Bride present at (3,4) has 5 qualities.

The Bride present at (3,5) has 3 qualities.

The Bride present at (4,3) has 5 qualities.

The Bride present at (4,4) has 8 qualities.

The Bride present at (4,5) has 5 qualities.

The Bride present at (5,3) has 3 qualities.

The Bride present at (5,4) has 5 qualities.

The Bride present at (5,5) has 3 qualities.

As we see, the girl present in (4,4) has maximum number of Qualities. Hence, she is the bride.

Hence, the output will be 4:4:8.