maximzombi

Посчитаем ответ для случая с 1 и 2 тумблерами: f(1)=1 f(2) = 2 Пусть тумблеров n штук. Чтобы выключить самый левый, нужно, чтобы (n-1)-ый тумблер слева остался вкл, а остальные выкл. Чтобы выключить n-2 левых, нужно f(n-2) переключений. Также нужно переключить сам левый тумблер (т.е. еще одно переключение). Итого этими действиями мы привели тумблеры к виду: 0100...00, где 1 - вкл, 0 - выкл Чтобы выключить (n-1)-й тумблей, нужно включить все тумблеры правее него(т.е. нужно включить только (n-2)-й тумблер, но для его включения нужно включить (n-3)-й тумблей и т.д.). Чтобы включить все тумблеры правее (n-1)-го, необходимо также f(n-2) действий. Теперь тумблеры имеют вид 0111...11 Осталось перевести все тумблеры левее самого левого в режим выкл., на что понадобится f(n-1) действий. Итого получаем рекуррентную формулу: f(1)=1, f(2)=2, f(n)=f(n-2) * 2 + f(n-1) + 1 => f(7) = 85