08-09-2016, 09:57 AM
1453711518-Q9..pdf (Size: 484.47 KB / Downloads: 6)
Given below are 5 Programming questions, you have to solve any
3 out of 5 questions.
These 5 questions you can attempt in any technology like C/C++,
java, .Net
To solve these 5 questions you’ve max. 3 hours.
Question: - 1
Farmer Don watches the fence that surrounds his N meter by N meter square, flat field
(2<=N<=500,000). One fence corner is at the origin (0, 0) and the opposite corner is at (N,N); the
sides of Farmer Don's fence are parallel to the X and Y axes.Fence posts appear at all four corners
and also at every meter along each side of the fence, for a total of 4×N fence posts. The fence posts
are vertical and are considered to have no radius. Farmer Don wants to determine how many of his
fence posts he can watch when he stands at a given location within his fence. Farmer Don’s field
contains R (1<=R<=30,000) huge rocks that obscure his view of some fence posts, as he is not tall
enough to look over any of these rocks. The base of each rock is a convex polygon with nonzero area
whose vertices are at integer coordinates. The rocks stand completely vertical. Rocks do not
overlap, do not touch other rocks, and do not touch Farmer Don or the fence. Farmer Don does not
touch the fence, does not stand within a rock, and does not stand on a rock. Given the size of Farmer
Don's fence, the locations and shapes of the rocks within it, and the location where Farmer Don
stands, compute the number of fence posts that Farmer Don can see. If a vertex of a rock lines up
perfectly with a fence post from Farmer Don's location, he is not able to see that fence post.
Input
The first line of input contains two space-separated integers: N and R.
The next line of input contains two space-separated integers that specify the X and Y
coordinates of Farmer Don's location inside the fence.
The rest of the input file describes the R rocks:
o Rock i’s description starts with a line containing a single integer pi (3 £ pi £ 20), the number of
vertices in the rock's base.
o Each of the next pi lines contains a space-separated pair of integers that are the X and Y
coordinates of a vertex. The vertices of a rock’s base are distinct and given in counterclockwise
order.
The first line of input contains two space-separated integers: N and R. The next line of input contains
two space-separated integers that specify the X and Y coordinates of Farmer Don's location inside
the fence. The rest of the input file describes the R rocks: Rock i’s description starts with a line
containing a single integer pi (3<=pi<=20), the number of vertices in the rock's base. Each of the
next pi lines contains a space-separated pair of integers that are the X and Y coordinates of a vertex.
The vertices of a rock’s base are distinct and given in counterclockwise order.
Output
The output file should contain a single line with a single integer, the number of fence posts visible
to Farmer Don.
Example:
Input:
100 1
60 50
5
70 40
75 40
80 40
80 50
70 60
Output:
319
Question: - 2
Abotrika is having a party because his team won the african cup so he is inviting his friends to eat
some pizza.
Unfortunately,Abotrika's friends can't eat an entire pizza but all of them know exactly how much
pizza they can eat and insist on getting the exact amount of pizza but Abotrika eats one complete
pizza and all of them wants his amount of pizza in one slice.
Their requests break down to three different pizza slices-either one quarter or a half or three
quarters of pizza.
write a program that will help Abotrika to find out what is the minimal number of pizzas he has to
order so that everyone gets exact amount of pizza they want.
Input
First line contains an integer N, 0<=N<=10,000 , number of friends.
In each of next N lines there is amount of pizza that each of Abotrika's friends wants to eat, that is
the fraction 1/4 , 1/2 or 3/4.
Output
In the first and only line you should write the minimal number of pizzas Abotrika has order don't
forget to order one complete pizza for Abotrika.
Example:
Input:
3
1/2
3/4
3/4
Output:
4
Input:
5
1/2
3/4
1/2
1/4
1/4
Output:
4
Question: -- 3
John is moving to a different city and he wants to use all his perishable food before doing it,
to avoid wasting. Luckily all he has now is eggs, flour, sugar and milk, so he is going to make
his famous cakes and give them to his friends as a goodbye gift.
John only knows how to make an entire cake and not half a cake, a third of a cake, or any
other portion. So, he will buy whatever is needed of each ingredient so that he can make an
integer number of cakes and have nothing left. Of course, he wants to spend as little money as
possible. You must help John to decide how much he should buy of each ingredient.
Input
The input contains several test cases. Each test case is described in a single line that contains
eight integers E, F , S, M , E' , F' , S' and M' separated by single spaces. Values E and E' are
numbers of eggs, F and F' are grams of flour, S and S' are grams of sugar, and M and M' are
centiliters of milk. For each ingredient, X is the amount John has (0 ≤ X ≤ 1000), while X' is
the amount needed to make a single cake (1 ≤ X ≤ 1000). The last line of the input contains
the number −1 eight times separated by single spaces and should not be processed as a test
case.
Output
For each test case output a single line with four non-negative integers separated by single spaces,
representing the amount of each ingredient John needs to buy, in the same order and units as
the input.
Example:
Input:
2 3 4 5 1 1 1 1
3 6 9 0 1 2 3 4
-1 -1 -1 -1 -1 -1 -1 -1
Output:
3 2 1 0
0 0 0 12
Question: - 4
You have a sequence of integers. You can paint each of the integers black or white, or leave
it unpainted. The black integers must appear in ascending order and the white integers
must appear in descending order. The ascending/descending order must be strict, that
is, two integers painted with the same color cannot be equal. Paint the sequence so as to
minimize the number of unpainted integers.
Input
The input contains several test cases, each one described in exactly two lines. The first line
contains an integer N indicating the number of elements in the sequence (1 ≤ N ≤ 200).
The second line contains N integers Xi separated by single spaces, representing the
sequence to paint (1 ≤ Xi ≤ 106 for 1 ≤ i ≤ N ). The last line of the input contains a
single −1 and should not be processed as a test case.
Output
For each test case output a single line with an integer representing the minimum number
of unpainted elements of the sequence, when the sequence is painted optimally following
the rules described above.
Example:
Input:
8
1 4 2 3 3 2 4 1
12
7 8 1 2 4 6 3 5 2 1 8 7
-1
Output:
0
2
Question: - 5
Abotrika is a famous player who plays in a good team , his team is going to play the final match next
week and he have to train hard because all his fans are expecting that Abotrika will score more than
one goal , so his team-mates suggested helping him in training given that Abotrika will play alone
against all his friends in the training.
Input
Given two integers N,M (length and width of the training court) , 2<=N,M<=20 and X,Y the starting
point of Abotrika on the court where X is number of row and Y is number of column 1<=X,Y<=N,M
then P[i][j],where P is the power of each of his friends 0< P[i][j]<100 , and P[X][Y] is the power of
Abotrika.
Output
The output must be one line either "N" or "Y then the maximum power "Abotrika can get when he
pass from his friends to reach the (the goal who is at the cell P[N][M] in the court ). NOTE
: Abotrika's power decreases by the power of his team-mate whom Aboutrika succeeded to get
through on his way to score a goal. "Y" means that he had scored a goal with power at least 0 and
"N" if he couldn't reach the goal with zero power at least … don't forget that Abotrika can move
through two directions either right or downwards to reach the goal.
Example:
Input:
4 4
1 1
100 55 10 2
20 10 90 1
60 20 22 4
1 30 70 5
Output:
Y 23