Programming Geek
Rated 4.7/5 based on 1446 reviews

MockVita 2018 Problem: Lattice Disks

Lattice Disks

Problem Description

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.

MockVita 2018 Problem: Orchard

Orchard

Problem Description

There is a large orchard containing apple trees that is coming up for sale. You want to bid for the same but you need to count the number of trees in the orchard so that you can arrive at a reasonable bid. The orchard is quite huge. While the boundaries are straight lines, the area covered by the orchard is a polygon. The polygon is simple (the sides will not intersect) but may not be convex (the interior angles may be more than 180 degrees) However, if you introduce a coordinate system inside the orchard, with the origin at a tree, all the trees are uniformly located at all points whose both coordinates are even integers. (Note that an integer is said to be even if the absolute value is even; hence -6 and 0 are even, -3 is not). The corner points of the boundaries are also at points whose coordinates are even integers. Given the coordinates of the corner points of the boundary, write a program to count the number of trees in the orchard.


Constraints

4<=N<=50

Input Format

The first line contains an integer N which gives the number of boundary corners.

The next N lines each contain two commas separated integers giving the coordinates of the boundary corners in clockwise order (so that the interior of the orchard is always on the right when going from one point to the next).


Output

One integer giving the number of trees in the orchard (including the trees on the boundary).


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.

MockVita 2018 Problem: Finding Products

Finding Product

Problem Description:


You are given a set of N positive integers and two small prime numbers P and Q (not necessarily distinct). You need to write a program to count the number of subsets of the set of N numbers whose product is divisible by PQ (the product of P and Q). Since the number K of such sets can be huge, output K modulo 1009 (the remainder when K is divided by 1009).

Constraints

      N <= 300

      P,Q <=50

      The integers are <= 10000

Input Format:


First line three comma separated integers N, P,Q

The next line contains N comma separated integers

Output:


One integer giving the number of subsets the product of whose elements is divisible by PQ. Give the result modulo 1009.

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
4,5,7
5,49,10,27
Output
6
Explanation
N is 4, P is 5, Q is 7. We need to find subsets of the numbers given so that the product of the elements is divisible by 35 (the product of 5 and 7). These subsets are (5,49),(5,49,10),(5,49,27),(5,49,10,27), (49,10),(49,10,27). There are 6 subsets, and the output is 6.
Example 2
Input
4,11,13
3,7,12,13
Output
0
Explanation
N is 4, P is 11, Q is 13. We need to find subsets of the numbers given so that the product of the elements is divisible by 143 (the product of 11 and 13).As none of the N numbers is divisible by 11 (a prime number), there are no subsets for which the product of the elements is divisible by 143. Hence the output is 0.

MockVita 2018 Problem: Heights of Students

Heights of Students

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.

MockVita 2018 Problem: Largest Integer

Largest Integer

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.

MockVita 2018 Problem: Triangles

Triangles

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.