fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5.  
  6. 	int n;
  7. 	cin >> n;
  8. 	int dp[5][n+1];	// 1 based indexing
  9.  
  10. 	// Let dp[1][x] = get at A and moves remain = n - x
  11. 	// Let dp[2][x] = get at B and moves remain = n - x
  12. 	// Let dp[3][x] = get at C and moves remain = n - x
  13. 	// Let dp[4][x] = get at D and moves remain = n - x
  14. 	// And at dp[][n-1]	when only one move is remain ant shouldn't be at D
  15. 	// dp[4][0] -> start	// dp[4][n] -> End
  16.  
  17. 	for(int i=0; i<=n; i++)
  18. 	{
  19. 		if(i == 0) 
  20. 		{
  21. 			dp[1][i] = 0;
  22. 			dp[2][i] = 0;
  23. 			dp[3][i] = 0;
  24. 			dp[4][i] = 1;	// from outside to get at D
  25. 		}
  26.  
  27. 		else if (0 < i < n-1)
  28. 		{
  29. 			dp[1][i] = dp[2][i-1] + dp[3][i-1] + dp[4][i-1];	// from B,C,D -> ant can get to A
  30. 			dp[2][i] = dp[1][i-1] + dp[3][i-1] + dp[4][i-1];	// from A,C,D -> ant can get to B
  31. 			dp[3][i] = dp[1][i-1] + dp[2][i-1] + dp[4][i-1];	// from A,B,D -> ant can get to C
  32. 			dp[4][i] = dp[1][i-1] + dp[2][i-1] + dp[3][i-1];	// from A,B,C -> ant can get to D
  33. 		}
  34.  
  35. 		// At n-1 
  36. 		else if (i == n-1)
  37. 		{
  38. 			// Only thing to take care at 'n-1' ant cannot get at D
  39. 			dp[1][i] = dp[2][i-1] + dp[3][i-1] + dp[4][i-1];	
  40. 			dp[2][i] = dp[1][i-1] + dp[3][i-1] + dp[4][i-1];
  41. 			dp[3][i] = dp[1][i-1] + dp[2][i-1] + dp[4][i-1];
  42. 		}
  43.  
  44. 		else if(i == n)
  45. 		{
  46. 			// At 'n' ant should be at D
  47. 			dp[4][i] = dp[1][i-1] + dp[2][i-1] + dp[3][i-1];  
  48. 		}
  49. 	}
  50.  
  51. 	// for(int i=1; i<=4; i++)
  52. 	// {
  53. 	// 	for(int j=0; j<=n; j++)
  54. 	// 		cout << dp[i][j] << " ";
  55. 	// 	cout << "\n";	
  56. 	// }
  57.  
  58. 	cout << dp[4][n] << "\n";
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
4
stdout
copy 
21
https://ideone.com/vrbwkM
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!