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.


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).


To the first and only line of input output the solution.


1 1 3 3
5 5 7


hide comments
Waseem Ahmed: 2021-06-20 17:32:10

Finally got an AC with Dijkstra. Wonderful problem. Learnt many new concepts.

Thanks a lot for the test case @Gurpreet Singh!! And for the expected answer @Branfili.

may_007: 2020-08-19 09:15:14

AC in one go.

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
1 1 1000 1000
31232 323452 21353321

Branfili: 2013-02-21 15:18:55

To me, it comes out as 13413466

Last edit: 2013-02-21 20:31:22
Gurpreet Singh: 2011-08-22 15:29:30

Whats the answer for following test case:
1 1 1000 1000
31232 323452 21353321

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.
Thanks Gustav! Nice Problem!

Last edit: 2011-02-14 18:14:19
: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.

Nice problem BTW, thanks Gustav :)

Last edit: 2011-01-08 21:48:20
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
Time limit:1.145s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem