Задача C. Полоса препятствий

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Одно из заданий на соревнованиях по подводной робототехнике — полоса препятствий. Полоса состоит из n подряд идущих стен, высота i-й стены hi.

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

Робот имеет ограниченный заряд батареи. Изначально он способен подняться над стеной высотой k или меньше, далее после каждого подъёма максимальная высота стены, которую может преодолеть робот, снижается на 1.

Робот поддерживает две команды: D — идти через подкоп (если подкопа ещё нет, то робот выкапывает его), U — проплыть над препятствием.

Формат входного файла

Первая строка входного файла содержит целые числа n m k. Следующая строка содержат n целых чисел hi - высоты стен.

Формат выходного файла

Выходной файл должен содержать строку NO, если задание выполнить невозможно. В противном случае — две строки: строку YES и строку из 2 n символов U и D — последовательность команд робота, которая позволит ему преодолеть полосу препятствий и вернуться обратно. Первые n символов содержат описание прохождение от стены с номером 1 до стены с номером n, следующие n символов содержат описание прохождения от стены с номером n до стены с номером 1.

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

Ограничения

1 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1401 ≤ n, m ≤ 102, 1 ≤ k, hi ≤ 109полная
2601 ≤ n, m ≤ 105, 1 ≤ k, hi ≤ 1091полная

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5 10
10 1 4 2 4 3 4 4 8 9
YES
DUDUDUUUDDDDUUUDUDUD
2
5 1 1
5 5 5 5 5
NO
3
10 10 10000
13123 141323 213323 3213 213213 321 323213 1323 213 1232113
YES
DDDDDDDDDDDDDDDDDDDD

Разбор

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


0.107s 0.012s 13