|
Линейный футбол
(Время: 2 сек. Память: 32 Мб Сложность: 44%)
Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.
В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть n игроков. Для определённости пронумеруем их позиции числами от 1 до n слева направо.
Ворота находятся в позициях 0 и n+1. Каждый игрок имеет свою силу удара и может при ударе по мячу перебросить его на фиксированное количество позиций другому игроку. Силу удара игрока на позиции i обозначим через ai, что означает, что после удара этого игрока мяч переместится на ai позиций. Если ai положительное, то мяч переместится вправо, в сторону увеличения номеров, а если ai отрицательное, то мяч переместится влево, в сторону уменьшения. Если после удара мяч попадает в позицию, меньшую либо равную 0, то засчитывается гол в левые ворота, а если в позицию, большую либо равную n+1, то в правые. Если после удара мяч попадает к другому игроку, то тот наносит следующий удар со своей силой, и игра продолжается.
Близнецы решили сыграть n игр, в i-й из которых первый удар нанесёт игрок номер i. Для каждой игры выведите, в какие ворота будет забит мяч в этой игре (L, если в левые, R, если в правые, U, если гол никто не забьёт).
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 105) – количество игроков. Далее в следующих n строках указаны силы и направления ударов игроков. В i+1 строке указана сила игрока ai, находящегося в позиции i. После удара этого игрока мяч окажется в позиции i+ai. (−105 ≤ ai ≤105 для любого i от 1 до n).
Выходные данные
В выходной файл OUTPUT.TXT выведите n символов, обозначающих результаты игр, в одну строку без пробелов. Если пронумеровать эти символы от 1 до n, то в i-й позиции этой строки может находиться символ L для мяча, забитого в левые ворота, R для мяча, забитого в правые ворота и U для случая, когда игра не закончилась взятием ворот (при начале этой игры c удара i-го игрока).
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 10
-5
2
0
5
5
-1
6
-1
-1
-5 | LRURUURRRU |
Пояснение
В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый – девятому, девятый – восьмому, восьмой – седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
