Условие

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

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

Пусть дорога содержит n полос для движения. Пронумеруем полосы от 1 до n слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак «движение по полосам» разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:

• если с i-й полосы разрешено движение в a-м направлении, а с j-й полосы — в b-м направлении, причем i < j, то a ≤ b;

• с каждой полосы разрешено движение хотя бы в одном направлении;

• в каждом направлении разрешено движение хотя бы с одной полосы.

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

Примеры

Ввод: 4 2 Вывод: 7

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

// Функция для подсчета количества возможных знаков "движение по полосам"
fun traffic(m: Int, n: Int): String {
    val dp = Array(m) { LongArray(n) { 1L } } // Двумерный массив для хранения количества возможных вариантов

    for (i in 1 until m) {
        for (j in 1 until n) {
            // Заполняем массив по формуле динамического программирования
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]
        }
    }

    return dp[m - 1][n - 1].toString() // Возвращаем итоговое количество вариантов
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`)) // Читаем вводные данные
    val writer = BufferedWriter(OutputStreamWriter(System.out)) // Готовим буферизированный вывод
    val (m, n) = reader.readLine().split(" ").map { it.toInt() } // Читаем значения m и n
    writer.write(traffic(m, n)) // Вычисляем и записываем результат
    writer.newLine()
    writer.flush()
    writer.close()
}