CRAN01 - An Experiment by Penny
Penny started studying in a community college. However she did not tell Leonard about this because she did not want Leonard helping her at every point in her studies. This went well until the professor ordered her to perform an advanced experiment. In this experiment she was given an advanced microbiological specimen. This specimen is placed in an n X m size grid which is divided into 1 X 1 cells.
It expands according to following rules.
If at time t, the specimen occupies (x ,y), then at time t+1 it can expand to at most any two cells out of (x+1,y), (x-1,y), (x,y+1), (x,y-1).
For example if at t = 0 sec if the specimen occupies (4, 5), then at time t = 1 sec, the state of the grid can be any of the following
1. specimen at (4,5), (5,5) and (3,5).
2. specimen at (4,5), (5,5) and (4,6).
3. specimen at (4,5), (5,5) and (3,4).
4. specimen at (4,5), (3,5) and (4,6).
5. specimen at (4,5), (3,5) and (4,4).
6. specimen at (4,5), (4,6) and (4,4).
Note- At t= 2 sec, it can expand from all the points that the specimen occupied at t= 1.
The professor asks penny to find the minimum time it takes for the specimen to fill the entire grid.
Since penny is not so smart at math and she can't ask Leonard to help her, she turns to you for help and to find the solution to above problem.
T - The number of test cases.
n m - number of row and columns in the grid.
x y - coordinate of the initial position of the specimen.
The minimum time in seconds it takes for specimen to fill in the entire grid.
1 <= T <= 50
1 <= n, m <= 500
1 <= x <= n
1 <= y <= m
6 4 Output: 0
nice logic...try with different cases on paper
it should be (3,5) instead of (3,4) because it doesn't satisfying the above 4 movements..
Nice problem :) easy but not very obvious logic..Last edit: 2015-04-06 07:26:14
awesome problem.Although had to take help.Heres a hint:
took me a while to get the logic. So simple !!Last edit: 2014-05-28 11:44:06
I like dumb girls like Penny. It's because of them we look smart, smart enough to solve such questions. :P
@Pranay should be (4,4), author made a mistake.
how is movement to (3,4) from (4,5) (point 3 in shown example) valid for the given 4 movements ?
simple and elegant :)