|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Ремейк задачи Всероссийской командной олимпиады школьников по програмированию Как известно, плесени свойственно разрастаться. По каким правилам? Чтобы это выяснить, учёные поместили колонию плесневых грибков на одну клеточку вафли и стали наблюдать. На второй день плесень заполнила все клетки, соприкасающиеся с заплесневелой стороной или углом. На третий день плесень поразила те клетки, которые имели общую сторону с заплесневелыми, на четвёртый - опять плесень опять распространялась на другие клетки и через общую сторону, и через угол. В итоге учёные сделали вывод, что плесень в нечётные дни распространяется только через общую сторону, а в нечётные ещё и через общий угол. Непонятно? Вот картинка, на которой колония плесени на 5-й день эксперимента. Число обозначает день, на который клетка заплесневела. Как видите, после 5 дней плесень занимает 69 клеток вафли.
Разработайте программу, которая определяет количество клеток, занятых плесенью за первые N дней эксперимента. Входные данные. Натуральное число N, не превышающее 100 миллионов - продолжительность эксперимента. Выходные данные. Одно натуральное число - количество клеток, занятых плесенью после N дней эксперимента. Для отправки решений необходимо выполнить вход. |