Подразделы

Другие разделы

Дата и время

12/03/2025 07:12:14

Авторизация

Зарегистрироваться
Восстановить пароль

834. Витрина

Витрина Рис. 1 Рис. 2

Витрина

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Зал супермаркета имеет форму прямоугольника размером

$M$ x

$N$ , в котором расставлены витрины размером 1x1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером

$K$ x1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.

В первой строке входного файла записаны три натуральных числа

$M$ ,

$N$ и

$K$ (

$M,\ N\ ≤\ 100$ ,

$K\ ≤\ M$ ). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число

$V$ – количество витрин (

$0\ ≤\ V\ ≤\ N*M$ ). В следующих

$V$ строках входного файла записаны различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до

$M-1$ ) – расстояние от левой стены супермаркета до витрины, второе (от 0 до

$N-1$ ) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

В первой строке выходного файла выведите минимальное количество витрин, которые необходимо убрать. Во второй строке выведите возможный маршрут передвижения супервитрины в следующем формате. Выводится строка из заглавных латинских букв, обозначающих следующее:

U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.

Количество символов в строке не должно превышать

$N$ x

$M$ .

Если возможных маршрутов несколько, то выведите любой из них.

Пример ввода 1

10 10 5
0

Пример вывода 1

0
RUURUURUURUURU

Пример ввода 2

Пример вывода 2

1
URRRDRRRRUU

Решения, верно определяющие маршрут передвижения супервитрины в случае, когда убирать ни одной витрины не нужно, будут набирать 50 баллов.
Московская городская олимпиада школьников по информатике, 2008