Анализ с конца
Ошибка.
Попробуйте повторить позже
Перестановка чисел 
в некотором порядке называется забавной, если в ней каждое число, начиная со второго слева, либо
больше всех чисел, стоящих левее него, либо меньше всех чисел, стоящих левее него. Например, перестановка 
является забавной, а перестановка 
— нет. Найти количество всех различных забавных перестановок чисел
Источники:
Пойдём с конца. Последнее число 
забавной перестановки либо больше, либо меньше всех чисел множества 
следовательно,
оно равно 1 или 
Предпоследнее число 
забавной перестановки либо больше, либо меньше всех чисел множества 
кроме 
то есть это наименьший или наибольший элемент во множестве 
или во множестве 
В каждом из
случаев есть ровно две возможности выбора, варианты для двух последних чисел перестановки выглядят так 
Несложно убедиться, что при любом 
первые 
чисел 
перестановки образуют интервал из 
подряд
идущих чисел из множества 
а число 
является в этом интервале минимальным или максимальным — всего две
возможности, кроме самого первого числа 
для которого остаётся единственная возможность. Всего получаем ровно 
возможностей выбора.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
