Автор: | Восьмая всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
Входной файл: | traffic.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | traffic.out |
При организации движения по сложным перекресткам, для того,
чтобы траектории водителей, выполняющих различные маневры
не пересекались, вводят ограничения на возможные маневры водителей,
в зависимости от того, по какой полосе движения водитель
подъехал к перекрестку. Для этого используется знак "движение по
полосам", на рисунке справа приведен пример такого знака,
установленного перед одним из перекрестков в Санкт-Петербурге.
Рассмотрим дорогу, подходящую к перекрестку, на котором сходится m дорог. Водитель, подъезжающий к перекрестку по этой дороге, потенциально может продолжить свое движение в m различных направлениях — обратно по дороге, по которой он приехал, а также по одной из оставшихся m − 1 дорог. Пронумеруем возможные направления числами от 1 до m слева направо с точки зрения подъезжающего водителя, номер 1 получит разворот и возврат по дороге, по которой водитель подъезжал к перекрестку, номер 2 — поворот на самую левую из дорог, и т. д.
Пусть дорога содержит n полос для движения. Пронумеруем полосы от 1 до n слева направо, самая левая полоса получит номер 1, следующая номер 2, и т. д. Знак "движение по полосам" разрешает каждой из полос движение по некоторым из m возможных направлений. При этом должны выполняться следующие условия:
Инспекция по безопасности дорожного движения заинтересовалась, а сколько различных знаков "движение по полосам" можно установить перед таким перекрестком. Помогите им найти ответ на этот вопрос.
Входной файл содержит два целых числа: m и n.
В выходной файл выведите одно число — количество возможных знаков "движение по полосам", которые можно установить перед перекрестком.
В примере возможны следующие варианты знаков "движение по полосам":
С левой полосы | С правой полосы |
разворот | разворот, налево, прямо, направо |
разворот | налево, прямо, направо |
разворот, налево | налево, прямо, направо |
разворот, налево | прямо, направо |
разворот, налево, прямо | прямо, направо |
разворот, налево, прямо | направо |
разворот, налево, прямо, направо | направо |
2 ≤ m ≤ 50, 1 ≤ n ≤ 15
№ | Входной файл (traffic.in ) |
Выходной файл (traffic.out ) |
---|---|---|
1 |
|
|