Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2879. В поисках Цири
Поиск в глубину (DFS)Бинарный поиск
Олимпиадные задачи на русском языке
| 28/03/2026 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (08) |
Ограничения: время – 750ms/1500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Велен — прямоугольник размером `H` на `W` клеток. Вам известно положение ведьмака и клетка, в которую он должен попасть, чтобы покинуть провинцию. По пути к клетке-выходу ведьмак может перемещаться между соседними по стороне клетками и не должен покидать пределов прямоугольника. Благодаря своей быстроногой лошади Плотве Геральт передвигается практически мгновенно и может преодолеть за день любое количество клеток.
В первый день поисков в одной из клеток находится отряд королевской пограничной стражи. В начале каждого из следующих `N` дней отряд перемещается в одну из соседних по стороне клеток (по известному заранее маршруту). Клетка, в которой находятся пограничники, а также все посещенные ими ранее клетки являются для ведьмака непроходимыми. Совершив последнее перемещение в день `N+1`, отряд останавливается и больше не двигается.
Найдите максимальный номер дня, в который Геральт ещё может добраться до выхода любым доступным к тому моменту путем (не обязательно кратчайшим). А затем выведите какой-нибудь из таких путей.
В первой строке ввода содержатся `2` положительных целых числа `H` и `W` — высота и ширина провинции (в клетках, `1 <= H, W <= 10^5`). Верхняя левая клетка провинции имеет координаты `(1, 1)`, нижняя правая — `(H, W)`.
Во второй строке ввода содержатся `4` целых числа: `S_1`, `S_2`, `F_1`, `F_2` — текущее положение Геральта и положение клетки-выхода (`1 <= S_1, F_1 <= H`, `1 <= S_2, F_2 <= W`). Клетки `(S_1, S_2)` и `(F_1, F_2)` не совпадают.
В третьей строке содержатся `3` целых числа: `G_1`, `G_2` — положение пограничников в первый день (`1 <= G_1 <= H`, `1 <= G_2 <= W`) и `N` — длина маршрута, по которому они передвигаются (`1 <= N <= 10^5`).
В четвертой строке содержится описание маршрута пограничников — строка из `N` прописных букв. Каждая буква описывает направление перемещения в очередной день: `U`-вверх, `D`-вниз, `L`-влево, `R`-вправо. Гарантируется, что все клетки, которые посещает отряд, попарно различны и лежат в пределах прямоугольника. Гарантируется, что ни начальная клетка отряда, ни одна из клеток, посещаемых им по маршруту, не совпадает ни с клеткой `(S_1,S_2)`, ни с клеткой `(F_1,F_2)`.
В первой строке выведите единственное целое число `T` — максимальный номер дня (считая с первого), в который Геральт может достичь клетки-выхода, не проходя через клетки с пограничными заставами. Если пути не существует даже в первый день, выведите `0`. Если путь существует даже после того, как солдаты прошли весь запланированный маршрут, выведите `10^9`.
Если в первой строке выведено положительное число `T`, то во второй строке должно следовать описание пути Геральта из клетки `(S_1,S_2)` в клетку `(F_1,F_2)` в том же формате, в каком был описан путь пограничников (строка из прописных букв `U`, `L`, `D` и `R`). Путь не должен проходить через клетки, посещенные солдатами в день `T` или раньше. Путь не обязательно должен быть кратчайшим из возможных, но количество букв не должно превосходить `10^6`. Путь не должен выходить за пределы прямоугольника. Гарантируется, что, если решение существует, то существует и путь, удовлетворяющий этим ограничениям. Если путей несколько, выведите любой подходящий.
```sample Пример ввода 1
4 5
4 2 1 5
4 4 11
LULURURDRDD
```
```sample Пример вывода 1
6
LUUURRRR
```
Пояснение к примеру 1: маршрут, доступный на шестой день, изображен на первом рисунке (числа в клетках — номер дня, в который клетку посещают пограничники и она становится недоступной). В седьмой и последующие дни ни одного подходящего маршрута не существует. Финальное состояние провинции изображено на втором рисунке.
 
```sample Пример ввода 2
1 6
1 5 1 1
1 3 1
R
```
```sample Пример вывода 2
0
```
```sample Пример ввода 3
3 3
1 1 2 2
3 3 1
U
```
```sample Пример вывода 3
1000000000
RD
```
