|
Выбор приборов
(Время: 1 сек. Память: 16 Мб Сложность: 37%)
Обозначим через f(n) – количество способов выбора приборов. Легко найти, что f(1)=f(2)=0, f(3)=1. Также легко получаем, что f(n)=f(n div 2)+f(n- n div 2) или при чётном n f(2k)=2f(k), а при нечётном n f(2k+1)=f(k)+f(k+1). Таким образом, пара соседних значений f(n) при n=2k и n=2k+1 выразились через пару соседних значений k и k+1. Рассмотрим случай чётного k=2m. Тогда f(n)=f(2k)=2f(k)=4f(m), а f(n)=f(2k+1)=f(k)+f(k+1)=2f(m)+f(m)+f(m+1)=3f(m)+f(m+1).
Аналогично рассматривается случай и нечётного k. Таким образом, значения искомой функции пересчитывается через соседние вдвое меньшие значения, которые задаются коэффициентами i и j. Вначале эти коэффициенты определяются из соотношения f(n)=i*f(n)+j*f(n+1), т.е. равны i=1, j=0. а далее пересчитывается в зависимости от чётности либо i=2i+j, либо j=i+2j. Также, в зависимости от чётности последнего значения n выводим i или j.
| |
