Programming Geek
Rated 4.7/5 based on 1446 reviews

## Consider the lattice of circular disks each of which has center at a point (i, j), 0 <= i, j<=N, and radius 1/2. A convex polygonal line is drawn through the centers of these circles. Consider all the disks that are either completely inside the polygonal area or whose centers are on the boundary of the polygon. Find the total number of these disks that lie within the polygon.

In the figure above, the polygon is ABCDEFGA, and the points H, I and J are centers of disks that lie on the boundary. In the figure above, the portion of the areas of the disks marked y that lie inside the polygon should not be counted whereas those disks marked x must be included.
Constraints
N<=30
k<=12
Input Format
The first line of the input is a positive integer N, the size of the grid (number of disks on each row and column of the grid)
The next line has a single positive integer k, the number of vertices of the polygon.
The next k lines contain a set of four non-negative integers, giving the x and y coordinates of the starting and ending vertices in one segment of the polygon. Note that the segments may not be given in any order
Output
One line giving the number of disks in the polygon, using the counting method described above (if the polygon goes exactly through the center, or the disk is entirely within the polygon, count the disk)
Test Case
```
TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

```

### Explanation

Example 1
Input
8
4
2,1,1,7
1,7,6,8
6,2,2,1
6,2,6,8
Output
26
Explanation
The polygon and related disks are shown below.

There are 17 disks wholly within the polygon ABCD, 4 at the corners (A,B,C,D) and 5 through whose centers the line CD goes exactly through, giving a total of 26. Hence the output is 26
Example 2
Input
8
5
6,1,2,1
3,6,1,4
5,5,6,1
5,5,3,6
2,1,1,4
Output
19
Explanation
The polygon ABCDE is shown below

There are 10 internal disks in the polygon ABCDE. The disks on the side between B and C, those between D and E, and those between E and A are all partially cut, and not counted. Apart from the 5 vertices (A, B, C, D and E), the line AB goes through the centres centers of 3 disks (F, G, H) and the side CD goes through the center of 1 disk (I), which all need to be counted. The total number of disks to be counted is 10 + 5 + 3 + 1=19. Hence the output is 19.

## Test Case

```
TestCase 1
8
5
6,1,2,1
3,6,1,4
5,5,6,1
5,5,3,6
2,1,1,4

19

TestCase 2
8
4
2,1,1,7
1,7,6,8
6,2,2,1
6,2,6,8

26

```

### Explanation

Example 1
Input
7
-4,-2
-4,2
-6,6
2,2
8,4
6,-4
6,2
Output
17
Explanation
The polygon AGFEDCB is shown below. Trees are planted at points where the x and y coordinates are even, and the corner points are also even.

As can be seen, the number of trees on the boundary are 11, and the number of trees in the interior is 6, giving a total of 17 trees.
Example 2
Input
7
-2,-4
-4,-6
-6,4
0,0
6,6
8,-6
4,-4
Output
28
Explanation
The polygon ABCDEFG is shown below. The trees are on the corner points and the boundary and interior points which have both x and y coordinates even.

There are 11 boundary trees and 17 interior trees. Hence the output is 28.

## Problem Description

There are a N students in a high school class. For simplicity, the students are named A, B, C, . . . (up to the Nth letter of the alphabet). No two students have exactly the same height.
The Principal of the school wants to organize a class photograph where the students are arranged in descending order of heights. The class teacher has been asked to list the students in descending order of heights to send to the photographer.
The teacher does not know the heights of the various students. However, there are a set of photographs, which between them have all the students in that class. From each of the photographs, the teacher obtained a list of students in descending height order and needs to combine them into one list of students in descending height order.
It is possible that the photographs do not fully determine the ordering in the list. In this case, as it is vacation time, the teacher needs to write to some of the students to send her their exact height, so that she can create the complete list.
The objective is to write a program that can list the students to whom she must write to determine their heights.
Constraints
N<=26, K<=10
Input Format
Line 1 contains two comma separated positive integers, N and K. N gives the number of students in the class (A,B,C, . . .), and K is the number of photographs
The next K lines each contain a comma separated list of the students in descending order from the corresponding photograph.
Output
Output should be one comma separated list (in alphabetical order) of students whose height must be known to create the ordered list. If it is not necessary to write to any student, the output should be N/A
Test Case
```
TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

```

### Explanation

