Qus 1.

You’ll be given a grid as below:

0 1 0 2 0 --> Non highlighted part
02221
02111
10100
00122
11001
x x S x x -->highlighted yellow
In the grid above,

1: This cell has a coin.

2: This cell has an enemy.
0: It contains nothing.
The highlighted(yellow) zone is the control zone. S is a spaceship that we need to control so
that we can get maximum coins.
Now, S’s initial position will be at the center and we can only move it right or left by one
cell or do not move. At each time, the non-highlighted part of the grid will move down by
one unit.
We can also use a bomb but only once. If we use that, all the enemies in the 5×5 region
above the control zone will be killed.
If we use a bomb at the very beginning, the grid will look like this:

0 1 0 2 0 --> Non highlighted part

00001
00111
10100
00100
11001
x x S x x --> highlighted yellow
As soon as, the spaceship encounters an enemy or the entire grid has come down, the game ends.
For example,
At the very first instance, if we want to collect a coin we should move left **( coins=1)**. This is because when
the grid comes down by 1 unit we have a coin on the second position and by moving left we can collect that coin.
Next, we should move right to collect another coin **( coins=2)** .
After this, remain at the same position **( coins=4)**.
This is the current situation after collecting 4 coins.
01020 01000
0 2 2 2 1 -->after using 0 0 0 0 1
x x S x x -->bomb xxSxx
Now, we can use the bomb to get out of this situation. After this, we can collect at most 1 coin. So
maximum coins=5.

Qus2.
Qus3.

There are n balloons and n bullets and each balloon is assigned with a particular number (point).
Whenever a particular balloon is shot the no of points increases by 1.the multiplication of point
assigned to balloon on left and that of right side.

2.point assigned to left if no right exists

3.point assigned to right if no left exists.

4.the point assigned to itself if no other balloon exists.

You have to output the maximum no of points possible.

Input

1234

Output

20

qus 4.

Given a directed graph. Check whether a graph contain a cycle or not.

Qus 5.

qus 6.

Given a graph print either of the set of the vertices that are colored with the same color. And if the
graph is not bipartite print “-1”. Test cases also included the cases when a graph is not connected.
qus 7

Mr. Kim has to deliver refrigerators to N customers. From the office, he is going to visit all the
customers and then return to his home. Each location of the office, his home, and the customers is
given in the form of integer coordinates (x,y) (0≤x≤100, 0≤y≤100) . The distance between two
arbitrary locations (x1, y1) and (x2, y2) is computed by |x1-x2| + |y1-y2|, where |x| denotes the
absolute value of x; for instance, |3|=|-3|=3. The locations of the office, his home, and the customers
are all distinct. You should plan an optimal way to visit all the N customers and return to his among
all the possibilities.
You are given the locations of the office, Mr. Kim’s home, and the customers; the number of the
customers is in the range of 5 to 10. Write a program that, starting at the office, finds a (the) shortest
path visiting all the customers and returning to his home. Your program only have to report the
distance of a (the) shortest path.

Constraints

5≤N≤10. Each location (x,y) is in a bounded grid, 0≤x≤100, 0≤y≤100, and x, y are integers.

Input

You are given 10 test cases. Each test case consists of two lines; the first line has N, the number of
the customers, and the following line enumerates the locations of the office, Mr. Kim’s home, and
the customers in sequence. Each location consists of the coordinates (x,y), which is reprensented by
‘x y’.

Output

Output the 10 answers in 10 lines. Each line outputs the distance of a (the) shortest path. Each line
looks like ‘#x answer’ where x is the index of a test case. ‘#x’ and ‘answer’ are separated by a
space.

I/O Example

Input (20 lines in total. In the first test case, the locations of the office and the home are (0, 0) and
(100, 100) respectively, and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70),
(50, 20).)

5 ← Starting test case #1

0 0 100 100 70 40 30 10 10 5 90 70 50 20

6 ← Starting test case #2

88 81 85 80 19 22 31 15 27 29 30 10 20 26 5 14
10 ← Starting test case #3

39 9 97 61 35 93 62 64 96 39 36 36 9 59 59 96 61 7 64 43 43 58 1 36

Output (10 lines in total)

#1 200

#2 304

#3 366

Qus 8
There is a maze that has one entrance and one exit. Jewels are placed in passages of the maze. You
want to pick up the jewels after getting into the maze through the entrance and before getting out of
it through the exit. You want to get as many jewels as possible, but you don’t want to take the same
passage you used once.

