fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. string ans = "0", dn[10][100];
  6. bool check[10][100];
  7. int n;
  8.  
  9. string sum(string a, string b)
  10. {
  11. 	if (a.length() < b.length()) swap(a, b);
  12. 	int tmp = 0;
  13. 	for (int i = 0; i < b.length(); i++)
  14. 	{
  15. 		tmp += a[i] - 48 + b[i] - 48;
  16. 		a[i] = tmp % 10 + 48;
  17. 		tmp /= 10;
  18. 	}
  19. 	for (int i = b.length(); i < a.length(); i++)
  20. 	{
  21. 		tmp += a[i] - 48;
  22. 		a[i] = tmp % 10 + 48;
  23. 		tmp /= 10;
  24. 	}
  25. 	while (tmp)
  26. 	{
  27. 		a += tmp % 10 + 48;
  28. 		tmp /= 10;
  29. 	}
  30. 	return a;
  31. }
  32.  
  33. string rec(char ch, int index)
  34. {
  35. 	if (ch == 'A') return "0";
  36. 	if (index == n - 1) return "1";
  37. 	if (check[ch - 48][index]) return dn[ch - 48][index];
  38. 	char tmp1 = 'A', tmp2 = 'A', tmp3 = 'A';
  39. 	switch (ch)
  40. 	{
  41. 	case '0': tmp1 = '4'; tmp2 = '6'; break;
  42. 	case '1': tmp1 = '6'; tmp2 = '8'; break;
  43. 	case '2': tmp1 = '7'; tmp2 = '9'; break;
  44. 	case '3': tmp1 = '4'; tmp2 = '8'; break;
  45. 	case '4': tmp1 = '0'; tmp2 = '3'; tmp3 = '9'; break;
  46. 	case '5': break;
  47. 	case '6': tmp1 = '0'; tmp2 = '1'; tmp3 = '7'; break;
  48. 	case '7': tmp1 = '2'; tmp2 = '6'; break;
  49. 	case '8': tmp1 = '1'; tmp2 = '3'; break;
  50. 	case '9': tmp1 = '2'; tmp2 = '4'; break;
  51. 	}
  52. 	check[ch - 48][index] = 1;
  53. 	return dn[ch - 48][index] = sum(rec(tmp1, index + 1), sum(rec(tmp2, index + 1), rec(tmp3, index + 1)));
  54. }
  55.  
  56. int main() {
  57. 	cin >> n;
  58. 	for (int i = 0; i < 10; i++) for (int j = 0; j < n; j++) check[i][j] = 0;
  59. 	for (int i = 0; i < 10; i++) if ((i != 0) && (i != 8)) ans = sum(ans, rec((char)(i + 48), 0));
  60. 	for (int i = ans.length() - 1; i >= 0; i--) cout << ans[i];
  61. }
Success #stdin #stdout 0s 16088KB
comments (?)
stdin
copy 
1
stdout
copy 
8
https://ideone.com/rDVAxA
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!