Example 1
Input
8,3
D,C,E,F,G,H
C,A,B,E
D,B
Output
N/A
Explanation
N is 8 and K is 3, and so there are 8 students and 3 photographs. As the students are named the first N letters of the alphabet, the students are A, B, C, D, E, F, G, H.
The first photograph shows the ordering as D, C, E, F, G, H, that is D is taller than C who is taller than E and so on. The second photograph shows that C is taller than A, who is taller than B who is taller than E. The third photograph shows that D is taller than B.
From photograph 1, E, F, G and H are all shorter than C, and are in that order. From photograph 2, A and B are taller than E and in that order. Hence A, B, C and D are all taller than E, F, G and H. Hence the last four in the final ordered list must be E, F, G, H in that order.
From the first photograph, D is taller than C, and from the second photograph, C is taller than A who is taller than B. Hence the order of the first four is D, C, A, B. The third photograph confirms this order.
Hence the full list is D, C, A, B, E, F, G, H. The full order can be determined without writing to any student to get their height. Hence the output is N/A.
Example 2
Input
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E
Output
A,B
Explanation
N is 8 and K is 3. The students are A, B, C, D, E, F, G, H (the first N letters of the alphabet)
As before, from photographs 1, 2 and 3, we can determine that A, B, C and D are taller than E, F, G, H, and that E, F, G, H are the last four in the ordered list.
From the first photograph, D is taller than C, and from the second photograph, C is taller than A. From the third photograph, C is taller than B. The possible orders of the first four could be D, C, A, B or D, C, B, A. No information is present in any of the photographs which says which order is correct. Hence the teacher must write to both B and A to determine their heights so as to establish the correct order. The output must be sorted in alphabetic order, and hence the output is A,B.

## Problem Description

The casino has introduced a new game in which there are M vertical chutes each containing N single digit (possibly zero) numbers. You can choose any chute and draw the bottom number and when you do this all the other numbers in the chute descend by one slot. You need to build the largest integer using this process drawing all the numbers from the chutes. For example, in the following example, we have three chutes of four numbers each and the largest number that can be drawn is 469534692781. Given the number of chutes and the numbers in each chute, write a program to find the largest integer that could be formed using the above process.

to find the largest integer that could be formed using the above process.

Constraints
1 <= M <= 20, 1 <= N <= 50

Input Format
First line contains M,N two comma separated integers giving the number of chutes and the number of digits in each chute
The next M lines each contain N comma separated digits, giving the digits from top to bottom in each of the chutes.

Output
One line containing the largest integer that could be formed.

Test Case
```
TestCase 1
4,4

7,5,5,2

3,6,1,7

8,7,0,4

8,7,3,9

9743782557163078

TestCase 2
2,3

1,2,3

2,4,6

643221

```

### Explanation

Example 1
Input
2,3
1,2,3
2,4,6
Output
643221
Explanation
M is 2 and N is 3 (there are 2 chutes with 3 digits in each). The chutes look like this

The largest integer that can be formed is 643221
Example 2
Input
4,4
7,5,5,2
3,6,1,7
8,7,0,4
8,7,3,9
Output
9743782557163078
Explanation
M is 4 and N is 4. The chutes look like this

The largest integer that can be formed is 9743782557163078, and this is the output.

## Problem Description

A number (N) of lines (extending to infinity) in both directions are drawn on a plane. The lines are specified by the angle (positive or negative) made with the x-axis (in degrees). It may be assumed that the different lines are not coincident (they do not overlap each other) and that no three of them are concurrent (no three of them pass through the same point).
The objective is to determine the number of triangles formed by the set of these lines
If the lines are given with an angle of 10, 70, 30 and 30, the figure looks like this

L1 is at 10 degrees to the x axis, L2 is at 70 degrees to the x axis, L3 and L4 are at 30 degrees to the x-axis. It can be seen that there are two triangles (L1,L2,L3 and L1,L2,L4). L3 and L4 do not meet as they are parallel.
Constraints
N<=50
-89 <= angle for any line <=90
Input Format
The first line of the input consists of a single integer, N.
The next line consists of a series of integers (positive, zero or negative), each corresponding to a separate line, and giving the angle that it makes with the x-axis (measured in degrees and in the anticlockwise direction).
Output
The output is a single integer giving the number of triangles formed by the lines
Test Case
```
TestCase 1
8,3
D,C,E,F,G,H
C,A,E
D,C,B,E

A,B

TestCase 2
8,3
D,C,E,F,G,H
C,A,B,E
D,B

N/A

```

### Explanation

Example 1
Input
5
20,-20,0,50,50
Output
7
Explanation
There are 5 lines, with angles at 20,-20,0, 50 and 50 degrees with the x-axis. The figure looks like this

There are 7 triangles, those formed by (L1,L2,L3),(L1,L2,L5), (L1,L2,L4), (L1,L3,L4), (L1,L3,L5), (L2,L3,L5), (L2,L3,L4). Hence the output is 7.
Example 2
Input
5
50,-50,50,-50,50
Output
0
Explanation
There are 5 lines with angles 50,-50,50,-50 and 50 degrees. The figure looks like this

As L1,L3 and L5 are parallel, and L2 and L4 are parallel, no triangles are formed by any set of three lines. Hence, the output is 0.

### TCS CodeVita Previous years' question

Watch this Space for TCS CodeVita Previous years' question.

I will be publishing most of the TCS CodeVita questions as and when I get. As I depend on you guys for the TCS CodeVita's questions so I might not be able to publish all the questions. Keep sending your CodeVita's question at vikash@programminggeek.in.  The questions published below are not all the questions asked previously in CodeVita's. These are only a few.

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita

CodeVita