When locations of a maze and jewels are given, find out the greatest number of jewels you can get
without taking the same passage twice, and the path taken in this case.

Input

There can be more than one test case in the input file. The first line has T, the number of test cases.
Then the totally T test cases are provided in the following lines (T ≤ 10 ).

In each test case, In the first line, the size of the maze N (1 ≤ N ≤ 10) is given. The maze is N×N
square-shaped. From the second line through N lines, information of the maze is given. “0” means a
passage, “1” means a wall, and “2” means a location of a jewel. The entrance is located on the
upper-most left passage and the exit is located on the lower-most right passage. There is no case
where the path from the entrance to the exit doesn’t exist.
Output

From the first line through N lines, mark the path with 3 and output it. In N+1 line, output the
greatest number of jewels that can be picked up. Each test case must be output separately as a
empty.

Qus 9

There is an island surrounded by oil mines. You will be given n companies and m oil mines having
values. You have to distribute the mines to "n" companies in fair manner. Remember the companies
can have oil mines adjacent to each other and not in between of each others.After distributing them
compute the difference of oil mines from the company getting highest and company getting lowest.
This number should be minimum.(then only the distribution can be termed as fair).
Example
Input
2
24
6 13 10 2
24
6 10 13 2

output
5
1

qus 10.
A company sells its products with a unique serial number on it. Company has has found that there
are some products that don’t sell well which are identified to have ominous numbers in the serial
number of the product. So if a serial number of the product contains atmost ’k’ ominous number
then it won’t sell. Given a range form s to e, you need to find number of products that would sell,
leaving out the products that contains atmost ’k’ ominous numbers.
Input: First line contains the number of test cases, followed buy the range s to e, 1

qus 12

Company S has developed an industrial endoscope available to explore inner part of the decrepit
water pipes. It is possible to explore the inner part of the pipes putting the endoscope in a certain
part of the pipe. The endoscope can be moved in the pipe only. Meanwhile, when the pipes are
connected to each other, if the length of the endoscope is long enough to explore ,then it is able to
inspect the connected pipes. However, we cannot observe every pipe because the length of
endoscope is limited.
When the map of the ground water pipe, the location where the endoscope to out in, and the length
of the endoscope is given, calculate the number of pipe which are available to explore. Length of
endoscope means the range upto which endoscope can explore. There are seven kind of pipes, and
description for each pipe are shown below:

S.
N Pipe Connected to
o
Up, Down, Left,
1
Right

2 Up, Down

3 Left, Right

4 Up, Right

5 Down, Right

6 Down, Left

7 Up, Left

When the map of the ground water pipe, the location where the endoscope to out in, and the length
of the endoscope is given, calculate the number of pipe which are available to explore. Length of
endoscope means the range upto which endoscope can explore.

Input

In the first line, T, the number of total test cases is given. From the second line, T test cases are
given. In the first line of each test case, N, the height of the map of the ground water pipes, M, the
width, R, the vertical location of the water pipe where to put in the endoscope, C, the horizontal
location of it, and the length of the endoscope L are given. In the following N lines information of
the map of ground water pipe is given. Each line has M numbers. Each number (from 1 to 7) means
the type of water pipe for that point. 0 means there is no water pipe buried in that place.
Output

Print the respective answer for T test cases in total for T lines. The answer is the number of water
pipes which is available to observe using the endoscope.

Qus 13
qus 14

A Research team want to establish a research center in a region where they found some rare-
elements.They want to make it closest to all the rare-elements as close as possible so that they can
reduce overall cost of research over there.It is given that all the rare-element’s location is connected
by roads.It is also given that Research Center can only be build on road.Team decided to assign this
task to a coder.If you feel you have that much potential.
Here is the Task :- Find the shortest of the longest distance of research center from given locations
of rare-elements.
locations are given in the matrix cell form where 1 represents roads and 0 no road.. number of rare-
element and their location was also given(number<=5) and order of square matrix was less than
equal to (20).
qus 15
There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is
given. There are N number of warmholes; each warmhole has 5 values. First 2 values are starting
co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole
and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-
directional. Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2). The main problem
here is to find minimum distance to reach spaceship from source to destination co-ordinate using
any number of warm-hole. It is ok if you wont use any warmhole.