Решение задачи Движение по полосам с Яндекс Контест

Без пояснения   Просмотров: 2260

При организации движения по сложным перекресткам, для того, чтобы траектории водителей, выполняющих различные маневры не пересекались, вводят ограничения на возможные маневры водителей, в зависимости от того, по какой полосе движения водитель подъехал к перекрестку. Для этого используется знак «движение по полосам».

Рассмотрим дорогу, подходящую к перекрестку, на котором сходится m дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в m различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся m - 1 дорог. Пронумеруем возможные направления числами от 1 до m слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т. д.

Код 

m, n = map(int, input().split())
dp = []
for i in range(n):
    dp.append([0] * m)
dp[0][0] = 1
for i in range(n):
    for j in range(m):
        if i == n and m == -1:
            infty = dp[i][j]
        if i != n - 1:
            dp[i + 1][j] += dp[i][j]
        if i != n - 1 and j != m - 1:
            dp[i + 1][j + 1] += dp[i][j]
        if j != m - 1:
            dp[i][j + 1] += dp[i][j]
print(dp[n - 1][m - 1])

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp