Задача по питону
Линейный футбол
Ограничение по времени: 1
секунда
Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.
В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть 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
‑го игрока).
Система оценки
Решения, правильно работающие для случаев, в которых количество игроков не превосходит 100
, получат не менее 44 баллов.
Решения, правильно работающие для случаев, в которых все игроки, кроме самого правого, ударяют вправо, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых левая половина игроков ударяет вправо, а правая половина игроков ударяет влево, причём количество игроков, перебрасывающих мяч на противоположную половину поля, не превосходит 10, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых каждая игра заканчивается взятием ворот, получат не менее 12
баллов.
Пояснение
В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый —
девятому, девятый — восьмому, восьмой — седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.
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]) 