Максимальное разрезание
(Время: 1 сек. Память: 16 Мб Сложность: 61%)
Юный математик Егор очень любит вкусно поесть и поэтому часто заглядывает в холодильник. Однажды он достал оттуда палку колбасы и с помощью трёх разрезов ножом получил из нее 4 куска, которые впоследствии благополучно съел.
Конечно, на этом он решил не останавливаться и в следующий раз при открытии холодильника взгляд Егора упал на аппетитную пиццу, которую он разогрел в микроволновой печи, после чего смог разрезать на 7 частей и съесть.
Несмотря на внушительные размеры съеденной пиццы и ее высокую калорийность при следующем открытии заветной двери холодильника Егор не смог устоять перед большим куском сыра, который он смог достать с верхней полки и разрезать на 8 частей.
В отличие от предыдущих продуктов сыр представлял собой серьёзное испытание для Егора и потребовал массу времени для его употребления. В процессе поедания сыра Егор задумался над тем, почему же при равном числе разрезов каждый раз получалось разное количество частей, несмотря на то, что каждый раз Егор старался получить максимальное количество кусков от каждого продукта. В результате он понял, что все дело в размерности: колбасу он рассматривал как одномерный отрезок, пиццу – как двумерный круг, а сыр – как трехмерный куб.
Теперь Егор хочет решить более общую задачу: на какое максимальное количество частей можно разрезать K-мерный куб, используя N прямых разрезов размерности K-1?
Входные данные
Входной файл INPUT.TXT содержит целые числа K и N – размерность куба и количество разрезов размерности K-1 (1 ≤ K, N ≤ 63).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – ответ на задачу Егора.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 3 | 4 |
| 2 | 2 3 | 7 |
| 3 | 3 3 | 8 |
Система оценки
Решения, работающие только для K = 1, будут оцениваться в 10 баллов.
Решения, работающие только для K ≤ 2, будут оцениваться в 40 баллов.
Решения, работающие только для K ≤ 3, будут оцениваться в 80 баллов.
Решения, работающие только для K ≥ N и для K=1 при N=3, будут оцениваться в 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
