//Суть алгоритма в следующем: //"Клавиатура возможностей" == клавиатура, где вместо цифр количество возможных переходов (уже известных) // Для начала берём цикл, что бы пройти по всем возможным началам номера {1,2,3,4,6,7,9} // Затем для каждой кнопки на "Клавиатуре" на которую мы можем перейти увеличиваем количество возможностей на величину, //…

4.2.2.cpp

#include <string>
#include <iostream>
using namespace std;


int main(){

	long long last[10],next[10],i,n,h,ans;

	cin>>n;

	ans=0;
	for (i=0; i <=9; ++i) //проходим по всем циферкам на клаве
		if ((i!=0)&&(i!=5)&&(i!=8)){ // а тут отсеиваем те, с которых начинаться не может
			for (h=0; h<=9; ++h) { //выбираем с какой начинаем и тыкаем ее в соответствующую ячейку массива
				if (h==i) 
					last[h]=1;
				else 
					last[h]=0;
			}
			for (int j = 1; j < n; ++j){ //смотрим по количеству цифр в последовательности начиная с 1, ну понятно почему.
				for (h=0; h<= 9; ++h)//ну понятно
					next[h]=0; 
				for (h=0; h<= 9; ++h)
					if (last[h]>0) // строим последовательность начиная с нашей имеющейся циферки
						switch (h){
						case 0: 
							next[4]+=last[h]; //увеличиваем количество вариантов, которые соответствуют этой цифре на количество потомков
							next[6]+=last[h]; 
							break;
						case 1: 
							next[6]+=last[h]; 
							next[8]+=last[h]; 
							break;
						case 2: 
							next[7]+=last[h]; 
							next[9]+=last[h]; 
							break;
						case 3: 
							next[4]+=last[h]; 
							next[8]+=last[h]; 
							break;
						case 4: 
							next[0]+=last[h]; 
							next[3]+=last[h]; 
							next[9]+=last[h]; 
							break;
						case 6: 
							next[0]+=last[h]; 
							next[1]+=last[h]; 
							next[7]+=last[h]; 
							break;
						case 7: 
							next[6]+=last[h]; 
							next[2]+=last[h]; 
							break;
						case 8: 
							next[1]+=last[h]; 
							next[3]+=last[h]; 
							break;
						case 9: 
							next[4]+=last[h]; 
							next[8]+=last[h]; 
							break;
					}
					for (h=0; h<= 9; ++h)
						if (h!=5) //вообще конечно 5кой он может стать в 1 случае, ну да ладно
							last[h]=next[h]; //делаем новую "клавиатуру возможностей" старой

			}
			for (h=0; h<= 9; ++h)
				ans=ans+last[h];
		}
		if (n==1) 
			++ans; 
		cout<<ans;
		return 0;
}