SKY - Sky Lift
We can represent a grid of skyscrapers by an NxN matrix of their positive heights. A skyscraper is made out of square blocks, and you may travel through them using a special elevator that can move as any other, but also sideways (four possible directions on a fixed floor). They may move anywhere as long as they don't exit the skyscrapers. In other words, if the elevator is inside a skyscraper, it may move to the neighboring skyscraper only if its height is greater or equal to the current level the elevator is at.
Moving sideways (in one of the 4 directions, that is, N, E, S, W...) is done for free when using this elevator, but moving one floor up or down costs exactly one unit.
Given the positions of two skyscrapers, find the cost of moving from the top block of the first to the top block of the second using the described elevator.
Input
The first line of input contains a single integer N ( 1 <= N <= 1000 ). The next line contains four integers, xa, ya, xb, yb, (between 1 and N), representing the positions of the two skyscrapers.
The next line contains three integers: A, B and C (1 <= A, B, C <= 109).
Generate the height of the skyscraper at coordinates (i, j) using the formula hij = (((i-1)*N+j-1)*A + B) mod C (indicies are 1-based).
Output
To the first and only line of input output the solution.
Example
Input:
3
1 1 3 3
5 5 7
Output:
2
hide comments
Waseem Ahmed:
2021-06-20 17:32:10
Finally got an AC with Dijkstra. Wonderful problem. Learnt many new concepts.
|
|
naruto09:
2015-10-21 18:47:29
if moving sideways doesnot cost anything then the answer is just the difference between the heights of 2 buildings..?? am i wrong..?? |
|
zain:
2015-09-27 03:45:46
dijekstra got AC |
|
deepak garg:
2015-02-03 15:49:31
Getting wa any tricky test cases. running successfully for
|
|
Branfili:
2013-02-21 15:18:55
@Gurpreet
|
|
Gurpreet Singh:
2011-08-22 15:29:30
Whats the answer for following test case:
|
|
Ravi Kiran:
2011-08-22 15:29:30
Answer may not fit in signed 32 bit integer type.I lost my AC for overlooking that fact initially.
|
|
:D:
2011-08-22 15:29:30
The grid size is NxN. First coordinate is x/i and second y/j. All values are 1-based.
|
|
Ayush:
2011-08-22 15:29:30
I am not able to understand the problem. What is xa,xb,ya,yb,i,j? |
Added by: | gustav |
Date: | 2011-01-03 |
Time limit: | 1.145s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem |