| Автор: | И. Блинов | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены hi.
Цель робота — преодолеть все стены, достать флаг, который находится в конце полосы за всеми стенами, и вернуться обратно. Стену можно преодолеть двумя способами: подняться, проплыть над ней и опуститься обратно или сделать подкоп. Если стена была преодолена с помощью подкопа, то в при проходе в обратную сторону можно воспользоваться уже готовым подкопом. Всего разрешается сделать не более m подкопов.
Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.
Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.
Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел hi - высоты стен.
Выходной файл должен содержать строку NO, если задание выполнить невозможно.
В противном случае — две строки: строку YES и строку из 2n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n
символов содержат описание прохождения от стены с номером n до стены с номером 1.
Если решений несколько, выведите любое из них.
1 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 40 | 1 ≤ n, m ≤ 102, 1 ≤ k, hi ≤ 109 | полная | |
| 2 | 60 | 1 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 109 | 1 | полная |
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
1) Можно потратить все подкопы, если n ≤ m,
иначе можно сделать n подкопов и пройти маршрут только с помощью команд D.
Далее всегда считаем, что n ≤ m.
2) Если стена преодолевается с помощью подкопа, то подкоп лучше сделать при первом проходе стены. Это позволит сэкономить один дополнительный прыжок.
3) Исходя из пункта 2, каждую стену, через которую следует преодолеть с помощью подъёма, мы переплываем дважды.
4) Теперь мы знаем, что всего следует сделать 2 ⋅ n − 2 ⋅ m подъёмов и высота последнего подъёма H = k − (2 ⋅ n − 2 ⋅ m) + 1.
5) Не важно, сможет ли робот переплыть препятствие при первом проходе, так как при обратном проходе максимальная высота подъёма робота будет меньше.
6) Используя пункты 1-5. Для решения задачи нам достаточно пробежать по всем стенам слева направо и действовать следующим образом: если высота стены меньше или равна H, то эту стену мы переплываем и увеличиваем максимальную возможную высоту подъёма H на 1. В противном случае эту стену следует преодолеть подкопом. Если уже робот уже смог преодолеть n − m стен, то все оставшиеся стены проходим подкопом. Далее можно легко восстановить ответ, зная, какие стены как преодолеваются подкопом. Асимптотика решения O(n).