1462. Хоттаб-share |

1463. Бег по коридору |

1464. Шагающий циркуль |

1465. Флэш-моб |

1466. Стиральный вопрос |

1467. Fence relicts |

1468. Group by GCD |

1470. Improve RLE |

24/02/2024 02:05:20

Олимпиадные задачи на английском языке

24/06/2010 | Лето 2010 дорешивание (10H) |

14/07/2010 | Лето 2010 - 10 (H) |

*Ограничения: время – 3s/6s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

The Gridland is a small country located on a beautiful hilly landscape. It is well known for its
achievements in the fields of nanotechnology and car industry.

The country has many cities, located in the nodes of `W\ times\ H` grid with square cells.
All roads between cities go straight along the lines of the grid in either north-south or east-west direction
and have the same length.

A young scientist Vasya Reshetkin developed a new hi-tech car powered by nuclear batteries. The car is very
energy-efficient: while going uphill, the car consumes a fixed amount of energy per unit of distance, and while
going downhill it stops the engine, consuming no energy at all. That means that the amount of energy required to
travel along the fixed route from `A` to `B` and then back from `B` to `A` depends only on the distance, and not on the
inclination profile of the road.

Thus if the car requires `a` units of energy to move from a city to its neighbor, then moving back will
require `L-a` units, where `L` is the same for all cities. To simplify maintenance, each battery was
designed to store exactly `L` units of energy.

Unfortunately, prolonged storage of half-used batteries may lead to nuclear
contamination of the environment, so it is important that the batteries are always used fully.

Your country is known for achievements in computer programming. So you have been given a job to
write a program that plans a route from city `A` to city `B` such that it will use exactly `L\ -\ k` units of energy
for some integer `k`. This route may not be the shortest one, but this is a price Gridland citizens
are willing to pay for environment preservation.

First line of input file contains integers `L\ W\ H` – battery capacity, width and height of city grid respectively.

Second line contains integers `r_A\ c_A\ r_B\ c_B` – row and column of city `A` and row and column of city `B` respectively.
Rows span from west to east in order of increasing column numbers. Columns span from north
to south in order of increasing row numbers. All numbering is zero-based.

Next `H\ -\ 1` lines contain `2\ *\ W\ -\ 1` integers `e_1\ s_1\ …\ e_{W-1}\ s_{W-1}\ s_W`, where `e_i` is the energy
required to move from `i`-th city in the row to its eastern neighbor, and `s_i` – energy to move to its southern neighbor.

Last line contains `W\ -\ 1` integers `e_i` – energy required to move from the `i`-th city in the southernmost row to
its eastern neighbor.

Output file must contain a single line with the string of symbols "`N`", "`S`", "`E`", "`W`",
describing a route from city `A` to city `B` which requires integer amount of batteries of capacity `L`. It there is
more than one answer, output any of them not exceeding `3(H\ +\ W)L` in length. If there is no answer,
output a single symbol "`X`".

`2\ ≤\ L,\ W,\ H\ ≤\ 1000`, `0\ ≤\ e_i,\ s_i\ ≤\ L`

Sample Input

5 3 2 1 0 0 2 4 2 5 2 4 2 2

Sample Output

ENE