Властелин Огня напал на Страну Холода. Он уже добрался до ледяной крепости, где живет Снежная Королева, и выстроил свое войско на отрезке длины n недалеко от стен замка. И только ледяной маг Соломон может спасти Страну Холода.
Отрезок длины n находится на расстоянии ровно 1 от стен замка. Его можно мысленно разделить на единичные отрезки. На некоторых из этих единичных отрезков находятся огненные демоны — не более одного демона на позицию. Каждый демон характеризуется силой — некоторым целых положительным числом. Можно считать, что огненные демоны неподвижны.
Изначально Соломон находится на стене крепости. Он может несколько раз подряд выполнять следующие действия:
- > — Соломон перемещается на единицу вправо. Это действие нельзя делать если справа нет ледяного блока.
- < — Соломон перемещается на единицу влево. Это действие нельзя делать на стене замка.
-
- — если перед Соломоном ничего нет, то Соломон создает ледяной блок, который сразу же примораживается к блоку, на котором Соломон сейчас стоит. Если же там уже есть ледяной блок, то Соломон его уничтожает. При этом могут остаться ледяные блоки правее только что уничтоженного и они остаются без опоры. Эти ледяные блоки падают вниз. На каждое из этих действий Соломон тратит ровно одну секунду.
В результате действий Соломона вниз падают отрезки из ледяных блоков. Когда на огненного демона падает ледяной блок, блок превращается в пар, а сила демона уменьшается на 1. Когда сила огненного демона становится равной 0, огненный демон исчезает. Как это происходит, можно посмотреть на рисунке ниже. Ледяной блок, упавший на позицию, где нет демона, разбивается на множество мелких осколков и исчезает, не нанося никому повреждений.
Помогите Соломону за наименьшее время уничтожить все войско Властелина Огня.
В первой строке находится целое число n (1 ≤ n ≤ 1000). В следующей строке находятся n чисел. i-ое из них означает силу огненного демона на i-ой позиции — целое число от 1 до 100. Если в i-ой позиции нет демона, то i-е число равно 0. Гарантируется, что во входных данных имеется хотя бы один огненный демон.
Выведите строку наименьшей длины, состоящую из символов «>», «<» и «*» — последовательность действий, приводящую к искомому результату.
Если возможных ответов несколько — выведите любой.
Позиции демонов: 1 0 1
Действия Соломона: *>*>*>*<<<*
Позиции демонов: 0 2 0
Действия Соломона: *>*>*<**>*<*
Прототип задачи стянут с codeforces.ru
- Форкаем репозиторий, создаем бранч вида
%login%-solution. - Запускаем в корне
php composer.phar installдля автозагрузки классов - Заменяем везде
YourGitHubLoginна свой логин от GitHub (не забываем об PSR-0) в папке src\ - Пишем код, запускаем тесты (просто
vendor/bin/phpunitв папке с проектом), и т.д. - Проверяем стиль кода через phpcs (PRS-2), отсутствие дубликатов черех phpcpd (пример смотреть в .travis.yml)
- Когда все тесты проходят, комментарии написаны, код отрефакторен — отправляем PR в
master-ветку.