Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.
В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть n игроков. Для определённости пронумеруем их позиции числами от 1 до n слева направо. Ворота находятся в позициях 0 и n+1. Каждый игрок имеет свою силу удара и может при ударе по мячу перебросить его на фиксированное количество позиций другому игроку. Силу удара игрока на позиции i обозначим через ai, что означает, что после удара этого игрока мяч переместится на ai позиций. Если ai положительное, то мяч переместится вправо, в сторону увеличения номеров, а если ai отрицательное, то мяч переместится влево, в сторону уменьшения. Если после удара мяч попадает в позицию, меньшую либо равную 0, то засчитывается гол в левые ворота, а если в позицию, большую либо равную n+1, то в правые. Если после удара мяч попадает к другому игроку, то тот наносит следующий удар со своей силой, и игра продолжается.
Близнецы решили сыграть n игр, в i‑й из которых первый удар нанесёт игрок номер i. Для каждой игры выведите, в какие ворота будет забит мяч в этой игре (L, если в левые, R, если в правые, U, если гол никто не забьёт).
Формат входных данных
Первая строка входных данных содержит целое число n (1≤n≤105) — количество игроков. Далее в следующих n строках указаны силы и направления ударов игроков. В i+1 строке указана сила игрока ai, находящегося в позиции i. После удара этого игрока мяч окажется в позиции i+ai. (−105≤ai≤105 для любого i от 1 до n).
Формат выходных данных
Выведите n символов, обозначающих результаты игр, в одну строку без пробелов. Если пронумеровать эти символы от 1 до n, то в i‑й позиции этой строки может находиться символ L для мяча, забитого в левые ворота, R для мяча, забитого в правые ворота и U для случая, когда игра не закончилась взятием ворот (при начале этой игры c удара i‑го игрока).
Пояснение
В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый — девятому, девятый — восьмому, восьмой — седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.
1 Ответ
Ответ:
n = int(input())
L = [[] for i in range(n + 2)]
for i in range(1, n + 1):
x = int(input())
if i + x < 1:
L[0].append(i)
elif i + x > n:
L[n + 1].append(i)
else:
L[i + x].append(i)
Ans = [‘U’ for i in range(n + 2)]
Stack = L[0]
while len(Stack) > 0:
p = Stack.pop()
Ans[p] = ‘L’
Stack += L[p]
Stack = L[n + 1]
while len(Stack) > 0:
p = Stack.pop()
Ans[p] = ‘R’
Stack += L[p]
print(».join(str(i) for i in Ans)[1:-1])